搜索
1.3.1算法案例(一)—辗转相除法与更相减损术必修③第一章算法初步咸丰一中杨金煜35915[问题1]：在小学，我们已经学过求最大公约数的知识，你能求出18与30的最大公约数吗？〖创设情景，揭示课题〗183023∴18和30的最大公约数是2×3=6.方法：先用两个数公有的质因数连续去除,一直除到所得的商是互质数为止,然后把所有的除数连乘起来.练习1(1)求25和35的最大公约数,(2)求49和63的最大公约数.25（1）5535749（2）77639所以，25和35的最大公约数为5所以，49和63的最大公约数为7〖创设情景，揭示课题〗[问题2]:我们都是利用找公约数的方法来求最大公约数，如果公约数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求8251与6105的最大公约数?28251261503825136150482514615058251561506825166150思路1：试值？！何时结束？有何好的方法？案例一：辗转相除法（欧几里得算法）观察用辗转相除法求8251和6105的最大公约数的过程第一步用两数中较大的数除以较小的数，求得商和余数8251=6105×1+2146结论：8251和6105的公约数就是6105和2146的公约数，求8251和6105的最大公约数，只要求出6105和2146的公约数就可以了.第二步对6105和2146重复第一步的做法6105=2146×2+1813同理6105和2146的最大公约数也是2146和1813的最大公约数.完整的过程8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0例如，用辗转相除法求225和135的最大公约数225=135×1+90135=90×1+4590=45×2显然37是148和37的最大公约数，也就是8251和6105的最大公约数显然45是90和45的最大公约数，也就是225和135的最大公约数思考：从上面的两个例子可以看出计算的规律是什么？S1：用大数除以小数S2：除数变成被除数，余数变成除数S3：重复S1，直到余数为0问题提出：你能把辗转相除法编成一个计算机程序吗？算法分析：从上面对辗转相除法的认识中可以看出，辗转相除法中包含重复操作的步骤，因此可以用循环结构来构造算法。算法步骤：第一步，给定两个正整数m，n(mn)。第二步，计算m除以n所得的余数r。第三步，m=n，n=r。第四步，若r=0，则m,n的最大公约数等于m；否则，返回第二步。否思考：画出辗转相除法的程序框图并设计其程序开始输入两个正数整m,nr=mMODnr=0?输出m结束m=nn=r是INPUTm,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND思考：你能用当型循环结构构造算法，求两个正整数的最大公约数吗？试写出算法步骤、程序框图和程序。分析：在使用当型循环结构时，因为在输入两个正数后，直接进入判断r0,这里没有一个最初的r值，因而在设计过程中，可先令r=1。算法步骤：第一步，给定两个正整数m，n(mn)。第二步,令r=1.第三步，若r０，则执行第四步；否则，m，n的最大公约数等于m,结束算法.第四步，计算m除以n所得的余数r。第五步，m=n，n=r,返回第三步.开始输入m,nr=1r0?输出m结束n=r求m除以n的余数rm=n是否程序框图如下：程序如下：INPUTm,nr=1WHILEr0r=mMODnm=nn=rWENDPRINTmEND知识探究（二）:更相减损术1:设两个正整数mn，若m-n=d，则m与n的最大公约数和n与k的最大公约数相等.反复利用这个原理，可求得98与63的最大公约数为多少？98-63=35，14-7=7.21-7=14，28-7=21，35-28=7，63-35=28，《九章算术》——更相减损术算理：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之.算法分析：第一步、任意给定两个正整数，判断他们是否都是偶数，若是，用2约简；若不是，执行第二步。第二步、以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数.例2、用更相减损术求98与63的最大公约数（自己按照步骤求解）解：由于63不是偶数，把98和63以大数减小数，并辗转相减。=7所以，98和63的最大公约数等于7。（98，63）=（63，35）98-63=3563-35=28=（35，28）35-28=7=（28，7）28-7=21=（21，7）21-7=14=（14，7）14-7=7=（7，7）练习：用更相减损术求下列两数的最大公约数：（1）（225，135）（2）（98，196）（3）（72，168）（4）（153，119）45982417思考：更相减损直到何时结束？运用的是哪种算法结构？更相减损是一个反复执行直到减数等于差时停止的步骤，这实际也是一个循环结构2:上述求两个正整数的最大公约数的方法称为更相减损术.一般地，用更相减损术求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？第一步，给定两个正整数m，n(mn).第三步，计算m-n所得的差d.第四步，判断“d不等于n”是否成立，若是，则将n，d中大者用m表示，小者用n表示，返回第三步；否则，2^k*d(k是约简整数2的个数)为所求的最大公约数。第二步，若m、n都是偶数，则不断用2约简，使他们不同时是偶数，约简的两个数仍记为m，n。讨论：你能根据更相减损术的算法步骤画出其程序框图并写出程序语句吗?其算法步骤也可以这样设计第一步，给定两个正整数m，n(mn).第二步，计算m-n所得的差d.第三步，比较n与d的大小，其中大者用m表示，小者用n表示.第四步，若m=n，则m，n的最大公约数等于m；否则，返回第二步.其程序框图和程序语句如下：INPUT“m,n=”;m,nIFmnTHENa=mm=nn=aENDIFd=m-nWHILEdnIFdnTHENm=dELSEm=nn=dENDIFd=m-nWENDPRINTdENDm思考：辗转相除法与更相减损术有什么区别和联系？区别：计算上辗转相除法以除法为主，更相减损术以减法为住；在计算次数上，辗转相除法计算次数相对较少，特别当两个数大小差别较大时计算次数的区别较明显；从结果输出的时候看，辗转相除法当余数为0时输出除数，更相减损术当差和减数相等时输出差。联系：都是求最大公约数的方法。因为做一次除法与做若干次减法效果相同，商就是减法的次数，余数就是最后的差，由此可知二者是完全统一的！练习：1，下列说法中正确的是（）A辗转相除法是中国古代数学中的算法B更相减损术与辗转相除法的算理完全不同C辗转相除法与更相减损术相比较，用辗转相除法求最大公约数最优越D辗转相除法与更相减损术，在设计程序时，都要用到循环结构。D2，4830与3289的最大公约数为_______3，用更相减损术求87与27的最大公约数时，反复相减，直至求出最大公约数，需要进行减法运算的次数是______4，用辗转相除法求87与27的最大公约数，需要进行除法运算的次数是_____5，46，115，276的最大公约数是____2383236，下面是求115与276的最大公约数的程序，把程序补充完整。a=115b=276DOr=__________a=bb=rLOOPUNTILr=____PRINTaENDaMODb0小结：辗转相除法与更相减损术的比较:（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主;计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显.（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到.