1.3.1算法案例—辗转相除法与更相减损术.ppt

1、1.3 算法案例,第一课时,问题提出,1.研究一个实际问题的算法，主要从算法步骤、程序框图和编写程序三方面展开.在程序框图中算法的基本逻辑结构有哪几种？在程序设计中基本的算法语句有哪几种？,2.“求两个正整数的最大公约数”是数学中的一个基础性问题，它有各种解决办法，我们以此为案例，对该问题的算法作一些探究.,辗转相除法与 更相减损术,知识探究（一）:辗转相除法,思考1:18与30的最大公约数是多少？你是怎样得到的？,先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公约数.,思考2:对于8251与6105这两个数，由于其公有的质因数较大，利用上述方法

2、求最大公约数就比较困难.注意到8251=61051+2146，那么8251与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，,辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构。,m = n q r,用程序框图

3、表示出右边的过程,r=m MOD n,m = n,n = r,r=0?,是,否,思考4：辗转相除法中的关键步骤是哪种逻辑结构？,思考5:上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法.一般地，用辗转相除法求两个正整数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

4、,n=r,LOOP UNTIL r=0,PRINT m,END,思考7:如果用当型循环结构构造算法，则用辗转相除法求两个正整数m，n的最大公约数的程序框图和程序分别如何表示？,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的最大公约数相等.反复利用这个原理

5、，可求得98与63的最大公约数为多少？,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

6、 m，n,WHILE mn,k=m-n,IF nk THEN,m=n,n=k,ELSE,m=k,END IF,WEND,PRINT m,END,“更相减损术”在中国古代数学专著九章算术中记述为： 可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之.,INPUT “m,n=“;m,n IF mn THEN a=m m=n n=a END IF K=0 WHILE m MOD 2=0 AND n MOD 2=0 m=m/2 n=n/2 k=k+1 WEND d=m- n,While dn IF dn then m=d ELSE m=n n=d End if d=m-n

7、 Wend d=2k*d PRINT d End,理论迁移,例1 分别用辗转相除法和更相减损术求168与93的最大公约数.,辗转相除法：168=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=10

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