算法初步复习

1、一、知识结构一、知识结构算法算法程序框图程序框图算法语句算法语句辗转相除法与辗转相除法与更相减损术更相减损术 秦九韶算法秦九韶算法 进位制进位制二、知识梳理二、知识梳理1.1.算法的概念算法的概念 在数学中，按照一定规则解决某一类问题的在数学中，按照一定规则解决某一类问题的明确和有限的步骤称为算法明确和有限的步骤称为算法. . 用程序框、流程线及文字说明来表示算法的图用程序框、流程线及文字说明来表示算法的图形称为程序框图形称为程序框图. .2.2.程序框图的概念程序框图的概念3.3.程序框、流程线的名称与功能程序框、流程线的名称与功能图形符号图形符号 名名 称称 功功 能能 终端框终端框 （起

2、止框）（起止框） 输入、输出输入、输出框框 处理框处理框 （执行框）（执行框） 判断框判断框 流程线流程线 表示一个算法的起始和结束表示一个算法的起始和结束 表示一个算法输入和输出的表示一个算法输入和输出的信息信息 赋值、计算赋值、计算 判断某一条件是否成立，成立时在判断某一条件是否成立，成立时在出口处标明出口处标明“是是”或或“Y”Y”；不成立；不成立时标明时标明“否否”或或“N” N” 连接程序框，表示算法步骤的连接程序框，表示算法步骤的执行顺序执行顺序 4.4.算法的顺序结构算法的顺序结构（1 1）概念：）概念： 由若干个依次执行的步骤组成的逻辑结构，由若干个依次执行的步骤组成的逻辑结构

3、，称为顺序结构称为顺序结构. .（2 2）程序框图：）程序框图：步骤步骤n步骤步骤n+15.5.算法的条件结构算法的条件结构（1 1）概念：）概念： 由若干个在一定条件下才会被执行的步骤组由若干个在一定条件下才会被执行的步骤组成的逻辑结构，称为条件结构成的逻辑结构，称为条件结构. .（2 2）程序框图：）程序框图：满足条件？满足条件？步骤步骤A步骤步骤B是是否否满足条件？满足条件？步骤步骤A是是否否6.6.算法的循环结构算法的循环结构（1 1）概念：）概念： 由按照一定的条件反复执行的某些步骤组成由按照一定的条件反复执行的某些步骤组成的逻辑结构，称为循环结构的逻辑结构，称为循环结构. .（2

4、2）程序框图：）程序框图：循环体循环体满足条件？满足条件？是是否否循环体循环体满足条件？满足条件？是是否否7.7.算法的输入语句算法的输入语句INPUT “INPUT “提示内容提示内容”；变量；变量8.8.算法的输出语句算法的输出语句PRINT “PRINT “提示内容提示内容”；表达式；表达式9.9.算法的赋值语句算法的赋值语句变量变量= =表达式表达式10.10.算法的条件语句算法的条件语句IF IF 条件条件 THENTHEN 语句体语句体END IFEND IFIFIF 条件条件 THENTHEN 语句体语句体1 1ELSEELSE 语句体语句体2 2END IFEND IF满足条件

5、？满足条件？步骤步骤1步骤步骤1是是否否满足条件？满足条件？步骤步骤A是是否否11.11.算法的循环语句算法的循环语句DODO 循环体循环体LOOP UNTILLOOP UNTIL 条件条件满足条件？满足条件？是是循环体循环体否否WHILEWHILE 条件条件 循环体循环体WENDWEND 循环体循环体满足条件？满足条件？是是否否12.12.辗转相除法辗转相除法第一步，给定两个正整数第一步，给定两个正整数m m，n(mn(mn).n).第二步，计算第二步，计算m m除以除以n n所得的余数所得的余数r. r. 第三步，第三步，m=nm=n，n=r.n=r.第四步，若第四步，若r=0r=0，则，

6、则m m，n n的最大公约数等于的最大公约数等于m m；否则，返回第二步否则，返回第二步. . 求两个正整数的最大公约数求两个正整数的最大公约数13.13.更相减损术更相减损术第一步，给定两个正整数第一步，给定两个正整数m m，n(mn(mn).n). 第二步，计算第二步，计算m-nm-n所得的差所得的差k.k. 第三步，比较第三步，比较n n与与k k的大小，其中大者用的大小，其中大者用m m表示，表示，小者用小者用n n表示表示. . 第四步，若第四步，若m=nm=n，则，则m m，n n的最大公约数等于的最大公约数等于m m；否则，返回第二步否则，返回第二步. . 求两个正整数的最大公约

7、数求两个正整数的最大公约数14.14.秦九韶算法秦九韶算法第一步，输入多项式的次数第一步，输入多项式的次数n n，最高次项的系数，最高次项的系数a an n和和x x的值的值. . 第二步，令第二步，令v=av=an n，i=n-1.i=n-1. 第三步，输入第三步，输入i i次项的系数次项的系数a ai i. . 第四步，第四步，v=vx+av=vx+ai i，i=i-1.i=i-1.第五步，判断第五步，判断i0i0是否成立是否成立. .若是，则返回第三步；若是，则返回第三步；否则，输出多项式的值否则，输出多项式的值v. v. 求多项式求多项式f(xf(x)=a)=an nx xn n+a+

8、an-1n-1x xn-1n-1+a+a1 1x+ax+a0 0的值的值第一步，输入第一步，输入a,ka,k和和n n的值；的值；第二步，将第二步，将b b的值初始化为的值初始化为0,i0,i的值初始化为的值初始化为1 1；第三步，第三步，b=b+ab=b+ai i* *k ki-1i-1, i=i+1;, i=i+1;第四步，判断第四步，判断inin是否成立是否成立. .若是若是, ,则执行第五则执行第五步步, ,否则否则, ,返回第三步；返回第三步；第五步，输出第五步，输出b b的值的值. .15.k15.k进制化十进制的算法进制化十进制的算法110( )110110(10)nnknnnn

9、a aa aakakakak16. 16. 十进制化十进制化k k进制的算法进制的算法第四步，若第四步，若q0q0，则，则a=qa=q，返回第二步；否则，返回第二步；否则，输出全部余数输出全部余数r r排列得到的排列得到的k k进制数进制数. .第一步，输入十进制数第一步，输入十进制数a a和基数和基数k k的值的值. .第二步，求出第二步，求出a a除以除以k k所得的商所得的商q q，余数，余数r.r.第三步，把所得的余数依次从右到左排列第三步，把所得的余数依次从右到左排列. .除除k k取余法取余法三、巩固练习三、巩固练习 习题习题1.3 B组：组：某班有某班有45位学生，设计一个算法，

10、输入每个学生的数学成位学生，设计一个算法，输入每个学生的数学成绩后，分别统计在区间绩后，分别统计在区间0,60), 60,80), 80,100内的成绩的个数，用自然语言内的成绩的个数，用自然语言描述算法步骤，可用描述算法步骤，可用a(i)表示第表示第i个学生的成绩。个学生的成绩。算法步骤：算法步骤：S1:令令p=0,q=0,m=0，i=1,n=45S2:输入学生的成绩输入学生的成绩ts3:判断判断0t60，若是则，若是则p=p+1,执行执行S6s4:判断判断60t80，若是则，若是则q=q+1,执行执行S6s5:判断判断80t 100，若是则，若是则m=m+1, 执行执行S6开始p=0,q=

11、0,m=0,i=1,n=45输入t0t6060t45i=i+1 输出p,q,m结束p=p+1q=q+1m=m+1YYYYNNNNS6:i=i+1,判断是否判断是否i45,若是执行若是执行S7，否则返回，否则返回S2S7：输出输出p,q,m开始p=0,q=0,m=0,i=1,n=45输入t0t6060t45i=i+1 输出p,q,m结束p=p+1q=q+1m=m+1YYYYNNNNp=0q=0m=0i=1n=45DOINPUT “ t=“;tIF 0=t AND t60 THENp=p+1END IFIF 60=t AND t80 THENq=q+1ENF IFIF 80=t AND t45PR

12、INT “p,q,m=“;p.q.mEND复习参考题复习参考题:A组组:1、画程序框图对于输入的、画程序框图对于输入的X值，输出相应的值，输出相应的Y值：值： 0 (x0)(1)y= 1 (0 x1) x (x1) (x+2)2 (x0)(2)开始开始输入输入XX0y=0 x1y=xy=1输出输出y结束结束NYYN开始开始输入输入XX0y=(x+2)2x=0y=4y=(x-2)2输出输出y结束结束NYYN1. INPUT “a1,b1,c1=“;a1,b1,c1 INPUT “a2,b2,c2=“;a2,b2,c2 d=a1*b2-a2*b1 IF D0 THEN x=(b2*c1-b1*c2

13、)/d y=(a1*c2-a2*c1)/d PRINT “x,y=“; x,y ELSE PRINT “输入的数据不符题意输入的数据不符题意” END IF END 开始开始d0 x=(b2*c1-b1*c2)/dy=(a1*c2-a2*c1)/d输出输出x,y输入的数据不符题意输入的数据不符题意结束结束输入输入 a1,b1,c1输入输入a2,b2,c2d=a1*b2-a2*b12、求解二元一次方程组：、求解二元一次方程组：NY3、某市固定电话（市话）的收费标准为：、某市固定电话（市话）的收费标准为：3分钟之内（包括三分钟分钟之内（包括三分钟)收取收取0.2元元;超过超过3分钟分钟,每分钟每分

14、钟(不足一分钟不足一分钟,按一分钟计算按一分钟计算)按按0.10元计算元计算,设计一个算法设计一个算法,根据根据通话时间计算话费通话时间计算话费.INPUT “t=“;tIf t0 then PRINT “输入有误输入有误”END IFIF t0 THEN y=0.2ELSE t=t1+1 y=0.1*tEND IFPRINT y;”元元”END 开始开始t0输入输入t0tni=i+1输出输出s结束结束YNi=1,s=0s=s+1/iINPUT “n=“;ni=1s=0DO s=s+1/i i=i+1LOOP UNTIL inPRINT sEND5.一个球从一个球从100M高处自由落下高处自由

15、落下,每次着地后又跳回到原来高度的一半再落下每次着地后又跳回到原来高度的一半再落下,编写编写程序程序,求当它第求当它第10次着地时次着地时,(1)向下的运动共经过多少米向下的运动共经过多少米?(2).第第10次着地后反弹多次着地后反弹多高高?(3).全程共经过多少米全程共经过多少米?开始开始k=10i=i/2输出输出i结束结束YNk=1,s=0s=s+ii=100k=k+1输出输出2s-100输出输出sk=1s=0i=100WHILE k=100 s=s+I i=i/2 k=k+1WENDPRINT “(1)=“;sPRINT “(2)=“;iPRINT “(3)=“;2*s-100END 复

16、习参考题复习参考题B组：组：1、编写程序，将用户输入的正、编写程序，将用户输入的正整数转换成相应的星期值输出。整数转换成相应的星期值输出。开始开始输入输入 nr=0r=1r=2r=3r=4r=5r=6结束结束r=n mod 7SundayTuesdayMondayWednesdayThursdayFridaySaturdayYYYYYYYNNNNNNNINPUT “n=“;nr=n MOD 7IF r=0 THEN PRINT “Sunday”END IFIF r=1 THEN PRINT “Monday”END IFIF r=2 THEN PRINT “Tuesday”END IFIF r=

17、3 THEN PRINT “Wednesday”END IFIF r=4 THEN PRINT “Thursday”END IFIF r=5 THEN PRINT “Friday”END IFIF r=6 THEN PRINT “Saturday”END IFend开始开始输入输入nr=n MOD 7r=0输出星期日输出星期日输出输出 r结束结束NYINPUT “n=“;nr =n MOD 7IF r =0 THENPRINT “星期日星期日”ELSEPRINT ”星期星期”;rEND IFEND2.画出程序框图画出程序框图,用二分法求方程用二分法求方程1.3x2-26.013x2+0.975

18、x-19.50975=0在在(20,21)之之间的近似根间的近似根(精确度为精确度为0.005)开始开始a=20：b=21:d=0.005f(x)=1.3x2-26.013x2+0.975x-19.50975m=(a+b)/2b=ma=mf(a)f(m)0|a-b|d或或f(m)= 0结束结束输出所求的近似根输出所求的近似根m否否是是否否是是a=20b=21d=0.005y=1.3*x3-26.013*x2+0.975*x-19.50975DO m=(a+b)/2 g= 1.3*a3-26.013*a2+0.975*a-19.50975 f=1.3*m3-26.013*m2+0.975*m-19.50975 IF g*f0 THEN b=m ELSE a=m END IFLOOP UNTIL ABS(a-b)2)位数是位数是不是回文数，用自然语言描述算法步骤。不是回文数，用自然语言描述算法步骤。算法步骤：算法步骤：S1：输入一个正整数输入一个正整数X和它的位数和它的位数n。S2：判断判断n是不是偶数，如果是不是偶数，如果n是偶数，令是偶数，令m=n/2,如果如果n 是奇数，令是奇数，令m=(n-1)/2。S3：当当I 从从1到到m取值时，依次判断取值时，依次判断x的第的第i位与第位与第(n+i-1)位位是的数字是不是相等，如果都相等，则是的数字是