1.3.1算法案例辗转相除法和更相减损术市公开课金奖市赛课一等奖课件

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页〖创设情景，揭示课题〗[问题2]:我们都是利用找条约数方法来求最大条约数，假如条约数比较大而且依据我们观察又不能得到一些条约数，我们又应该怎样求它们最大条约数？比如求8251与6105最大条约数?思绪1：试值？！何时结束？有何好方法？第3页案例一：辗转相除法（欧几里得算法）观察用辗转相除法求8251和6105最大条约数过程第一步

用两数中较大数除以较小数，求得商和余数

8251=6105×1+2146结论：8251和6105条约数就是6105和2146条约数，求8251和6105最大条约数，只要求出6105和2146条约数就能够了.第二步对6105和2146重复第一步做法

6105=2146×2+1813

同理6105和2146最大条约数也是2146和1813最大条约数.第4页完整过程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第5页问题提出：你能把辗转相除法编成一个计算机程序吗？算法分析：从上面对辗转相除法认识中能够看出，辗转相除法中包含重复操作步骤，所以能够用循环结构来结构算法。算法步骤：第一步，给定两个正整数m，n(m>n)。第二步，计算m除以n所得余数r。第三步，m=n，n=r。第四步，若r=0，则m,n最大条约数等于m；不然，返回第二步。第6页否思索：画出辗转相除法程序框图并设计其程序开始输入两个正数整m,nr=mMODnr=0?输出m结束m=nn=r是INPUTm,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND第7页思索：你能用当型循环结构结构算法，求两个正整数最大条约数吗？试写出算法步骤、程序框图和程序。分析：在使用当型循环结构时，因为在输入两个正数后，直接进入判断r>0,这里没有一个最初r值，因而在设计过程中，可先令r=1。算法步骤：第一步，给定两个正整数m，n(m>n)。第二步,令r=1.第三步，若r>０，则执行第四步；不然，m，n最大条约数等于m,结束算法.第四步，计算m除以n所得余数r。第五步，m=n，n=r,返回第三步.第8页开始输入m,nr=1r>0?输出m结束n=r求m除以n余数rm=n是否程序框图以下：程序以下：INPUTm,nr=1WHILEr>0r=mMODnm=nn=rWENDPRINTmEND第9页知识探究（二）:更相减损术

1:设两个正整数m>n，若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，第10页《九章算术》——更相减损术

算理：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之.算法分析：第一步、任意给定两个正整数，判断他们是否都是偶数，若是，用2约简；若不是，执行第二步。第二步、以较大数减较小数，接着把所得差与较小数比较，并以大数减小数。继续这个操作，直到所得减数和差相等为止，则这个等数就是所求最大条约数.第11页例2、用更相减损术求98与63最大条约数（自己按照步骤求解）解：因为63不是偶数，把98和63以大数减小数，并辗转相减。=7所以，98和63最大条约数等于7。（98，63）=（63，35）98-63=35

63-35=28=（35，28）35-28=7=（28，7）28-7=21=（21，7）21-7=14=（14，7）14-7=7=（7，7）第12页练习：用更相减损术求以下两数最大条约数：（1）（225，135）（2）（98，196）（3）（72，168）（4）（153，119）45982417思索：更相减损直到何时结束？利用是哪种算法结构？更相减损是一个重复执行直到减数等于差时停顿步骤，这实际也是一个循环结构第13页2:上述求两个正整数最大条约数方法称为更相减损术.普通地，用更相减损术求两个正整数m，n最大条约数，能够用什么逻辑结构来结构算法？其算法步骤怎样设计？第一步，给定两个正整数m，n(m>n).

第三步，计算m-n所得差d.第四步，判断“d不等于n”是否成立，若是，则将n，d中大者用m表示，小者用n表示，返回第三步；不然，2^k*d(k是约简整数2个数)为所求最大条约数。第二步，若m、n都是偶数，则不停用2约简，使他们不一样时是偶数，约简两个数仍记为m，n。第14页讨论：

你能依据更相减损术算法步骤画出其程序框图并写出程序语句吗?第15页其算法步骤也能够这么设计第一步，给定两个正整数m，n(m>n).

第二步，计算m-n所得差d.第三步，比较n与d大小，其中大者用m表 示，小者用n表示.

第四步，若m=n，则m，n最大条约数等于 m；不然，返回第二步.第16页其程序框图和程序语句以下：

INPUT“m,n=”;m,nIFm<nTHENa=mm=nn=aENDIFd=m-nWHILEd<>nIFd>nTHENm=dELSEm=nn=dENDIFd=m-nWENDPRINTdENDm第17页思索：辗转相除法与更相减损术有什么区分和联络？区分：计算上辗转相除法以除法为主，更相减损术以减法为住；在计算次数上，辗转相除法计算次数相对较少，尤其当两个数大小差异较大时计算次数区分较显著；从结果输出时候看，辗转相除法当余数为0时输出除数，更相减损术当差和减数相等时输出差。联络：都是求最大条约数方法。因为做一次除法与做若干次减法效果相同，商就是减法次数，余数就是最终差，由此可知二者是完全统一！第18页练习：1，以下说法中正确是（）A辗转相除法是中国古代数学中算法B更相减损术与辗转相除法算理完全不一样C辗转相除法与更相减损术相比较，用辗转相除法求最大条约数最优越D辗转相除法与更相减损术，在设计程序时，都要用到循环结构。D第19页

2，4830与3289最大条约数为_______3，用更相减损术求87与27最大条约数时，重复相减，直至求出最大条约数，需要进行减法运算次数是______4，用辗转相除法求87与27最大条约数，需要进行除法运算次数是_____5，46，115，276最大条约数是____238323第20页

6，下面是求115与276最大条约数程序，把程序补充完整。a=115b=276DOr=__________a=bb=rLOOPUNTILr=____PRINTaEN