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

1.3算法案例

第一课时1.3算法案例第一课时1

我们是如何求两个正数的最大公约数的？如：求下面两个正整数的最大公约数：（1）求25和35的最大公约数（2）求2520和1470的最大公约数25（1）55357（2）1470101472520252所以，25和35的最大公约数为5所以，2520和1470的最大公约数为210解：回顾736217123如何算出8251和6105的最大公约数？我们是如何求两个正数的最大公约数的？如：求下面两个正整数的2辗转相除法（欧几里德算法）辗转相除法（欧几里德算法）3思考1:对于8251与6105这两个数，由于8251=6105×1+2146

8251与6105的公约数就是6105与2146的公约数。？那么,8251与6105这两个数的公约数和

6105与2146的公约数有什么关系？思考1:对于8251与6105这两个数，由于824思考2:重复上述操作，如何得到8251与6105这两个数的最大公约数？思考2:重复上述操作，如何得到8251与5完整的过程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+0显然37是148和37的最大公约数，也就是8251和6105的最大公约数显然45是90和45的最大公约数，也就是225和135的最大公约数S1：用大数除以小数S2：除数变成被除数，余数变成除数S3：重复S1，直到余数为0从上面的两个例子中可以看出计算的规律是什么？完整的过程8251=6105×1+21466105=2146

辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构。8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0m=n×q＋r思考3:辗转相除法中的关键步骤是哪种逻辑结构？其算法步骤如何设计？

第一步：给定两个正整数m，n(m>n)。第二步：计算m除以n所得的余数r。

第三步：m=n，n=r。第四步：判断“r=0”是否成立，若r=0，则m，n的最大公约数等于m；否则，返回第二步。

辗转相除法是一个反复执行直8251=6105×78251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0m=n×q＋r思考3:辗转相除法中的关键步骤是哪种逻辑结构？其算法步骤如何设计？

用程序框图表示出右边的过程r=mMODnm=nn=r是否r=0?8251=6105×1+21466105=2146×28思考5:

如果用当型循环结构构造算法，则用辗转相除法求两个正整数m、n的最大公约数的程序框图和程序分别如何表示？思考5:9是开始求m除以n的余数rm=n否输出m结束n=rr≠0？输入m，nr=1开始求m除以n的余数rm=n否输出m结束n=rr≠0？输入m10练习1：利用辗转相除法求两数4081与20723的最大公约数.(53)20723=4081×5+3184081=318×12+265318=265×1+53265=53×5+0练习1：利用辗转相除法求两数4081与(53)2011练习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.练习2：求325，130，270三个数的最∵325=12

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

现代数学中的更相减损术：可半者半之，不可半者，副置分母、子之数，以少13例:用更相减损术求98与63的最大公约数.解：由于63不是偶数，把98和63以大数减小数，并辗转相减所以，98和63的最大公约数等于798-63=35，14-7=7.21-7=14，28-7=21，35-28=7，63-35=28，例:用更相减损术求98与63的最大公约数.解：由于63不是1498-63=3514-7=721-7=1428-7=2135-28=763-35=28思考6:

用什么逻辑结构来构造算法？其算法步骤如何设计？程序框图如何表示？m－n＝k第一步，给定两个正整数m，n(m>n).

第二步，计算m-n所得的差k.

第三步，比较n与k的大小，其中大者用m表示，小者用n表示.

第四步，若m=n，则m，n的最大公约数等于m；否则，返回第二步.98-63=3514-7=721-7=1428-7=213515理论迁移

例1.分别用辗转相除法和更相减损术求168与93的最大公约数.辗转相除法：168=93×1+75 93=75×1+18 75=18×4+3 18=3×6+0理论迁移例1.分别用辗转相除法和更相减损辗转相16更相减损术: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）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到小结比较辗转相除法与更相减损术的区别小结181.辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数.

小结作业2.更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数.1.辗转相除法，就是对于给定的两个正整数，用较大的数除19比较辗转相除法与更相减损术的区别（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到小结比较辗转相除法与更相减损术的区别小结20任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是，则以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。任意给定两个正整数；判断他们是否都是偶数。若是21例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.例2求325，130，270三个数的最大公约数.22该算法的程序框图:开始输入m，n求m除以n的余数rm=nn=rr=0？是输出m结束否该算法的程序框图:开始输入m，n求m除以n的余数rm=nn=23思考4:该程序框图对应的程序如何表述？INPUTm，nDOr=mMODnm=nn=rLOOPUNTIL

r=0PRINTmEND是开始输入m，n求m除以n的余数rm=nn=rr=0？输出m结束否思考4:该程序框图对应的程序如何表述？INPUTm，nD24开始输入m，n求m除以n的余数rm=nr=0？否输出m结束n=rINPUTm，nWHILEn>0r=mMODnm=nn=rWENDPRINTmEND是开始输入m，n求m除以n的余数rm=nr=0？否输出m结束n25知识探究（二）:更相减损术

可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。（1）、《九章算术》中的更相减损术：1、背景介绍：（2）、现代数学中的更相减损术：知识探究（二）:更相减损术可半者半之，不可半者26INPUT“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

INPUT“m,n=“;m,nWhiled<>n27作业：P45练习：1.P48习题1.3A组：1.作业：28

科学精神

——

欧几里德留给现代文明的宝贵遗产

他的生平，后人所知甚少。大概早年在雅典就读,深悉柏拉图的学说。公元前300年左右，欧几里德接受托勒密王（公元前364～前283）的邀请，来到亚历山大城，长期在那里工作。他是一位温良敦厚的教育家，对有志数学之士，总是循循善诱。但反对投机取巧、不肯刻苦钻研的作风，也反对狭隘实用观点。

218x32014kjpg

欧几里德-陈具才,具才软件...

科学精神

——

29学问追求真理而并非追求实利

知识渊博的欧几里德在教授学生时，像一个真正的父亲那样引导学生，关心他们。然而有时，他也用辛辣的讽刺来鞭挞学生中的傲慢之徒。

斯托贝乌斯（约公元500年）转述：有个学生在听讲“第一定理”之后，便问道：“学习几何，究竟会有什么好处？”于是，欧几里得转身吩咐佣人说：“格鲁米阿，拿三个钱币给这位先生，因为他想在学习中获得实利。”“几何学里没有王者大道”

及“科学无坦途”

据希腊学者普罗克洛斯（约410～485年）转述历史记载，亚历山大国王多禄米曾师从欧几里得学习几何，有一次对于欧几里得一遍又一遍地解释他的原理表示不耐烦。国王问道：“有没有比你的方法简捷一些的学习几何学的途径？”

欧几里德回答：“陛下！原野上有两种道路，一种是供平民百姓走的崎岖小路，一条种供王者走的坦途。但是在几何学里，大家只能走同一条崎岖小路！走向学问，是没有什么王者大道的！请陛下明白。”

欧几里德的这番话，后代广为传诵，简略为“几何无王者之大道”、“求知无坦途”，又成为马克思引用并信奉的名言：“在科学上是没有康庄大道可走的；只有在那崎岖小路上不畏劳苦、勇敢攀登的人，有希望达到光辉的顶点！”

学问追求真理而并非追求实利

30

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

16世纪以前多少世代，中国在技术方面一直领先于欧洲。但从来31复习引入1.回顾算法的三种表示方法：（1）、自然语言（2）、程序框图（3）、程序语言（三种逻辑结构）（五种基本语句）复习引入1.回顾算法的三种表示方法：（1）、自然语言（2）32思考2:重复上述操作，如何得