高一信息科技算法与程序设计复习.doc

信息科技算法与程序设计复习一、常见的运算运算符的优先级别：1. 先算术，后关系，再逻辑，括号改变顺序2. 算术运算：先乘幂，后取负，再乘除，整除余，末加减3. 逻辑运算：先非，后与，再或常用函数：取整函数int（）、求算术平方根函数sqr（）、求绝对值函数abs（）类别运算符运算结果优先级算术运算符+、-、*（乘）、/（除）、（乘方）、mod（求余）数值关系运算符、=、=、=、True（T，1）或False（F，0）逻辑运算符not、and、orTrue（T，1）或False（F，0）notandor逻辑运算规则ABA and BA or BCNot CTTTTTFTFFTFTFTFTFFFF习题：（1）13 or not -1=1 T（2）ab or 5=2*4 T（3）假设变量a的值是1，变量b的值是2，变量c的值是3，计算下列表达式的值。a3+b*c 7c mod b +a2int(c/b) b-aFa0Ta+bc or b+ca and c+abT二、算法的一些概念1用计算机解决问题的步骤：分析问题设计算法编写程序运行程序2. 计算机程序是指示计算机如何去解决问题或完成任务的一组可执行的指令。指令是依次逐条执行的。程序的组成部分：指令部分、数据部分3. 内存中每个存储单元都有唯一的编号，成为地址。4. 算法的定义：为解决某一问题设计的确定的有限的步骤。5算法的描述：自然语言、流程图描述、伪代码。6. 算法的特点：有穷性、确定性、可行性、有0个或多个输入（可以没有输入）、有一个或多个输出（至少有一个输出）7. 算法的流程图表示： 8常量和变量：常量：在程序执行过程中事先设置、其值不发生改变的量。变量：在程序执行过程中，用来存放数据的存储单元。读取变量的值不会改变其存放的值，但当有新的数据存放进去会覆盖其原来存放的值。1）每个变量都有一个名字作为标记，不同程序设计语言对变量的命名规则不相同。2）从变量中读取数据后，变量的值不发生改变。3）变量的赋值：a = 2 或 a 24）变量赋值的特点：取之不尽，一冲就丢5）变量的命名规则：以字母、数字、下划线组成，必须以字母开头。常用变量的类型：整数型（Integer）、长整型（Long）、单精度实数型（Single）、双精度实数型（Double）、字符串型（String）9. 计数器：在算法执行过程中，用来记录某种事件发生次数的变量。1）计数器的初值通常为0，i = 02）在循环体中的计数语句，如：i = i + 110. 累加器：在算法执行过程中，用来生成并存储数据累加和的变量。1）累加器的初值通常为0 , s = 02）在循环体中的累加语句，如：s = s + a11. 累乘器：在算法执行过程中，用来生成并存储数据累乘积的变量。1）累乘器的初值通常为1, s = 12）在循环体中的累乘语句，如：s = s * a10算法的三种基本结构：顺序结构、分支结构、循环结构三、算法基本模式（一）顺序结构（顺序模式）顺序结构按照自上而下的顺序把每个步骤执行一次。练习1：输入一个圆的半径，求圆的周长和面积，并输出结果。代码：Dim r As Singler = InputBox(输入半径)s = 3.14 * r 2c = 2 * 3.14 * rPrint 周长; cPrint 面积; s练习2：输入一个两位数，交换个位和十位的值，输出结果。代码：x = InputBox(请输入)a = Int(x / 10)b = x Mod 10y = 10 * b + aPrint y练习3：输入两个变量的值，将两个变量中的值互相交换并输出结果。 代码：Dim a As Single, Dim b As Singlea = InputBox(第一个数)b = InputBox(第二个数)c = aa = bb = cPrint a; b（二）分支结构（选择模式）分支结构根据条件决定执行步骤1或步骤2中的算法步骤，判断框有一个入口两个出口，分支结构有一个入口，一个出口。单分支语句格式If Then If Then End If双分支语句格式If Then Else End If 练习1：输入两个数，比较它们的大小，输出较大的数。代码：Dim a As SingleDim b As Singlea = InputBox(请输入)b = InputBox(请输入)If a b Then Print aElse Print bEnd If练习2：输入一个三位数，判断它是否是水仙花数(三位数各个数位上的立方和等于它本身)。代码：Dim n As Singlen = InputBox(输入一个三位数)a = Int(n / 100)b = Int(n / 10) - a * 10c = n Mod 10If a 3 + b 3 + c 3 = n Then Print 是水仙花数Else Print 不是水仙花数End If 练习3：输入一个数，求它的绝对值，并输出结果。代码：Dim a As Singlea = InputBox(请输入)If a 0 Then a = -aEnd IfPrint a练习4：阶梯电价第一档第二档第三档方案1每月用电210度电价维持现有电价超出部分上涨不低于5分钱超出部分每度涨价不低于0.20元Dim x As Singlex = InputBox(输入用电)If x 110 Then y = 0.61 * xElseIf x = 210 Then y = 0.61 * 110 + 0.66 * (x - 110) Else y = 0.61 * 110 + 0.66 * 100 + 0.81 * (x - 210)End IfPrint 电费; y练习5：购买地铁车票：乘1-4站3元/位，5-9站4元/位，9站以上5元/位，输入站数和人数，输出应付款。Dim a,b,m as integera = inputbox(“请输入站台数：”)b = inputbox(“请输入人数：”)If a=4 thenm=3*bElseIf a=9 then m=4*bElse m=5*bEnd IfPrint m练习6：长江遂桥货车通行费收费标准（载重用w表示,收费用m表示）Dim w As Singlew = InputBox(输入载重)If w 2 And w 5 And w 10 And w 15 Thenm = 145End IfPrint 应付款, m（三）循环结构（重复结构）当循环的一般形式直到循环的一般形式当遇到需要重复执行的操作时，可以用循环结构，循环结构有一个入口，一个出口。Do while 条件 循环体语句LoopFor 循环变量=初值 to 终值 步长 循环体语句Next 循环变量Do 循环体语句Loop while 条件当循环和直到循环的区别：当循环的循环体可能一次也不执行，直到循环的循环体至少执行一次。1输出系列问题n = 0Do While n 5 Print * n = n + 1Loop练习1：输出5个*练习2：输出1，2，3，4，5方法一：用次数来控制循环方法二：用输出的数字来控制循环a = 1Do While a =5 Print a a = a + 1Loop练习3：输出21，22，23，24，25的值方法一：把a当成整个数方法二：把a当指数2求和系列问题练习1：求1+2+3+4+5的和 练习2：求1+3+5+7+9的和 练习3：求21+22+23+24+25的和 练习4： 求12+23+34+45+56的和。练习5：求1+2+3+k的和，其中k由键盘输入。练习6：求1*2*3*4*5的积练习7：求1+2+3+加到第几项和超过5？方法一：用i来计算项数方法二练习8：求输入的5个数的平均值（如70，60，80，50，90）Dim a As Singles = 0n = 0Do While n = 5练习2：求1+2+4+7+11的和s = 0a = 1n = 1Do s = s + a a = a + n n = n + 1Loop while n 5Print s 5数组：数组是一种特殊的变量，它在内存中的位置是连续的，用于存储一批类型、作用相同的数据。数组元素的下标可以是常量也可以是变量，也可以是一个表达式，可以从0开始，数组元素可以参与运算，和普通的变量一样。Dim d(10) As Singlen = 1Do While n = 1 Print a(n) n = n - 1Loop练习1：输入10个数，再将其逆序输出。算法实例复习一、解析法1.解析法概念：根据题目中给出的已知条件，找出已知条件与要求的结果之间的关系的数学表达式，并通过计算表达式来实现问题求解的方法。2.解析法算法实例（1）输入直角坐标系中两点坐标，计算两点间距离，并输出结果。Dim x1 As Integer, y1 As Integer,Dim x2 As Integer, y2 As Integerx1 = InputBox(x1:)y1 = InputBox(y1:)x2 = InputBox(x2:)y2 = InputBox(y2:)d = Sqr(x1 - x2) 2 + (y1 - y2) 2)print dPrint d=; d（2）输入圆半径，计算圆面积和周长，并输出结果。Dim r As IntegerDim s As Single, c As Singler = InputBox(请输入半径值:)s = 3.14 * r * rc = 2 * 3.14 * rPrint 圆面积为; sPrint 圆周长为; c（3）输入人民币金额，计算兑换后的美元金额并输出。（假定汇率为6.83）Dim rmb As IntegerDim usd As Singlermb = InputBox(请输入人民币金额:)usd = rmb / 6.83Print 可以兑换美元金额为; usd二、枚举法1 枚举算法的概念列出各种可能的情况并逐一进行检验，根据检验的结果执行相应的操作。“枚”就是一个一个；“举”就是列举。核心：不遗漏不重复。枚举算法充分利用了计算机“运行速度快、不知疲倦”的优势。2枚举算法的结构特点l 列举由循环结构实现l 检验由分支结构实现因此，枚举算法的一般结构是：循环结构中嵌套分支结构。3枚举算法的设计步骤l 确定列举的范围不能随意扩大和缩小范围，否则会造成重复或漏解。l 明确检验的条件根据检验的对象来设定条件，以及检验后所执行的相关操作。l 确定循环控制的方式和列举的方式借助循环变量的变化来列举。4.枚举算法实例通过输入的数据作为检验的对象。（1）输入10个数，分别统计正数和负数的个数（2）输入5个成绩，统计其中100分的人数 这两个问题也采用了枚举算法的思想，从结构上看，都是循环结构嵌套分支结构。所检验的对象是通过键盘输入的数据。Dim x As SingleDim i, n,m As Integeri = 1n = 0m=0Do While i 0 Then n = n + 1ElseIf x0 Then m=m+1End If i = i + 1LoopPrint n,mDim mark As SingleDim i, n As Integeri = 1n = 0Do While i = 5 mark = InputBox(请输入成绩：) If mark = 100 Then n = n + 1 End If i = i + 1LoopPrint n通过循环变量的变化来作为检验的对象。 以下6个实例是不需要输入语句的，因为检验的对象正好包含循环变量的变化。（1）打印出1-1000以内能同时被7和11整除的自然数。（变量 n 表示这个自然数，列举范围从11000）Dim n As Integern = 1Do While n = 1000 If n Mod 7 = 0 And n Mod 11 = 0 Then Print n End Ifn = n + 1Loop（2）找水仙花数：一个三位数，各个位置上的数字的立方和等于该数本身（变量 n 表示这个三位数，列举范围从100999）Dim n As Integern = 100Do While n = 999 a = Int(n / 100) b = (n - 100 * a) 10 c = n - 100 * a - 10 * b If a 3 + b 3 + c 3 = n Then Print n End Ifn = n + 1Loop（3）鸡兔同笼：20只头，56只脚，问鸡、兔各有几只？（变量 x 表示鸡的个数，列举范围从120）Dim x As Integerx = 1Do While x = 19 If 2 * x + (20 - x) * 4 = 56 Then Print 鸡有：; x, 兔有：; 20 - x End Ifx = x + 1Loop（4）涂抹单据：一张单据上的5位数号码，千位和百位数字已经模糊不清 “1XX47” ，但这个5位数是57或67的倍数。（变量 x 表示这个两位数，列举范围从099）Dim n As Intege, x As Integerx = 0Do While x = 99 If (10047 + 100 * x) Mod 57 = 0 Or (10047 + 100 * x) Mod 67 = 0 Then Print x End Ifx = x + 1Loop（5）包装600个变形金刚，小盒每盒12个，大盒每盒15个。盒数都不能为0。输出所有可能的包装方案。（变量 s 表示小盒子的数量，列举范围从150，不包括50）Dim s As Integers = 1Do While s 50 If (600 - 12 * s) Mod 15 = 0 Then Print 小盒：; s, 大盒：; (600 - 12 * s) / 15 End Ifs = s + 1Loop（6）等式成立：34*856 = 43*658 使等式成立的数字是什么？（变量 n表示这个数，列举的范围从09）Dim x As Integern = 0Do While n = 9 If 34 * (8056 + 100 * n) = 43 * (6508 + 10 * n) Then Print 使等式成立的数字是：; n End Ifn = n + 1Loop三、数组 数组是一种特殊的变量，它在内存中的位置是连续的，利用数组中各个元素下标的连续性的特点，可以采用循环结构对各个元素进行赋值或运算。【实例】数组的输入与逆序输出Dim i As IntegerDim d(1 To 5) As Singlei = 1Do While i = 1 Print d( i ) i = i - 1Loop四、查找（1）顺序查找的算法思想：从数组的第一个元素开始，依次往下查找，若找到，输出该数组元素的下标值并结束；若找遍所有元素没有找到，则输出0,并结束。（2）对分查找的算法思想：先取数组中间位置上的元素和关键字比较，若不相等则缩小近一半的查找范围，在剩下的元素中再取中间位置上的元素和关键字比较，若不相等则缩小近一半的查找范围，继续查找，以此类推，若找到，输出该数组元素的下标值并结束；若找遍所有元素没有找到，则输出0,并结束。由于对分查找每查找一次，查找范围就缩小一半，因此对分查找的效率要远高于顺序查找，但它的前提是：待查找的数据必须是有序的。例如：顺序查找6288例如：对分查找22五、排序1、冒泡排序：l 从最下面一个元素起，自下而上地比较相邻两个元素中的数据，将较小的数值交换到上面一个元素。重复这一过程，直到处理完最后两个元素中的数据，称为一遍加工。此时，最小的数据已经上升到第一个元素的位置。l 然后对余下的i-1个元素重复上述过程。l 由于每一遍加工都是将最小的元素像气泡一样浮至顶端，故称为冒泡排序。例如：有4个数据：18，15，2，9，按照从小到大的顺序排列，过程如下：原始数据181529第一遍218159第二遍291815第三遍291518i = 1Do While i i If d(j) d(j - 1) Then t = d(j) d(j) = d(j - 1) d(j - 1) = t End If j = j - 1 Loop i = i + 1Loop分支结构的实现语句单分支:if 条件 then语句组end if双分支:if 条件 then 语句组Aelse 语句组Bend if分支嵌套：if 条件 then 语句组AelseIf 语句组Belse语句组Cend if循环结构的实现语句当型循环:do while 循环条件循环体语句组loop直到型循环:do 循环体语句组loop while 循环条件计数循环for循环语句代码for 循环变量=初值 to 终值 step 步长 循环体语句next 循环变量