信息科技复习之程序设计篇.doc

算法与程序设计1算法：为解决某一问题设计的确定的有限的步骤。2算法的主要特征：有穷性、确定性、可行性、有0个或多个输入、有一个或多个输入。3算法的描述方法：自然语言，流程图，程序或位代码。4. 用计算机解决问题的一般过程：分析问题设计算法编写程序上机调试和维护5流程图符号：起止框 输入输出框 处理框 判断框 流程线6常量：在程序执行过程中事先设置、其值不发生改变的量。7变量：在程序执行过程中，取值可以改变的量，对应计算机内部的存储单元。（1）每个变量都有一个名字作为标记，不同程序设计语言对变量的命名规则各不相同。基本命名规则：只能由字母、数字和下划线三类字符组成，但第一个字符必须是字母，字母大小写都可以。变量名长度适当，要有意义。（2）从变量中读取数据后，变量的值不发生改变。（3）变量赋值：将赋值号右边常量的值或变量的值，或表达式的结果存放在左边变量名对应的存储单元中，成为左边变量的值。例：（注意“=” 是赋值号）n 变量=常量 例如：a=3n 变量=变量 例如：b=an 变量=表达式 例如：c=2*a+b （4）变量赋值的特点：取之不尽，赋值即覆盖（5）变量的定义：Dim As ， As 类型名 中文名 取值范围 Single 单精度实数 10-451038 Integer 整数 -3276832767 String 字符串 一段文字与符号 例：name=“Liming” 8运算符类别运算符运算结果优先级算术运算符+ 、-、* 、/、mod数值* /mod+ -关系运算符、=、=、=、True或False相同逻辑运算符not、and、orTrue或FalseNotandor9三类运算符的优先级：算术运算符关系运算符逻辑运算符10. 常用数学函数：Int(x) 取整运算,求不大于x的最大整数Sqr(x) 求x的算术平方根Abs(x) 求x的绝对值11主要函数：取整函数Int（）、求算术平方根函数sqr（）、求绝对值函数abs（）12算法的三种结构：顺序结构、分支结构、循环结构。顺序结构双分支结构单分支结构当型循环结构直到型循环结构顺序结构13.判断框一个入口、两个出口；分支结构一个入口、一个出口。14循环结构中要注意：循环初始状态、循环体、循环条件。15计数器：在算法执行过程中，用来记录某种事件发生次数的变量。（1）计数器的初值通常为0（2）在循环体中的计数语句i = i + 116. 累加器：在算法执行过程中，用来生成并存储数据累加和的变量。（1）累加器的初值通常为0（2）在循环体中的累加语句s = s + a17累乘器：在算法执行过程中，用来生成并存储数据累乘积的变量。（1）累乘器的初值通常为1（2）在循环体中的累乘语句s = s * a18解析算法：用解析的方法找出表示问题的前提条件与结果之间关系的数学表达式，并通过表达式的计算来实现问题求解。【解析算法实例】输入已知三角形三条边的长a、b、c，利用海伦公式求三角形面积。input a, b, c s = (a + b + c) / 2 x = Sqr(s * (s - a) * (s - b) * (s - c) Print x19枚举算法：列出各种可能的情况并逐一进行检验，根据检验的结果执行相应的操作。“枚”就是一个一个；“举”就是列举。核心：不遗漏不重复。枚举算法充分利用了计算机“运行速度快、不知疲倦”的优势。（1）结构特点：循环中嵌套分支结构l列举由循环结构实现l检验由分支结构实现（2）设计步骤1）确定列举的范围：不能随意扩大和缩小范围，否则会造成重复或漏解2）明确检验的条件：根据检验的对象来设定条件，以及检验后所执行的相关操作。3）确定循环控制的方式和列举的方式：借助循环变量的变化来列举，或通过输入。 x = 100 Do While x = 999 a = Int(x / 100) b = Int(x Mod 100) / 10) c = x Mod 10 If a 3 + b 3 + c 3 = x Then Print x , End If x = x + 1Loop【枚举算法实例】若一个三位数x=100*a+10*b+c（a、b、c都是个位数），满足a3+b3+c3=x，则x称为水仙花数。找出三位数中所有的水仙花数。20数组：一种特殊的变量，在内存中的位置是连续的，用于存储一批类型、作用相同的数据。几个相关概念：数组名、数组元素、数组元素名、数组元素下标、数组元素值。Dim d(10) For i = 1 to 10 Input a d(i) = a next i for i = 10 to 1 step -1 Print d(i) Next i【数组实例】输入10个数字，依次存放到数组中，再将其逆序输出。21冒泡排序的算法思想(由右向左依次比较，这种考的比较多)（1）从最下面一个元素起，自下而上地比较相邻两个元素中的数据，将较小的数值交换到上面一个元素。重复这一过程，直到处理完最后两个元素中的数据，称为一遍加工。此时，最小的数据已经上升到第一个元素的位置。（2）然后对余下的i-1个元素重复上述过程。（3）由于每一遍加工都是将最小的元素像气泡一样浮至顶端，故称为冒泡排序。例：有一组数据23、61、24、15、89，问第二轮冒泡的第一次交换后数据排序的结果如何？冒泡过程：原始数据2361241589第一轮冒泡（交换3次）1589152489156124891523612489第二轮冒泡（第1次交换）2489246189答：第二轮冒泡的第一次交换后数据排序结果为15、23、24、61、8922选择排序的算法思想（找最值擂台法）（1）从第一个元素起，自上而下找出最小数，并记录下它的位置，将最小数交换到第一个元素中。完成第一遍加工。（2）然后对余下的i-1个元素重复上述过程。（3）在每一遍加工中，只需交换一次位置即可上例中的这组数据23、61、24、15、89，用选择排序的过程如下：原始数据2361241589第一遍加工1561242389第二遍加工1523246189冒泡排序与选择排序的比较选择排序实际上是一种优化了的排序方法，它和冒泡排序的区别在于减少了交换的次数，在每一遍的加工过程中，选择排序采用的方法是通过遍历，记录下最值的位置，最后再将最值所在位置的数据与待排元素所在的位置进行交换，因此每一遍加工只需交换依次位置。大大减少了算法的复杂度。23擂台法实例：已知数组d中已经存放了10个数，输出其中的最大值（1）先假设d1中的数值是最大值，令k d1 。（2）用d2与k比较，若d2大，则令k d2，否则继续比较，直至d1024顺序查找的算法思想：按照数组元素的先后次序，从第一个元素开始遍历，逐个检验是否和查找的数据相等。（枚举算法）例：在包含10个数字的数组中顺序查找一个符合要求的数。25对分查找的算法思想：先取数组中间的元素和关键字比较，若不相等则缩小近一半的查找范围，在剩下的元素中继续查找。由于对分查找每查找一次，查找范围就缩小一半，因此对分查找的效率要远高