高中数学高中数学：14算法案例-2必修三ppt课件

1、已学过的伪代码中的几种基本算法语句已学过的伪代码中的几种基本算法语句:(1)赋值语句赋值语句:变量变量表达式或变量或常数表达式或变量或常数(2)输入语句输入语句: Read a,b(3)输出语句输出语句:(4)条件语句条件语句:Print a,bIf A Then B Else CEnd If 复习复习当型语句当型语句:While p循环体循环体End while直到型语句直到型语句:Do循环体循环体Until pEnd Do循环语句循环语句伪代码中的伪代码中的:pAYNpAYN当循环的次数已经确定，可用当循环的次数已经确定，可用“For语句表语句表示示“For“For语句伪代码格式：语句伪代

2、码格式： For I From “ For I From “初值初值” To “” To “终值终值” ” step “step “步长步长” End For End For3 59 15 在小学，我们学过求两个正整数的最大公约在小学，我们学过求两个正整数的最大公约数的方法，先用两个数公有的质因数连续去除，数的方法，先用两个数公有的质因数连续去除，一直到所得的商是互质数为止，然后把所以的除一直到所得的商是互质数为止，然后把所以的除数乘起来，例如，求数乘起来，例如，求18与与30的最大共约数：的最大共约数：18 3023 所以，所以，18与与30的最大共约数是：的最大共约数是：23=6.引入引入

3、 写出求两个正整数写出求两个正整数a,b(ab)的最大公约数的一个算法的最大公约数的一个算法案例案例2 2公元前公元前3世纪，欧几里得在世纪，欧几里得在第七篇中第七篇中介绍了求两个正整数介绍了求两个正整数a,b(ab)的最大公约数的最大公约数的方法，即求出一列数：的方法，即求出一列数：. 0 ,121nnrrrrba这列数从第三项开始，每一项都是前两项相这列数从第三项开始，每一项都是前两项相除所得的余数，余数为除所得的余数，余数为0的前一项的前一项rn,即是即是a和和b的最大公约数。这种方法称为的最大公约数。这种方法称为“欧几里得辗欧几里得辗转相除法转相除法”辗转相除法辗转相除法 例例1 用辗

4、转相除法求用辗转相除法求a=204和和b=85的最大公约数的最大公约数。;3428520434,852041，所以为余数r 分析：分析：;172348517,34852，所以为余数r. 217340,17341，所以为余数r因此，因此，204与与85的最大公约数是的最大公约数是r2=17. 欧几里得辗转相除法找出欧几里得辗转相除法找出a,b的最大公约的最大公约数的步骤是数的步骤是: （1计算计算ab的余数的余数r,若若r=0,则则b为为a,b的最大公约数；的最大公约数； （2若若r0,则把前面的除数则把前面的除数b作为新的作为新的被除数被除数,把余数把余数r作为新的除数作为新的除数,继续运算继续运算,直到余数为直到余数为0,此时的除数即为此时的除数即为a,b的最大的最大公约数公约数.l求求a,b(ab)的最大公约数的算法为：的最大公约数的算法为：S1 输入两个正整数输入两个正整数a,b;S2 如果如果Mod(a,b) 0,那么转那么转S3,否则转否则转S6;S3 r Mod(a,b) ;S4 ab;S5 br,转转S2;S6 输出输出b.回顾反思回顾反思 l辗转相除法是当大数被小数除尽时，辗转相除法是当大数被小数除尽时，结束除法运算，较小的数就是最大公结束除法运算，较小的数就是最大公约数约数l求三个以上求三个以上(含三个数含三个数)的数的最大公的数的最大公约数时，可依次通