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

1、1.3 算法案例 第一课时 1. 我们是如何求两个正数的最大公约数的？如：求下面两个正整数的最大公约数：（1）求25和35的最大公约数（2）求2520和1470的最大公约数25（1）55357（2）147010 147 2520252所以，25和35的最大公约数为5 所以，2520和1470的最大公约数为210解：回顾736 217123如何算出8251和6105的最大公约数？2.辗转相除法（欧几里德算法）3.思考1:对于8251与6105这两个数，由于 8251=61051+2146 8251与6105的公约数就是6105与 2146的公约数。？那么,8251与6105这两个数的公约数和 6

2、105与2146的公约数有什么关系？ 4.思考2:重复上述操作，如何得到8251与 6105这两个数的最大公约数？5.完整的过程8251=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的最大公约数 S1：用大数除以小数S2：除数变成被除数，余数变成除数S3

3、：重复S1，直到余数为0从上面的两个例子中可以看出 计算的规律是什么？ 6. 辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构。 8251=61051+2146 6105=21462+1813 2146=18131+333 1813= 3335+148333= 1482+37148= 374+0m = n q r思考3:辗转相除法中的关键步骤是哪种逻辑结构？ 其算法步骤如何设计？ 第一步：给定两个正整数m，n(mn)。第二步：计算m除以n所得的余数r。 第三步：m=n，n=r。第四步：判断“r=0”是否成立， 若r=0，则m，n的最大公约数等于m；否则，返回第二步。 7

4、. 8251=61051+2146 6105=21462+1813 2146=18131+333 1813= 3335+148333= 1482+37148= 374+0m = n q r思考3:辗转相除法中的关键步骤是哪种逻辑结构？ 其算法步骤如何设计？ 用程序框图表示出右边的过程r=m MOD nm = nn = r是否r=0?8.思考5: 如果用当型循环结构构造算法，则用辗转相除法求两个正整数m、n的最大公约数的程序框图和程序分别如何表示？9.是开始求m除以n的余数rm=n否输出m结束n=rr0？输入m，nr=110.练习1：利用辗转相除法求两数4081与 20723的最大公约数. (5

5、3)20723=40815+3184081=31812+265318=2651+53265=535+011.练习2：求325，130，270三个数的最大公约数. 325=1302+65，130=652， 325与130的最大公约数是65. 270=654+10，65=106+5， 10=52， 65与270最大公约数是5. 故325，130，270的最大公约数是5.12. 可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。九章算术中的更相减损术：背景介绍： 任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是，则以较大的数减较小的数，接着把所得的差

6、与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。 现代数学中的更相减损术：13.例: 用更相减损术求98与63的最大公约数.解：由于63不是偶数，把98和63以大数减小数， 并辗转相减 所以，98和63的最大公约数等于7 98-63=35，14-7=7.21-7=14，28-7=21，35-28=7，63-35=28，14.98-63=3514-7=721-7=1428-7=2135-28=763-35=28思考6: 用什么逻辑结构来构造算法？其算法步 骤如何设计？程序框图如何表示？m n k第一步，给定两个正整数m，n(mn). 第二

7、步，计算m-n所得的差k. 第三步，比较n与k的大小，其中大 者用m表示，小者用n表示. 第四步，若m=n，则m，n的最大公约 数等于m；否则，返回第二步. 15.理论迁移 例1. 分别用辗转相除法和更相减损 术求168与93的最大公约数. 辗转相除法： 168=931+75 93=751+18 75=184+3 18=36+016.更相减损术: 168-93=75， 18-3=15， 93-75=18， 15-3=12， 75-18=57， 12-3=9， 57-18=39， 9-3=6， 39-18=21， 6-3=3。 21-18=3， 17.比较辗转相除法与更相减损术的区别（1）都是求

8、最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到小结18. 1.辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数. 小结作业 2. 更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到

9、差和较小的数相等，此时相等的两数即为原来两个数的最大公约数.19.比较辗转相除法与更相减损术的区别（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到小结20. 任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是，则以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。21.

10、例2 求325，130，270三个数的最大公约数. 因为325=1302+65，130=652，所以325与130的最大公约数是65. 因为270=654+10，65=106+5，10=52，所以65与270最大公约数是5. 故325，130，270三个数的最大公约数是5.22.该算法的程序框图:开始输入m，n求m除以n的余数rm=nn=rr=0？是输出m结束否23.思考4:该程序框图对应的程序如何表述？INPUT m，nDOr=m MOD nm=nn=rLOOP UNTIL r=0PRINT mEND是开始输入m，n求m除以n的余数rm=nn=rr=0？输出m结束否24.开始输入m，n求m除

11、以n的余数rm=nr=0？否输出m结束n=rINPUT m，nWHILE n0r=m MOD nm=nn=rWENDPRINT mEND是25.知识探究（二）:更相减损术 可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。（1）、九章算术中的更相减损术：1、背景介绍：（2）、现代数学中的更相减损术：26.INPUT “m,n=“

12、;m,nIF mn THEN a=m m=n n=aEND IFK=0WHILE m MOD 2=0 AND n MOD 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 27.作业：P45练习：1.P48习题1.3A组：1.28.科学精神欧几里德留给现代文明的宝贵遗产他的生平，后人所知甚少。大概早年在雅典就读,深悉柏拉图的学说。公元前300年左右，欧几里德接受托勒密王（公元前364前283）的邀请，来到亚历山大城，长期在那里工作。他是一位

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

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

15、领先于欧洲。但从来没有出现一个可以同欧几里德相比的、具有真正逻辑思维的中国数学家。结果，中国从未拥有过欧洲人那样的数学理论体系。华夏文明和印度文明等东方文明固然伟大，但是在思维方式方面，自古以来就是存在严重欠缺的！自古以来，中国思想界一向擅长综合、联想、类比，固然具有“中国特色”，但是容易堕入笼统、含混、武断、臆测、想当然、浮皮潦草、牵强附会、不符实际的联想类比、望文生义、不求甚解、含糊朦胧的表述方式。造成的危害是难以估量的。大量事实（甚至某些令人痛心而又可笑可叹可悲的事实）表明，中国人普遍的思维方式亟需提高！这需要我们大家做许多扎实的认真的工作！ 31.复习引入1. 回顾算法的三种表示方法：（1）、自然语言（2）、程序框图（3）、程序语言（三种逻辑结构）（五种基本语句）32.思考2:重复上述操作，如何得到8251与 6105这两个数的最大公约数？2146=18131+333 148= 374+0 333= 1482+371813= 3335+1488251=61051+21466105=21462+181333.思考2:重复上述操作，如何得到8251与 6105这两个数的最大公约数？2146=18131+333 148= 374