1、单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,算法案例2,1.4,已学过的伪代码中的几种基本算法语句,:,(1),赋值语句,:,变量,表达式或变量或常数,(2),输入语句,:,Read a,b,(3),输出语句,:,(4),条件语句,:,Print,a,b,If,A,Then,B,Else,C,End If,复习,当型语句,:,While,p,循环体,End while,直到型语句,:,Do,循环体,Until,p,End Do,循环语句,伪代码中的,:,p,A,Y,N,p,A,Y,N,当循环的次数已经确定，可用“,For”,语句表示,“,For,”,
2、语句伪代码格式：,For I From “,初值”,To“,终值”,step“,步长”,End For,3 5,9 15,在小学，我们学过求两个正整数的最大公约数的方法，先用两个数公有的质因数连续去除，一直到所得的商是互质数为止，然后把所以的除数乘起来，例如，求,18,与,30,的最大共约数：,18 30,2,3,所以，,18,与,30,的最大共约数是：,23=6.,引入,写出求两个正整数,a,b(ab),的最大公约数的一个算法,案例,2,公元前,3,世纪，欧几里得在,原本,第七篇中介绍了求两个正整数,a,b(ab),的最大公约数的方法，即求出一列数：,这列数从第三项开始，每一项都是前两项相除
3、所得的余数，余数为,0,的前一项,r,n,即是,a,和,b,的最大公约数。这种方法称为“,欧几里得辗转相除法,”,辗转相除法,例,1,用辗转相除法求,a=204,和,b=85,的最大公约数。,分析,：,因此，,204,与,85,的最大公约数是,r2=17,.,欧几里得辗转相除法找出,a,b,的最大公约数的,步骤,是,:,（,1,）计算,ab,的余数,r,若,r=0,则,b,为,a,b,的最大公约数；,（,2,）若,r,0,则把前面的除数,b,作为新的被除数,把余数,r,作为新的除数,继续运算,直到余数为,0,此时的除数即为,a,b,的最大公约数,.,求,a,b(ab),的最大公约数的算法为：,
4、S1,输入两个正整数,a,b;,S2,如果,Mod(a,b)0,那么转,S3,否则转,S6;,S3 r Mod(a,b),;,S4 ab;,S5 b,r,转,S2,;,S6,输出,b.,r,MOD(,a,b),a,b,b,r,r=0,是,否,Read,a,b,While,Mod(a,b),0,r,Mod(a,b),ab,b,r,End While,Print,b,End,流程图与伪代码,回顾反思,辗转相除法是当大数被小数除尽时，结束除法运算，较小的数就是最大公约数,求三个以上,(,含三个数,),的数的最大公约数时，可依次通过求两个数的最大公约数与第三数的最大公约数来求得,课外作业,直通车相应练习,
浙ICP备2021020529号-1 | 浙B2-20240490 
