1.3.1算法案例示范

算法案例（一）案例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的最大公约数?思路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得到一种商q0和一种余数r0；(m=n×q0+r0)第二步：若r0＝0，则n为m，n为最大公约数；若r0≠0，则用除数n除以余数r0得到一种商q1和一种余数r1；(n=r0×q1+r1)第三步：若r1＝0，则r0为m，r0为最大公约数；若r1≠0，则用除数r0除以余数r1得到一种商q2和一种余数r2；(r0=r1×q2+r2)……依次计算直至rn＝0，此时所得到的rn-1,即为所求的最大公约数.辗转相除法是一种重复执行直到余数等于0停止的环节，这事实上是一种循环构造.8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0m=n×q＋r用程序框图表达出右边的过程r=mMODnm=nn=rr=0?是否思考：辗转相除法中的核心环节是哪种逻辑构造？否思考：画出辗转相除法的程序框图并设计其程序开始

输入两个正数m,nr=mMODnr=0?输出n结束m=nn=r是INPUTm,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTnEND否思考：画出辗转相除法的程序框图并设计其程序开始

输入两个正数m,nm<n?r=mMODnr≠0?输出n结束m=xm=nn=r否是是x=nn=mINPUTm,nIFm<nTHENx=nn=mm=xENDIFr=mMODnWHILEr<>0m=nn=rr=mMODnWENDPRINTnEND练习2：运用辗转相除法求两数4081与20723的最大公约数.(53)20723=4081×5+318;4081=318×12+265;318=265×1+53;265=53×5+0.知识探究（二）:更相减损术

1:设两个正整数m>n，若m-n=k，则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:上述求两个正整数的最大公约数的办法称为更相减损术.普通地，用更相减损术求两个正整数m，n的最大公约数，能够用什么逻辑构造来构造算法？其算法环节如何设计？第一步，给定两个正整数m，n(m>n).

第二步，计算m-n所得的差k.第三步，比较n与k的大小，其中大者用m表 示，小者用n表达.第四步，若m=n，则m，n的最大公约数等于 m；否则，返回第二步.3:该算法的程序框图如何表达？开始输入m，nn>k？m=n是输出m结束m≠n？k=m-n是否n=km=k否4:该程序框图对应的程序如何表述？INPUTm，nWHILEm<>nk=m-nIFn>kTHENm=nn=kELSEm=kENDIFWENDPRINTmEND开始输入m，nn>k？m=n是输出m结束m≠n？k=m-n是否n=km=k否“更相减损术”在中国古代数学专著《九章算术》中记述为：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之.

INPUT“m,n=“;m,nIFm<nTHENa=mm=nn=aENDIFK=0WHILEmMOD2=0ANDnMOD2=0m=m/2n=n/2k=k+1WENDd=m-nWhiled<>nIFd>nthenm=dELSEm=nn=dEndifd=m-nWendd=2^k*dPRINTdEnd

理论迁移

例1分别用辗转相除法和更相减损术求168与93的最大公约数.辗转相除法：168=93×1+75， 93=75×1+18， 75=18×4+3， 18=3×6.更相减损术: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=130×2+65，130=65×2，因此325与130的最大公约数是65.由于270=65×4+10，65=10×6+5，10=5×2，因此65与270最大公约数是5.故325，130，270三个数的最大公约数是5.1.辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数.

小结作业2.更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数.小结：辗转相除法与更相减损术的比较: （1）都是求最大公约数的办法，计算上辗转相除法以除法为主，更相减损术以减法为主;计算次数上辗转相除法计算次数相对较少，特别当两个数字大社区别较大时计算次数的区别较明显. （2）从成果体现形式来看，辗转相除法体现成果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到.作业:课本P45页练习1;P48页A组1.用更相减损术求98与63的最大公约数.