高中数学 1.3.1辗转相除法与更相减损术 新人教A版必修3

1、1.3 算法案例,第一课时,辗转相除法与 更相减损术,算法案例之求最大公约数,求以下几组正整数的最大公约数。 (注：若整数m和n满足n整除m，则（m,n）=n。用（m,n）来表示 m和n的最大公约数。) （1）（18，30） （2）（24，16） （3）（63，63） （4）（72，8） （5）（301，133,想一想，如何求8251与6105的最大公约数,思考1：求18与24的最大公约数,6,8,63,8,7,短除法,知识探究（一）:辗转相除法,思考2:对于8251与6105这两个数，由于其公有的质因数较大，利用上述方法求最大公约数就比较困难.注意到8251=61051+2146，那么825

2、1与6105这两个数的公约数和6105与2146的公约数有什么关系,思考3:又6105=21462+1813，同理，6105与2146的公约数和2146与1813的公约数相等.重复上述操作，你能得到8251与6105这两个数的最大公约数吗,2146=18131+333,148=374+0,333=1482+37,1813=3335+148,8251=61051+2146,6105=21462+1813,8251和6105的最大公约数,解： 8251=61051+2146 6105=2146 2+1813 2146=1813 1+333 1813=333 5+148 333=148 2+37 1

3、48=37 4,8251，6105） =（6105，2146） =（2146，1813） =（1813，333） =（333，148） =（148，37） =37,关系式m=np+r中m,n,r得取值变化情况,8251,6105,2146,6105,2146,2146,1813,1813,333,1813,333,148,148,333,37,148,37,0,辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构,m = n q r,用程序框图表示出右边的过程,r=m MOD n,m = n,n = r,r=0,是,否,思考4：辗转相除法中的关键步骤是哪种逻辑结构,思考5:

4、上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法.一般地，用辗转相除法求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计,第一步，给定两个正整数m，n(mn,第二步，计算m除以n所得的余数r,第三步，m=n，n=r,第四步，若r=0，则m，n的最大公约数等 于m；否则，返回第二步,思考5:该算法的程序框图如何表示,思考6:该程序框图对应的程序如何表述,INPUT m，n,DO,r=m MODn,m=n,n=r,LOOP UNTIL r=0,PRINT m,END,思考7:如果用当型循环结构构造算法，则用辗转相除法求两个正整数m，n的最大公约数的程序框

5、图和程序分别如何表示,INPUT m，n,WHILE n0,r=m MODn,m=n,n=r,WEND,PRINT m,END,练习1：利用辗转相除法求两数4081与20723的最大公约数,53,20723=40815+318; 4081=31812+265; 318=2651+53; 265=535+0,穷举法（也叫枚举法） 步骤： 从两个数中较小数开始 由大到小列举，直到找到公 约数立即中断列举，得到的 公约数便是最大公约数,穷举法,知识探究（二）:更相减损术,思考1:设两个正整数mn，若m-n=k，则m与n的最大公约数和n与k的最大公约数相等.反复利用这个原理，可求得98与63的最大公约

6、数为多少,98-63=35,14-7=7,21-7=14,28-7=21,35-28=7,63-35=28,思考2:上述求两个正整数的最大公约数的方法称为更相减损术.一般地，用更相减损术求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计,第一步，给定两个正整数m，n(mn,第二步，计算m-n所得的差k,第三步，比较n与k的大小，其中大者用m表 示，小者用n表示,第四步，若m=n，则m，n的最大公约数等于 m；否则，返回第二步,思考3:该算法的程序框图如何表示,思考4:该程序框图对应的程序如何表述,INPUT m，n,WHILE mn,k=m-n,IF nk THE

7、N,m=n,n=k,ELSE,m=k,END IF,WEND,PRINT m,END,更相减损术”在中国古代数学专著九章算术中记述为： 可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之,程序： INPUT “a,b”;a,b i=0 WHILE a MOD 2=0 AND b MOD 2=0 a=a/2 b=b/2 i=i+1 WEND DO IF ba THEN t=a a=b b=t END IF a=a-b LOOP UNTIL a=b PRINT a*2i END,理论迁移,例1 分别用辗转相除法和更相减损术求168与93的最大公约数,辗转相除法：168

8、=931+75， 93=751+18， 75=184+3， 18=36,更相减损术:168-93=75， 93-75=18， 75-18=57， 57-18=39， 39-18=21， 21-18=3， 18-3=15， 15-3=12， 12-3=9， 9-3=6， 6-3=3,例2 求325，130，270三个数的最大公约数,因为325=1302+65，130=652，所以325与130的最大公约数是65,因为270=654+10，65=106+5，10=52，所以65与270最大公约数是5,故325，130，270三个数的最大公约数是5,1.辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数,小结作业,2. 更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数,比较辗转相除法与更相减损术的区别 （1）都是求最大公约数的方法，计算上辗转相除法以除法为主