算法与程序设计知识要点.doc

信息技术（选修1）算法与程序设计知识要点1、 设计程序利用计算机解决问题的过程（步骤）（教材第6页，以下记为P6）：具体问题分析问题设计算法编写程序调试程序得到答案2、 算法：是在有限步骤内求解某一问题所使用的一组定义明确的规则（通俗地说，就是用计算机求解某一问题的方法，是能被机械地执行的动作或指令的有穷集合）。（P8）3、 算法的特征：1）输入、2）确定性、3）有穷性、4）输出、5）能行性。（P9）4、 算法的描述：1）用自然语言描述算法（掌握），2）用流程图描述算法（重点、考点），3）用伪代码描述算法（不考）。（P9P12）5、 程序的基本结构：任何复杂的算法都可以用顺序结构、选择结构、循环结构三种基本结构组合而成的程序表示。这三种结构称为程序的三种基本控制结构。（P16P17）S1S2S3顺序结构CS1S2选择结构S1C循环结构是是否否注：S表示执行语句（或某个步骤），C表示条件（判断该条件是否能满足）6、 程序设计语言的产生与发展（P18P19） 机器语言：由“0”和“1”这样的二进制代码指令组表示的，是能够被计算机直接接受和执行的计算机语言。（这是早期程序设计语言，机器语言程序难以理解） 汇编语言：使用类英语缩略词且带有助记性符号的语言。（每条汇编指令都和一条机器指令相对应，只是指令码和操作数都采用符号形式。）（这种语言与特定的机器和特定的微处理器有关，且不能被机器直接接受，必须用一种语言翻译器将程序的每条语句翻译成机器语言才能执行。） 高级语言：更接近自然语言的计算机语言。（简单、易于理解、需要翻译、程序源代码与硬件和操作系统底层无关，在不同硬件和操作系统间移植性更好）。7、 Visual Basic（简称VB）语言：是Windows环境下快速开发应用程序的可视化工具。（P26）使用VB编写的程序可被翻译生成为32位的、可脱离VB开发环境而直接执行的应用程序（即二进制的机器语言程序）。使用VB编程的理念：面向对象和事件驱动（即程序设计者编写的程序代码只有在针对某个对象的某个事件发生时才启动）。例下表所示： 对象事件启动的代码块窗体激活Private Sub Form_Load()End Sub按钮（假设名称为Command1）单击Private Sub Command1_Click()End Sub注：省略号处是由程序员编写的，代码块启动时将要执行的那部分程序代码。8、 VB程序一般包括：1）数据类型说明部分、2）数据的输入部分、3）数据的处理部分、4）数据的输出部分。（P26）9、 数据：描述客观事物的数、字符以及所有能输入到计算机中，并被计算机加工处理的符号的集合。数据既是计算机程序处理的对象，也可以是运算产生的结果。（P26）10、 数据类型：设定用于存储某种数据的内存空间的大小。（P27）11、 常量：在程序运行过程中始终保持不变的常数、字符串等。如：3.14，”r=”等。在程序设计中，对于一些经常使用的常量，可以用常量说明语句来定义，以提高程序的可读性和可维护性。（P27）常量说明语句的格式： Const 常量名 As 类型=表达式 例如： Const PAI As Double=3.1415912、 变量：命名的存储单元位置，用于在程序处理数据时，暂时存储输入的数据、参数运算的数据、运算结果等临时数据。在VB中，变量名必须由英文字母开头，后面则可以由字母、数字或其它符号组成。变量名称最好用与它所表示的内容意义相同的英文单词来确定。13、 变量说明：在使用变量前，一般应先说明变量名及其类型，以使系统为其分配存储单元。（P28）变量说明语句的格式： Dim 变量 As 类型 例如： Dim StudentNumber As Integer Dim Score As Single Dim Length As Double Dim Name As String14、 函数：预先编写好的、可以在正式编写程序时调用的、具有一定功能的程序模块。在程序中要调用一个函数时，只需给出函数名和一个或多个参数，就能得到函数值。（P28P29）调用函数的格式： 函数名（参数表） 例如： SIN（90*3.14/180） COS（1.57） 注意：1）参数表应置于小括弧中；2）若有多个参数，应用英文逗号隔开；3）参数可以是常量、变量或表达式提示：打的函数是必须掌握其用法的函数！补充：Val（ ）函数可以把以数字为内容的字符串转换为双精度实数型数据，比如使用Val（”123”）得到的结果是123。15、 运算符：描述各种不同运算的符号称为运算符，而参与运算的数据称为操作数。VB中常用运算符有：） 算术运算符：加+、减、乘*、除/、乘方、整除、取余数MOD；括号（ ）用于决定运算顺序，只用小括号，可以多层嵌套。） 字符串运算符：连接字符串& ，如：”abc” & ”de” 可得 “abcde”） 关系运算符：大于、小于=、小于等于=、不等于，用于比较两边表达式之间的关系，把两边表达式连接起来，构成关系表达式（也就是自然语言中所说的条件）。若表达式与实际情况符合，则表达式的值为“真”，也就是说条件成立，若关系表达式与实际情况不符合，则表达式的值为“假”，也就是说条件不成立。） 逻辑运算符：AND、OR、NOT，分别对应逻辑上的与（就是“且”的意思）、或、非（就是“不”的意思），用于连接关系表达式构成逻辑表达式（也就是自然语言中所说的复合条件）。若AND连接的各个关系表达式全都为“真”，则逻辑表达式的值为“真”，也就是说复合条件成立，只要有一个关系表达式的值为“假”，则逻辑表达式的值为“假”，也就是说复合条件不成立；若OR连接的各个关系表达式的值全都为“假”，则逻辑表达式的值为“假”，只要有一个为“真”，则逻辑表达式的值为“真”；若NOT后面的那个关系表达式的值为“真”，则逻辑表达式的值为“假”，反之为“真”。注意：关系表达式和逻辑表达式的值既不是数值型，也不是字符型，而是逻辑型（Boolean）。逻辑型数据只有两个可能的值：真（True）和假（False）。举例：关系表达式9 8的值为“真”，而-1 0 的值是“假”； 逻辑表达式9 8 AND 1 0 的值为“真”，而 3 2 AND 1 2 OR 1 3 OR 1 5的值为“假”； 逻辑表达式NOT 1 5 的值为“真”，而 NOT 1 5的值为“假”；16、 表达式：是指某个求值规则，是由运算符和配对的圆括号将变量、常量、函数等操作数以合理的形式连接起来的式子。（P28） 表达式主要分为：1）算术表达式，即由算术运算符和配对的圆括号将变量、常量等操作数以合理的形式连接起来的式子； 2）函数表达式，即包含函数的表达式； 3）关系表达式，即用关系运算符将两边的表达式连接起来的式子，在自然语言中称为“条件”； 4）逻辑表达式，即用逻辑运算符将关系表达式连接起来的式子，在自然语言中称为“复合条件”；17、 VB开发环境：编写VB程序、翻译VB程序、运行VB程序的软件工具。（P30）18、 赋值语句：将赋值号右边的表达式的值赋给赋值号左边的变量，这样的语句称为赋值语句。（P35） 赋值语句基本格式： 变量 = 表达式 例如： a = 2 b = 3*2 c = SQR（a） d = b2 4*a*c 最严重提醒：在赋值语句中，“=”是赋值号而不是等号，表示左边的变量取得右边表达式的值，绝非左边等于右边！在关系表达式中，“=”的意思才是“相等”。19、 从键盘输入数据：InputBox（）函数。利用它可以产生一个对话框，提示用户输入数据，并得到一串从键盘输入的字符（即：该函数返回值是字符串类型）。（P36）语法格式： InputBox（提示信息，标题，默认值，位置）20、 输出数据到窗体：Print语句（P37）语法格式： Print 输出内容说明：1）输出内容可以是常数、变量、表达式或引号中的字符串； 2）若有多个输出内容，各项内容用逗号或分号隔开，用逗号隔开则按分区格式输出，用分号隔开则按紧凑格式输出； 3）若输出内容后没有标点符号，表示下一个Print语句提行输出； 4）若Print语句没有输出内容，则输入一个空行并提行。例如：Print 1,2,3 结果： 1 2 3 Print 1;2;3 结果： 1 2 3 Print “123” 结果：123 注意：多项输出内容之间不能用冒号分隔！21、 If条件语句：实现（二分支）选择结构的流程控制语句。（P42P44）条件语句格式： If 条件 Then 语句组1 Else 语句组2 格式： If 条件 Then 语句组1 Else 语句组2 End If 说明：1）条件可以是单一条件（即关系表达式）或复合条件（即逻辑表达式）；2）条件成立时，也就是关系表达式或逻辑表达式的值为“真”时，执行语句组1，否则执行语句组2； 3）如果条件不成立时，也就是关系表达式或逻辑表达式的值为“假”时，没有操作，则可省略Else和语句组2； 4）格式又称为行If语句，格式又称为块If语句，前者末尾没有End If子句，而后者末尾必须有End If语句，不能丢掉。（严重注意！） 例程1：从键盘输入圆的半径R，计算并输出圆的周长和面积。 例程2：从键盘输入长方体的长、宽和高，计算并输出表面积和体积。例程3：从键盘输入一元二次方程AX2+BX+C=0的二次项系数A、一次项系数B和常数项C，计算并输出方程的根。例程4 历法规定，若某一年份能被4整除但不能被100整除，或者能被400整除，则这一年是闰年，否则不是。如2000年、2004年、2008年是闰年，1900年、2001年、2010不是闰年。编程输入某个年份Year，判断其是否为闰年。22、 For循环语句：又称计数循环语句，是实现已知循环次数的循环结构的流程控制语句。（P51P52）基本格式：For 循环变量 = 初值 To 终值 Step 步长 语句组（又称循环体） Next 循环变量 说明：1）循环变量为数值型变量； 2）初值、终值和步长均为数值表达式； 3）当初值小于终值时，步长应为正数，当初值大于终值时，步长应为负数；4）如果步长为1，则可省略Step子句； 5）循环次数为（终值初值）/步长+1）的整数部分。 执行过程：1）循环变量赋初值； 2）判断循环变量是否超过终值，超过则退出循环并执行Next后面的语句，没有超过则执行循环体； 3）遇到Next语句，循环变量在原有基础上增加一个步长值，转到2），继续循环。 严重注意：Next语句绝对不能遗失！ 例程5：输出1到10之间的所有自然数。 例程6：输出1到10之间的所有偶数。 例程7：在程序窗口上输出如下图型。* 程序代码 运行结果23、 条件循环语句：是实现条件成立时重复执行特定操作的循环结构的流程控制语句。（在循环次数不易确定而循环得以持续的条件比较明确的情况下，推荐使用条件循环语句。）（P57）（注意：只要求掌握Do While Loop语句。） 基本格式： Do While 条件 语句组（又称循环体） Loop 说明：条件可以是单一条件（即关系表达式）或复合条件（即逻辑表达式）。 执行过程：1）判断条件是否成立；2）当条件成立（也就是关系表达式或逻辑表达式的值为“真”）时，执行循环体中的语句；3）遇到Loop语句，转到1），继续循环；4）当条件不成立（也就是关系表达式或逻辑表达式的值为“假”）时，退出循环并执行Loop后面的语句。严重注意：Loop语句绝对不能遗失！ 例程8：假设我国GDP每年增长7%，请问几年后GDP能够翻一番？24、 解析法：通过分析问题中各要素之间的关系，用最简练的语言或形式化的符号来表达它们的关系，得出解决问题所需要的表达式，然后设计程序求解问题的方法。（P98）解析法所述之表达式，可以是函数表达式，也可以是递推表达式。前面例1、例2和例3是利用函数表达式（如面积、体积和求根公式）编程处理数据的范例，而例8则是利用递推表达式（后一年的GDP是前一年的GDP与（1+增长率）的积）编程处理数据的范例。例9：计算1+2+3+4+100的和并输出 例9中左边程序使用函数表达式，右边程序使用递推表达式，结果一样，但前者效率更高。不过，在难以获得函数表达式的情况下，使用递推式更直观。例8也可以使用函数表达式求解，程序如下： 请注意：VB中函数Log（X）等同于数学中的LnX，因此应使用换底公式先将数学表达式Log1.072化为Ln2/Ln1.07，再重写为VB表达式LOG（X）/LOG（1+0.07）请思考：为什么输出 -Int(-N) 而不是 N ？25、 穷举法：列举一切与命题相关的情况，然后根据问题设定的条件，逐个 加以检查，找到满足条件的解。（P105）注意：在实施穷举时，“与命题相关的情况”所包含的范围可能很广，因此应加以适当的限制，否则会耗费计算机过多的运行时间。例10：若一个三位整数的个位、十位和百位数的立方和与该数相等，则称此数为“水仙花数”。请找出所有水仙花数。算法提示：逐个检查100到999的每个数，发现水仙花数立即输出。注释：a,b,c三个变量分别取得某个三位数i的百位、十位和个位数字。例11：请编程序找出所有能被7777777整除且百万位数字为3的8位正整数。 算法分析：本例左右两个程序采用了不同的穷举算法。左边的算法导致了9千万次循环，使得程序运行了很长时间，效率非常低。而右边的算法仅产生了11次循环（如何算出来的？），使得程序在极短时间内就得出结果，效率很高。另一方面，也必