辗转相除法与更相减损术课件.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，,思考4:上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法.一般地，用辗转相除法求两个正

3、整数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 MOD n,m=n,n=r,LOOP UNTIL r=0,PRINT m,END,INPUT m，n,WHILE n0,r=m MOD n,m=n,n=r,WEND,PRINT m,END,思考7:用当型循环结构构造算法:,“更相减损术”在中国

4、古代数学专著九章算术中记述为：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之.,知识探究（二）:更相减损术,第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是则执行第二步。,第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。,思考1:求98与63的最大公约数？,98-63=35,14-7=7,21-7=14,28-7=21,35-28=7,63-35=28,思考2:上述求两个正整数的最大公约数的方法称为更相减损术.一般地，用更相减损术求两

5、个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？,第一步，给定两个正整数m，n(mn).,第二步，判断mn是否成立.若不成立,则输 出m,否则转第三步.,第四步，比较n与k的大小，其中大者用m表 示，小者用n表示.之后转第二步.,第三步，计算m-n所得的差k.,思考3:该算法的程序框图如何表示？,思考4:该程序框图对应的程序如何表述？,INPUT m，n,WHILE mn,k=m-n,IF nk THEN,m=n,n=k,ELSE,m=k,END IF,WEND,PRINT m,END,理论迁移,例1 分别用辗转相除法和更相减损术求168与93的最大公约数.,辗转

6、相除法：168=931+75， 93=751+18， 75=184+3， 18=36+0.,更相减损术: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+0，所以65与270最大公约数是5.,故325，130，270三个数的最大公约数是5.,1.辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数.,小结作业,2. 更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数.,比较辗转相除法与更相减损术的区别,1.都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术