公开课算法案例-辗转相除法与更相减损术课件(人.ppt

1、1.3 1.3 算法案例算法案例 第一课时第一课时 我们是如何求两个正数的最大公约数的？我们是如何求两个正数的最大公约数的？如：求下面两个正整数的最大公约数：如：求下面两个正整数的最大公约数：（1）求）求25和和35的最大公约数的最大公约数（2）求）求2520和和1470的最大公约数的最大公约数25（1）55357（2）147010 147 2520252所以，所以，25和和35的最的最大公约数为大公约数为5 所以，所以，2520和和1470的最大公约数为的最大公约数为210解：解：736 217123如何算出如何算出8251和和6105的最大公约数？的最大公约数？（欧几里德算法）（欧几里德算

2、法）思考思考1:对于对于82518251与与61056105这两个数，由于这两个数，由于 8251=8251=610561051+1+21462146 82518251与与61056105的公约数就是的公约数就是61056105与与 21462146的公约数。的公约数。？那么那么,8251,8251与与61056105这两个数的公约数和这两个数的公约数和 61056105与与21462146的公约数有什么关系？的公约数有什么关系？思考思考2:重复上述操作，如何得到重复上述操作，如何得到82518251与与 61056105这两个数的最大公约数？这两个数的最大公约数？完整的过程完整的过程8251

3、=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0例：例：用辗转相除法求用辗转相除法求225和和135的最大公约数的最大公约数225=1351+90135=901+4590=452+0显然显然37是是148和和37的最大公约数，的最大公约数，也就是也就是8251和和6105的最大公约的最大公约数数 显然显然45是是90和和45的最大公约数，也就是的最大公约数，也就是225和和135的最大公约数的最大公约数 S1S1：用大数除以小数：用大数除以小数S2S2：除数变成被除数，余数变成除数：除数变成被

4、除数，余数变成除数S3S3：重复：重复S1S1，直到余数为，直到余数为0 0从上面的两个例子中可以看出从上面的两个例子中可以看出 计算的规律是什么？计算的规律是什么？辗转相除法是一个反复执行直辗转相除法是一个反复执行直到余数等于到余数等于0停止的步骤，这实际上停止的步骤，这实际上是一个循环结构。是一个循环结构。8251=61051+2146 6105=21462+1813 2146=18131+333 1813=3335+148333=1482+37148=374+0m=n q r思考思考3:辗转相除法中的关键步骤是哪种逻辑结构？辗转相除法中的关键步骤是哪种逻辑结构？其算法步骤如何设计？其算法

5、步骤如何设计？第一步：给定两个正整数第一步：给定两个正整数m m，n(mn(mn)n)。第二步：计算第二步：计算m m除以除以n n所得的余数所得的余数r r。第三步：第三步：m=nm=n，n=rn=r。第四步：判断第四步：判断“r=0”r=0”是否成立，是否成立，若若r=0r=0，则，则m m，n n的最大公约的最大公约数等于数等于m m；否则，返回第二步。；否则，返回第二步。8251=61051+2146 6105=21462+1813 2146=18131+333 1813=3335+148333=1482+37148=374+0m=n q r思考思考3:辗转相除法中的关键步骤是哪种逻辑

6、结构？辗转相除法中的关键步骤是哪种逻辑结构？其算法步骤如何设计？其算法步骤如何设计？用程序框图表示出右边的过程用程序框图表示出右边的过程r=m MOD nm=nn=r是否r=0?思考思考5:如果用当型循环结构构造算法，如果用当型循环结构构造算法，则用辗转相除法求两个正整数则用辗转相除法求两个正整数m m、n n的的最大公约数的程序框图和程序分别如最大公约数的程序框图和程序分别如何表示？何表示？是是开始开始求求m除以除以n的余数的余数rm=n否否输出输出m结束结束n=rr0？输入输入m，nr=1练习练习1 1：利用辗转相除法求两数：利用辗转相除法求两数40814081与与 2072320723的

7、最大公约数的最大公约数.(53)(53)20723=40815+3184081=31812+265318=2651+53265=535+0练习练习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的最大公约数是的最大公

8、约数是5.5.可半者半之，不可半者，副置分母、子之可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数数，以少减多，更相减损，求其等也，以等数约之。约之。九章算术九章算术中的更相减损术：中的更相减损术：背景介绍：背景介绍：任意给定两个正整数；判断他们是否都是偶数。任意给定两个正整数；判断他们是否都是偶数。若是，则用若是，则用2约简；若不是，则以较大的数减较小约简；若不是，则以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等减小数。继续这个操作，直到所得的减数和差相等为止，则

9、这个等数就是所求的最大公约数。为止，则这个等数就是所求的最大公约数。现代数学中的更相减损术：现代数学中的更相减损术：例例:用更相减损术求用更相减损术求9898与与6363的最大公约数的最大公约数.解：由于解：由于6363不是偶数，把不是偶数，把9898和和6363以大数减小数，以大数减小数，并辗转相减并辗转相减 所以，所以，9898和和6363的最大公约数等于的最大公约数等于7 7 98-63=3598-63=35，14-7=7.14-7=7.21-7=1421-7=14，28-7=2128-7=21，35-28=735-28=7，63-35=2863-35=28，98-63=3598-63=

10、3514-7=714-7=721-7=1421-7=1428-7=2128-7=2135-28=735-28=763-35=2863-35=28思考思考6:用什么逻辑结构来构造算法？其算法步用什么逻辑结构来构造算法？其算法步 骤如何设计？骤如何设计？程序框图如何表示？程序框图如何表示？m n k第一步，给定两个正整数第一步，给定两个正整数m m，n(mn(mn).n).第二步，计算第二步，计算m-nm-n所得的差所得的差k.k.第三步，比较第三步，比较n n与与k k的大小，其中大的大小，其中大 者用者用m m表示，小者用表示，小者用n n表示表示.第四步，若第四步，若m=nm=n，则，则m

11、m，n n的最大公约的最大公约 数等于数等于m m；否则，返回第二步；否则，返回第二步.理论迁移理论迁移 例例1.1.分别用辗转相除法和更相减损分别用辗转相除法和更相减损 术求术求168168与与9393的最大公约数的最大公约数.辗转相除法：辗转相除法：168=93168=931+75 1+75 93=75 93=751+181+18 75=18 75=184+3 4+3 18=3 18=36+06+0更相减损术更相减损术:168-93=75 168-93=75，18-3=1518-3=15，93-75=1893-75=18，15-3=1215-3=12，75-18=5775-18=57，12

12、-3=912-3=9，57-18=3957-18=39，9-3=69-3=6，39-18=2139-18=21，6-3=36-3=3。21-18=321-18=3，比较辗转相除法与更相减损术的区别比较辗转相除法与更相减损术的区别（1 1）都是求最大公约数的方法，计算上辗转相除）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。大小区别较大时计算次数的区别较明显。（2 2）从结果体现形式来看，辗转相

13、除法体现结果）从结果体现形式来看，辗转相除法体现结果是以相除余数为是以相除余数为0 0则得到，而更相减损术则以减数与则得到，而更相减损术则以减数与差相等而得到差相等而得到小结小结 1.1.辗转相除法，就是对于给定的两个正整辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约这时的较小的数即为原来两个数的最大公约数数.小结作业小结作业 2.2.更相

14、减损术，就是对于给定的两个正更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数数即为原来两个数的最大公约数.比较辗转相除法与更相减损术的区别比较辗转相除法与更相减损术的区别（1 1）都是求最大公约数的方法，计算上辗转相除）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计

15、算次数相对较少，特别当两个数字上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。大小区别较大时计算次数的区别较明显。（2 2）从结果体现形式来看，辗转相除法体现结果）从结果体现形式来看，辗转相除法体现结果是以相除余数为是以相除余数为0 0则得到，而更相减损术则以减数与则得到，而更相减损术则以减数与差相等而得到差相等而得到小结小结 任意给定两个正整数；判断他们是否都是偶数。任意给定两个正整数；判断他们是否都是偶数。若是，则用若是，则用2约简；若不是，则以较大的数减较小约简；若不是，则以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数的数，接着把所得的差与较

16、小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。为止，则这个等数就是所求的最大公约数。例例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最大公约数是最大公约

17、数是5.5.故故325325，130130，270270三个数的最大公约三个数的最大公约数是数是5.5.该算法的程序框图该算法的程序框图:开始开始输入输入m，n求求m除以除以n的余数的余数rm=nn=rr=0？是是输出输出m结束结束否否思考思考4:该程序框图对应的程序如何表述？该程序框图对应的程序如何表述？INPUT mINPUT m，n nDODOr=m MOD nr=m MOD nm=nm=nn=rn=rLOOP UNTILLOOP UNTIL r=0r=0PRINT mPRINT mENDEND是是开始开始输入输入m，n求求m除以除以n的余数的余数rm=nn=rr=0？输出输出m结束结束

18、否否开始开始输入输入m，n求求m除以除以n的余数的余数rm=nr=0？否否输出输出m结束结束n=rINPUT mINPUT m，n nWHILEWHILE n n0 0r=m MOD nr=m MOD nm=nm=nn=rn=rWENDWENDPRINT mPRINT mENDEND是是知识探究（二）知识探究（二）:更相减损术更相减损术 可半者半之，不可半者，副置分母、子之数，以可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。少减多，更相减损，求其等也，以等数约之。第一步：第一步：任意给定两个正整数；判断他们是否都是偶数。任意给定两个正整数；判断他们是否都是偶

19、数。若是，则用若是，则用2约简；若不是则执行第二步。约简；若不是则执行第二步。第二步：第二步：以较大的数减较小的数，接着把所得的差与较小以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。减数和差相等为止，则这个等数就是所求的最大公约数。（1）、九章算术中的更相减损术：1、背景介绍：（2）、现代数学中的更相减损术：INPUT “m,n=“;m,nIF mn THEN a=m m=n n=aEND IFK=0WHILE m MOD 2=0 AND n MOD

20、 2=0 m=m/2 n=n/2 k=k+1WEND d=m-nWhile dn IF dn then m=d ELSE m=n n=d End if d=m-nWend d=2k*dPRINT dEnd 作业：作业：P45P45练习：练习：1.1.P48P48习题习题1.3A1.3A组：组：1.1.科学精神科学精神 欧几里德留给现代文明的宝贵遗产欧几里德留给现代文明的宝贵遗产 他的生平，后人所知甚少。大概早年在雅典就读,深悉柏拉图的学说。公元前300年左右，欧几里德接受托勒密王（公元前364前283）的邀请，来到亚历山大城，长期在那里工作。他是一位温良敦厚的教育家，对有志数学之士，总是循循善

21、诱。但反对投机取巧、不肯刻苦钻研的作风，也反对狭隘实用观点。218x320 14k jpg欧几里德欧几里德-陈具才,具才软件.学问追求真理而并非追求实利学问追求真理而并非追求实利 知识渊博的欧几里德在教授学生时，像一个真正的父亲那样引导学生，关心他们。然而有时，他也用辛辣的讽刺来鞭挞学生中的傲慢之徒。斯托贝乌斯（约公元500年）转述：有个学生在听讲“第一定理”之后，便问道：“学习几何，究竟会有什么好处？”于是，欧几里得转身吩咐佣人说：“格鲁米阿，拿三个钱币给这位先生，因为他想在学习中获得实利。”“几何学里没有王者大道几何学里没有王者大道”及及“科学无坦途科学无坦途”据希腊学者普罗克洛斯（约41

22、0485年）转述历史记载，亚历山大国王多禄米曾师从欧几里得学习几何，有一次对于欧几里得一遍又一遍地解释他的原理表示不耐烦。国王问道：“有没有比你的方法简捷一些的学习几何学的途径？”欧几里德回答：“陛下！原野上有两种道路，一种是供平民百姓走的崎岖小路，一条种供王者走的坦途。但是在几何学里，大家只能走同一条崎岖小路！走向学问，是没有什么王者大道的！请陛下明白。”欧几里德的这番话，后代广为传诵，简略为“几何无王者之大道”、“求知无坦途”，又成为马克思引用并信奉的名言：“在科学上是没有康庄大道可走的；只有在那崎岖小路上不畏劳苦、勇敢攀登的人，有希望达到光辉的顶点！”16世纪以前多少世代，中国在技术方面

23、一直领先于欧洲。但从来没有出现一个可以同欧几里德相比的、具有真正逻辑思维的中国数学家。结果，中国从未拥有过欧洲人那样的数学理论体系。华夏文明和印度文明等东方文明固然伟大，但是在思维方式方面，自古以来就是存在严重欠缺的！自古以来，中国思想界一向擅长综合、联想、类比，固然具有“中国特色”，但是容易堕入笼统、含混、武断、臆测、想当然、浮皮潦草、牵强附会、不符实际的联想类比、望文生义、不求甚解、含糊朦胧的表述方式。造成的危害是难以估量的。大量事实（甚至某些令人痛心而又可笑可叹可悲的事实）表明，中国人普遍的思维方式亟需提高！这需要我们大家做许多扎实的认真的工作！复习引入复习引入1.回顾算法的三种表示方法

24、：回顾算法的三种表示方法：（1）、自然语言）、自然语言（2）、程序框图）、程序框图（3）、程序语言）、程序语言（三种逻辑结构）（三种逻辑结构）（五种基本语句）（五种基本语句）思考思考2:重复上述操作，如何得到重复上述操作，如何得到82518251与与 61056105这两个数的最大公约数？这两个数的最大公约数？21462146=181318131+1+333333 148 148=37374+04+0 333 333=1481482+2+373718131813=3333335+5+1481488251=8251=610561051+1+2146214661056105=214621462+2

25、+18131813思考思考2:重复上述操作，如何得到重复上述操作，如何得到82518251与与 61056105这两个数的最大公约数？这两个数的最大公约数？21462146=181318131+1+333333 148 148=37374+04+0 333 333=1481482+2+373718131813=3333335+5+1481488251=8251=610561051+1+2146214661056105=214621462+2+18131813思考思考2:该算法的程序框图如何表示？该算法的程序框图如何表示？开始开始输入输入m，nnk？m=n是是输出输出m结束结束mn？k=m-n是是否否n=km=k否否思考思考3:该程序框图对应的程序如何表述？该程序框图对应的程序如何表述？INPUT mINPUT m，n nWHILE WHILE m mn nk=m-nk=m-nIF nIF nk THENk THENm=nm=nn=kn=kELSEELSEm=km=kEND IFEND IFWENDWENDPRINT mPRINT mENDEND开始开始输入输入m，nnk？m=n是是输出输出m结束结束mn？k=m-n是是否否n=km=k否否