《131算法案例1课件.ppt》由会员分享，可在线阅读，更多相关《131算法案例1课件.ppt（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1.31.3算算 法法 案案 例例案案 例例11.求求25和和35的最大公约数的最大公约数.2.求求8251和和6105的最大公约数的最大公约数 . 辗转相除法辗转相除法, 又名又名“欧几欧几里德算法里德算法”（Euclidean algorithm）乃求两数）乃求两数之最大公因数算法之最大公因数算法.它它是最古老而有效的是最古老而有效的算法算法, 其可追溯至公元前其可追溯至公元前300年年.它首次出现于欧几它首次出现于欧几里德的几何原本中，里德的几何原本中，而在中国则可以追溯至而在中国则可以追溯至东汉出现的九章算东汉出现的九章算术术.它并不需要把二它并不需要把二数作质因数分解数作质因数分解
2、.欧欧几几里里德德辗转相除法（欧几里得算法）辗转相除法（欧几里得算法） 例例1用辗转相除法求用辗转相除法求8251和和6105的的 最大公约数最大公约数思考思考：从上面的例子可以看出：从上面的例子可以看出 计算的规律是什么？计算的规律是什么？ 开始开始输入：输入：m,n（mn）输出：输出：m结束结束r=0?m=nNY求求m除以除以n的余数的余数rn=r你能写出对应的程序吗？九章算术九章算术更相减损术更相减损术 算理：算理：可半者半之，不可半者，副置分母、可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，子之数，以少减多，更相减损，求其等也，以等数约之。以等数约之。例例3 用
3、更相减损术求用更相减损术求98与与63的最大公约数的最大公约数解：由于解：由于63不是偶数，把不是偶数，把98和和63以大数减小数，以大数减小数， 并辗转相减并辗转相减 9863356335283528728721217141477所以，所以，98和和63的最大公约数等于的最大公约数等于7 延伸：延伸： 你能根据减损术设计程序，来计算你能根据减损术设计程序，来计算两个正数的最大公约数吗？两个正数的最大公约数吗？开始输入m,nm=n？mn？m=m-nn=n-m输出m结束是否是否否练习练习1.分别用辗转相除法和更相减损术求分别用辗转相除法和更相减损术求779与与209的的 最大公约数，需要运算的次数分别为多少次？最大公约数，需要运算的次数分别为多少次？2.分别用辗转相除法和更相减损术求分别用辗转相除法和更相减损术求168、54 的最大公约数？的最大公约数？请学生谈一请学生谈一谈谈2.你能用所学你能用所学的知识去解的知识去解决一些实际决一些实际问题吗？问题吗？1.这节课你有这节课你有哪些收获哪些收获五、归纳小结五、归纳小结六、作业布置六、作业布置作业：课本作业：课本P48页习题页习题1.3A组第组第1题题