高中信息科技(选学模块)的复习提纲算法与程序设计Word版

1、高中信息科技（选学模块）的复习提纲算法与程序设计1.1使用计算机解决问题的一般过程(课本P35)1用计算机解决问题的步骤：分析问题à设计算法à编写程序à运行程序à问题解决分析问题：明确要计算机做什么设计算法：寻找到解决问题的途径和方法，并把方法步骤化。编写程序：选定编程语言，编制出相应的计算机程序。运行程序：让计算机一步一步地执行算法，以获得问题所需的计算结果。2计算机程序：指示计算机如何去解决问题或完成任务的一组可执行的指令。（了解）计算机科学克劳斯·沃思指出：算法+数结构=程序3程序设计：寻求解决问题的方法，并将其实现步骤编写成计算机可以执

2、行的程序的过程。4指令：用来规定计算机操作的命令。一条指令要求计算机执行一个动作。5指令集：计算机的所有指令组成了计算机的指令集。6典型的计算机指令：输入、输出、数学运算、逻辑判断、控制转移指令7一个程序由两部分组成：指令部分和数据部分。指令部分是由一系列指令构成，描述解决这个问题的计算过程。数据部分是用来存储计算所需的原始数据、计算的中间结果或最终结果。8设计程序需要考虑的两点：1.数据的存储 2.计算的过程（不仅须指出动作，还须指出动作的次序）1.2算法的概念（课本P6）1（了解）算法的由来：由9世纪阿拉伯数学家花拉子密的名字；派生而来的，这位数学家一生发现了许多求解算术问题的方法，并编写

3、了一本名为复原和化简的规则的书。这本书后来翻译成拉丁文，书名被简化成现在人们所熟悉的“代数学”。2算法的定义：解决问题的具体方法和步骤。即，在有限步骤内求解某一问题所使用的具有精确定义的一系列操作规则。也可以说是：能够清楚地表达解决问题的方法一步步是“怎样做”的过程。3算法的特点：u 有穷性：执行步骤有限、能够终止或在合理的时间范围内完成全部操作。（强调有限和合理间范围）u 确定性：必须有确切的含义，不能含糊、模棱两可。u 可行性：每个步骤能够在有限的时间内实际做到。u 有0个或多个输入。u 有一个或多个输出。1.3算法的表示方法（课本P8-9）1算法的表示方法：自然语言、流程图、伪代码u 自

4、然语言：通过文字或数学表达式来描述解决问题的过程。（缺点：容易产生二义性。）主要格式：(1)(2)(3)(4)u 流程图：用直观易懂的、图形来描述算法的方法。最基本、常用的符号有：处理框：框中指出要处理的内容，该框有一个入口和一个出口。输入、输出框：用来表示数据的输入或计算结果的输出。判断框：用来表示条件判断的情况，菱形框的四个顶点中，通常用上方的顶点表示入口，用另外三个顶点中两个来表示出口。所以对于判断框而言是一个入口，两个出口。连接框：用于连接因画不下而断开的流程线。流程线：指出流程控制方向，即运作的次序。开始、结束符：用来表示算法的开始或结束。一个算法只能有一个开始处，只能有一个结束处。

5、（书上说一个算法只能有一个开始处，但可以有多个结束处。这样的说法是错误的。要更正）流程图表示u 伪代码：介于自然语言和计算机程序语言之间的一种算法描述，也是专业软件开发人员描述算法的一种常用方法。输入：read（）输出：write（），print（）赋值：1.3.2变量与表达式与2.3.1数组（变量与常量的概念参见学科要求P46，课本P9）常量：指在程序执行过程中事先设置、其值不发生改变的量，即一个具体的数值。 变量：指在程序运行过程中，取值可以改变的量，一般用字母表示。在计算机内部变量对应了一定的存储单元。 变量命名的基本规则1.只能由字母、数字和下划线三类字符组成，但第一个字符必须是字母。

6、变量名不能为程序设计语言中的保留字（关键词）。2.字母大小写都可以，变量名长度适当。3.变量名与实际意义相符变量的特点：变量的值“取之不尽，一冲就丢”。变量赋值的格式：变量表达式将赋值号右边常量的值或变量的值存放到左边变量名对应的存储单元中，成为左边变量的值。表达式：指用运算符将常量、变量连接起来有意义的式子。课本P59-60 · 算术表达式：用算术运算符将常量、变量连接起来有意义的式子。课本P59· 字符表达式:用字符运算符将常量、变量连接起来有意义的式子。（优先级数值大于算术表达式，也就是先做算术表达式，再做字符表达式）+：只能是两个字符串间连接如，“123”+“589

7、”=“123589”&：可以是字符串与另一种类型的数据相连接 如，“123”&589=“123589”（优先级数值大于算术表达式，也就是先做算术表达式，再做字符表达式）如，2×3 & “23”=623注意在VB中使用&符号时，一定要在&的前面和后面加上空格。· 关系表达式：用关系运算符将常量、变量连接起来有意义的式子。（课本P59）字符大小比较的实质是其对应以ASCII码大大小。因此字母排列在前的小，排列在后的大，例如:”a”>”b”,”m”>”g”.对于多个字母组成的字符串比较大小，则是首先比较首字母，只有在首字母相同的

8、情况下，才比较第2个字母的大小，依此类推。例如：”abc”>”abb”,”dog”<”dogs”。P33.· 逻辑表达式（课本P60）注意：VB中使用算术运算符运算的结果是数值；使用字符运算符运算的结果是字符串；使用关系运算符和逻辑运算符运算的结果是逻辑值，即：要么是False，要么是True。Ø VB中常用数学函数（课本P84）重点掌握前三个。需要理解课本P84 中：的表示exp(log(a)*b) 和 的表示 log（b）/log（a）Ø VB中常用类型转换函数和字符串函数P85函数名函数的功能说明应用举例函数返回值Asc(x)字符转换为ASCII

9、码值Asc(“A”)65Chr(x)ASCII码值转换为字符Chr(65)“A”Val(x)数字字符串转换为数值Val(“-1234”)-1234Str(x)数值转换为字符串Str(-1234)“-1234”Len(x)计算字符串的长度Len(“hello”)5Mid(x,n,k)从字符串x中的第n个字符起截取长度为k的子串Mid(“hello”,3,3)“llo”Fix(x)截掉数据的小数部分Fix(3.1415926)3计数器：（课本P10，学科要求P58）在算法执行过程中，用来记录某种事件发生次数的变量。一般用法：在算法准备阶段中，应预置初值为0。即c=0在算法执行过程中，每当指定的事件

10、发生时，计数器计数，即把事件已发生的次数（计数器中的值）加1后，结果仍然送回计数器中。即c=c+1.累加器：（课本P11，学科要求P59）用来生成并存储数据累加的变量。一般用法：在求和开始前的准备阶段中，应预置初值0，即sum=0 在算法执行过程中，每遇到一个符合要求的数据时，把这个数据累加到累加器中，即计算累加器与数据之和，并把结果重新存储到累加器中。即sum=sum+a累乘与累加的操作相似。（学科要求P59）一般用法是：在求积开始前的准备阶段中，应预置初值1，即s=1算法执行过程中，每遇到一个符合要求的数据时，把这个数据累乘到累乘器中，即计算累乘器与数据之积，并把结果重新存储到累乘器中。即

11、s=s*d.循环变量：用于控制循环的变量。数组（学科要求P79-80，课本P27）特殊、有用的变量。规模为n的数组变量是由n个普通变量组成的，通常把组成数组的变量称为数组元素，一个数组变量中的所有元素拥有一个共同的名称，通过下标（一个从1n范围内的整数值）指出数组变量中的特定元素。实际上，下标指出了一个数组元素在数组变量中的位置。通常用数组变量来存储一批类型、作用相同的数据。1.3.3算法的执行流程算法中各个处理步骤的执行次序和模式。· 顺序模式（顺序结构）特点： 执行完一个处理步骤（step1）后，顺序执行下一个处理步骤step2。 一个入口，一个出口· 选择模式（分支结

12、构） 特点： 对某种情况e进行判断，当结果为真时，执行处理步骤step1，否则执行处理步骤step2。双分支结构单分支结构VBIf 条件 Then Step1(即条件为真时的语句)Else Step2(即条件为假的语句)End If注意：在这个结构中通过Els就已说明了是条件成立的情况，所以就不需要再对条件进行判断了。VBIf 条件 Then Step1(即条件为真时的语句)End If注意：若结构图中出现的是：当条件为假时执行语句，那么在写VB时，需要把条件换成相反意思。· 重复模式（循环结构）对某个条件进行判断，当结果为真时，执行一些语句，然后再次判断这个条件，当结果仍为真时，再

13、次执行一些语句，并继续判断条件。总是重复上述过程，直到情况判断的结果为假。当型循环结构：直到型循环结构1）先判断，后执行循环体2）循环体执行的循环次数可能是0次或多次VB:Do while 循环条件 循环体（即当循环条件为真时执行）Loop后续步骤（即，当循环条件为假时，也就是出口连接着的步骤，写在这里）注意：若结构图中出现的是：当条件为假时执行循环体，那么在写VB时，需要把循环条件换成相反意思。1）先执行循环体，后判断2）循环体执行的循环次数至少是1次或多次VB：（把结构改成当型循环结构）循环体（第一遍）Do while 此结构图中循环条件相反意思 循环体（即当循环条件为真时执行）LoopV

14、B：（直到型循环结构语句）Do 循环体（即当循环条件为假时执行）Loop Until 此结构图中循环条件每个算法都是这三种模式（结构）的任意组合。控制循环的几种常用方法（学科要求P57）1）计数法：一般用于在循环次数确定的情况下。采用一个变量，通过对该变量的计数来控制循环的次数。当达到要求的循环次数后适时地退出循环，这样的变量称为循环变量。循环变量的初值、终值和步长的设定与循环次数相关。有时，循环变量还参与其他运算。通常使用计数器来记录循环体执行次数并控制循环执行情况。2）标志法：对于不确定循环次数的算法，往往用设置标志性条件的方法来控制循环。² 设置标志性条件的方法通常有：以循环体

15、中某个或几个变量满足规定条件作为循环结束的标志；² 以输入某个特殊的数据作为结束循环的标志。循环结构中容易出现的问题（学科要求P57-58）死循环；随意改变循环体中各操作的执行次序。分析循环结构的算法的运行结果（学科要求P56）列表法；功能分析法。三种模式的应用。（学科要求P59-73）基本算法实例2.1解析算法（课本P18，学科要求P79）用解析的方法找出表示问题的前提条件与结果之间关系的数学表达式，并通过表达式的计算来实现问题求解。解析算法最关键的有两步（1）确定使用哪种执行流程来完成。 （解析算法的结构：可能是顺序结构（课本例1），也可能是顺序结构和分支结构的组合（例2），也可

16、能是顺序结构和循环结构的组合（例3），也可以是三种结构的任意组合；这完全取决于问题本身。）（2）确定条件与结果之间的表达式。解析法的特点 解析法的应用 解析法的实现2.2枚举算法（课本P22，学科要求P75-79）采用一种盲目的搜索方法，在搜索结果的过程中，把各种可能的情况都考虑到，并对所得的结果逐一进行判断，过滤掉那些不合要求的，保留那些符合要求的，这种方法叫做枚举算法。在列举过程中，既不能遗漏，也不应该重复。 基本结构：枚举算法最关键的有三步（1）确定列举的范围。（2）确定满足筛选的条件。（3）确定循环控制方式和列举方式枚举法的特点 枚举法的应用 枚举法的实现注意：枚举算法的优缺点（学科要

17、求P77）：枚举法充分利用了计算机快速高效的特点，让计算机将所有可能的解无一例外地进行检验，因此列举正确，枚举法具有非常高准确性和全面性；也决定了其局限性-效率不高。当算法花费的时间过长时，这样的枚举算法是没有实际意义的。2.4查找（课本P34）一种查询数据或信息的技术，其目标是能以比较少的步骤或较短的时间找到所需的对象。在课本中是指以在程序的某个数组变量中存储的一批数据内，寻找出特定的一个数据，或者确定在该数组内无这样的数据，来作为查找的目的。查找方法很多，除了顺序查找、对分查找，还有树形查找等等。Ø 顺序查找（课本P34，学科要求P81）用待查关键字（查找键）和已知的数据逐个比较

18、，直到找到与查找键值相等的值，即查找成功；或查完全部已知数据，而未找到查找键字相等的值，即为查找失败。顺序查找的原理 顺序查找的算法(课本P35+课堂上对其修改，学科要求P81) 顺序查找的实现Ø 对分查找（课本P35，学科要求P81）在有序数据中，采用查找键与有序数据内处于中间位置的元素进行比较，如果中间位置上的元素的数值与查找键不同，根据数据元素的有序性，就可以确定应该在数组的前半部分还是后半部分继续进行查找；在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。对分查找的原理 对分查找的算法(课本P35+课堂上对其修改) 对分查找的实现2.3排序（课本P29，学科要求P8

19、0）把杂乱无章的数据变成有序（递增/递减）数据的过程。Ø 冒泡排序把待排序的n个元素的数组看成是垂直堆放的一列数据。从最下面的一个元素起，自下而上比较相邻的两个元素中的数据，将数值最小的数据换到上面的一个元素中。重复这一过程，直到处理完最后两个元素中的数据，称为一遍加工。当第一遍加工完成时，最小的数据已经上升到第一个元素的位置。然后对余下的n-1个元素重复上述处理过程，直至最后进行余下两个数据的比较和交换。冒泡排序的原理 冒泡排序的算法（课本P32+课堂上的整理） 冒泡排序的实现Ø 【选择排序】是在参加排序的所有数组元素中找出最小（或最大）数据的元素，使它与第一个元素中的数据相互交换位置，然后再在余下的元素中找出最小（或最大）数据的元素，与第二个元素中的数据相互交换位置，以此类推，直到所有元素成为一个有序的序列。】（仅作参考）程序设计基础VB（Visual Basic)：Windows环境下广泛使用的一种应用程序开发工具，采用面向对象的程序设计方法。它是一种可视化的程序设计工具，能用它来开发具有图