新高一数学《案例1辗转相除法与更相减损术》

1、广灵五中高一数学备课组广灵五中高一数学备课组 刘鸿英刘鸿英1. 1. 回顾算法的三种表述：回顾算法的三种表述：自然语言自然语言程序框图程序框图程序语言程序语言（三种逻辑结构）（三种逻辑结构）（五种基本语句）（五种基本语句）2. 2. 思考：思考： 小学学过的求两个数最大公约数的方法？小学学过的求两个数最大公约数的方法？ 先用两个公有的质因数连续去除，一直除到所得的商是先用两个公有的质因数连续去除，一直除到所得的商是互为质数为止，然后把所有的除数连乘起来互为质数为止，然后把所有的除数连乘起来. .复复 习回顾习回顾所以，所以，7575和和105105的最的最大公约数为大公约数为15152 2、除

2、了用这种方法外还有没有其它方法？、除了用这种方法外还有没有其它方法？如求如求82518251和和61056105的最大公约数的最大公约数. . 1 1、求两个正整数的最大公约数、求两个正整数的最大公约数求求7575和和105105的最大公约数的最大公约数75755 5151510510521215 57 73 31 1、辗转相除法、辗转相除法: :此算法是欧几里得在公元前此算法是欧几里得在公元前300300左右左右首先提出的首先提出的 （欧几里得算法）（欧几里得算法） 所谓辗转相除法所谓辗转相除法, ,就是对于给定的两个数就是对于给定的两个数, ,用较大用较大的数除以较小的数的数除以较小的数.

3、 .若余数不为零若余数不为零, ,则将余数和较小的则将余数和较小的数构成新的一对数数构成新的一对数, ,继续上面的除法继续上面的除法, ,直到大数被小数直到大数被小数除尽除尽, ,则这时较小的数就是原来两个数的最大公约数则这时较小的数就是原来两个数的最大公约数. .例例1.用辗转相除法求用辗转相除法求161与与63的最大公约数的最大公约数.161=2633563=1 352835=1 28728=4 70所以，所以，161与与63的最大公约数为的最大公约数为7 7新新 课课82518251= =610561051+1+21462146 61056105= =214621462+2+181318

4、13 21462146= =181318131+1+33333318131813= =3333335+5+148148333333= =1481482+2+3737148148= =37374 4所以所以3737是是82518251和和61056105的最大公约数的最大公约数 例例2 2、求、求82518251和和61056105的最大公的最大公约数约数. . P P4545) )练习练习1(1)1(1)用辗转相除法用辗转相除法求求225225和和135135的最大公约数的最大公约数225225= =1351351+1+9090135135= =90901+1+45459090= =45452

5、 2所以所以4545是是225225和和135135的最大公约数的最大公约数 思考：从上面的两个例子可思考：从上面的两个例子可以看出计算的规律是什么？以看出计算的规律是什么？ S1S1：用大数除以小数：用大数除以小数S2S2：除数变成被除数，余数变成除数：除数变成被除数，余数变成除数S3S3：重复：重复S1S1，直到余数为，直到余数为0 0 辗转相除法是一个反复执行直到余数等于辗转相除法是一个反复执行直到余数等于0 0停止的步骤停止的步骤, ,这实际上是这实际上是一个循环结构一个循环结构m=nm=nq qr r算法步骤算法步骤第一步：输入两个正整数第一步：输入两个正整数m,n(mm,n(mn)

6、.n).第二步：计算第二步：计算m m除以除以n n所得的余数所得的余数r.r.第三步：第三步：m=n,nm=n,n=r.=r.第四步：若第四步：若r r0,0,则则m,nm,n的最大公约数等于的最大公约数等于m;m;否则转到第二步否则转到第二步. . 第五步：输出最大公约数第五步：输出最大公约数m.m.程序框图程序框图程程 序序r=m MOD nr=m MOD nm=nm=n是是否否n=rn=r开始开始输入输入m,nm,nr=0?r=0? 输出输出m m结束结束INPUT “m,n=“;m,nDOLOOP UNTIL r = m MOD nm = nn = rr=0PRINT mEND程序框

7、图程序框图程程 序序INPUT “m,n=“;m,nWHILE WEND r = m MOD nm = nn = rr0PRINT mENDr=1求求m m除以除以n n的余数的余数r rm=nm=n是是否否n=rn=r开始开始输入输入m,nm,nr0?r0? 输出输出m m结束结束r=1r=12 2、更相减损术、更相减损术第一步：任意给定两个正整数第一步：任意给定两个正整数; ;判断他们是否都是偶判断他们是否都是偶数数. .若是若是, ,则用则用2 2约简约简; ;若不是则执行第二步若不是则执行第二步. .第二步：以较大的数减较小的数第二步：以较大的数减较小的数, ,接着把所得的差与接着把所

8、得的差与较小的数比较较小的数比较, ,并以大数减小数并以大数减小数. .继续这个操作继续这个操作, ,直到直到所得的减数和差相等为止所得的减数和差相等为止, ,则这个等数就是所求的最则这个等数就是所求的最大公约数大公约数. . 算理：可半者半之算理：可半者半之, ,不可半者不可半者, ,副置分母、子之数副置分母、子之数, ,以少以少减多减多, ,更相减损更相减损, ,求其等也求其等也, ,以等数约之以等数约之. .例例3 3 用更相减损术求用更相减损术求9898与与6363的最大公约数的最大公约数解：由于解：由于6363不是偶数，把不是偶数，把9898和和6363以大数减小数，并辗转相减以大数

9、减小数，并辗转相减 989863633535636335352828353528287 728287 7212121217 7141414147 77 7所以，所以，9898和和6363的最大公约数等于的最大公约数等于7 7 98=6313563=3512835=2817 辗转相除法与更相减损术的区别辗转相除法与更相减损术的区别(1)(1)都是求最大公约数的方法都是求最大公约数的方法, ,计算上辗转相除法以除法为主计算上辗转相除法以除法为主, ,更相减损术以减法为主更相减损术以减法为主, ,计算次数上辗转相除法计算次数相对较计算次数上辗转相除法计算次数相对较少少, ,特别当两个数字大小区别较大

10、时计算次数的区别较明显特别当两个数字大小区别较大时计算次数的区别较明显. .(2)(2)从结果体现形式来看从结果体现形式来看, ,辗转相除法体现结果是以相除余数辗转相除法体现结果是以相除余数为为0 0而而 得到得到, ,而更相减损术则以减数与差相等而得到而更相减损术则以减数与差相等而得到解法1：（更相减损术）由于49不是偶数，把91和49以大数减小数，并辗转相减，即：914942 49427 42735 35728 28721 21714 147791与49的最大公约数是7。解法2（辗转相除法） 9149142 494217 4276 91与49的最大公约数是7。探究探究3:怎样用更相减损术求

11、182与98的最大公约数? 方法：由于 182与98 都是偶数，故将它们同除以2，得91与49，再用上面的方法求得91与49的最大公约数为7，则72=14为182与98的最大公约数.理论迁移理论迁移 例例1 1 分别用辗转相除法和更相减损分别用辗转相除法和更相减损术求术求168168与与9393的最大公约数的最大公约数. . 辗转相除法：辗转相除法：168=93168=931+751+75， 93=7593=751+181+18， 75=1875=184+34+3， 18=318=36.6.更相减损术更相减损术:168-93=75:168-93=75， 93-75=1893-75=18， 75

12、-18=5775-18=57， 57-18=3957-18=39， 39-18=2139-18=21， 21-18=321-18=3， 18-3=1518-3=15， 15-3=1215-3=12， 12-3=912-3=9， 9-3=69-3=6， 6-3=3.6-3=3. 例例2 2 求求325325，130130，270270三个数的最大三个数的最大公约数公约数. . 因为因为325=130325=1302+652+65，130=65130=652 2，所以所以325325与与130130的最大公约数是的最大公约数是65.65. 因为因为270=65270=654+104+10，65=1065=106+56+5，10=510=52 2，所以，所以6565与与270270最大公约数是最大公约数是5. 5. 故故325325，130130，270270三个数的最大公约三个数的最大公约数是数是5.5.用更相减损术求两个整用更相减损术求两个整数数m，n的最大公约数的最大公约数INPUT “m,n=”;m,nWHILE mn IF mn T