求两个正整数最大公约数的算法.ppt

《求两个正整数最大公约数的算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、求两个正整数最大公约数的算法学习目标：（１）了解中国古代数学中求两个正整数最大公约数的算法以及割圆术的算法；（２）通过对“更相减损之术”及“割圆术”的学习，更好的理解将要解决的问题“算法化”的思维方法，并注意理解推导“割圆术”的操作步骤。（3）学会借助实例分析，探究数学问题。人们在长期的生活，生产和劳动过程中，创造了整数，分数，小数，正负数及其计算，以及无限逼近任一实数的方法，在代数学，几何学方面，我国在宋，元之前也都处于世界的前列。我们在小学，中学学到的算术，代数，从记数到多元一次联立方程的求根方法，都是我国古代数

2、学家最先创造的。更为重要的是我国古代数学的发展有着自己鲜明的特色，也就是“寓理于算”，即把解决的问题“算法化”。本章的内容是算法，特别是在中国古代也有着很多算法案例，我们来看一下并且进一步体会“算法”的概念。求最大公约数你能求出18与30的公约数吗?你能看出78与36的公约数吗?更相减损之术（指导阅读课本P27----P28）步骤：以两数中较大的数减去较小的数，即７８－３６＝４２；以差数４２和较小的数3６构成新的一对数，对这一对数再用大数减去小数，即４２－３６＝６,再以差数６和较小的数３６构成新的一对数，对这一对数再

3、用大数减去小数，即３６－６＝３０,继续这一过程,直到产生一对相等的数，这个数就是最大公约数即，由，得与有相同的公约数理论依据：算法：输入两个正数如果，则执行，否则转到将的值赋予若，则把赋予，把赋予，否则把赋予，重新执行输出最大公约数程序:a=input(“a=”)b=input(“b=”)whilea<>bifa>=ba=a-b;elseb=b-a；endendprint(%io(2),a,b)我国早期也有解决求最大公约数问题的算法，就是更相减损术。更相减损术求最大公约数可半者半之，不可半者，副置分母分子之数，以少减

4、多，更相减损，求其等也，以等数约之。翻译出来为：第一步：任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数。例1用更相减损术求91与49的最大公约数.更相减损术的应用解：由于49不是偶数，把91和49以大数减小数，并辗转相减，即：91－48＝4249－42＝742－7＝3535－7＝2828－7＝2121－7＝1414－7＝7所以，91与49的

5、最大公约数是7。例2求两个正数a=204和b=85的最大公约数。辗转相除法求最大公约数分析：204与85两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数204＝85×2＋34显然204的最大公约数也必是85的约数，同样204与85的公约数也必是34的约数，所以204与85的最大公约数也是85与34的最大公约数。85＝34×2＋1734＝17×2+0则17为204与85的最大公约数。辗转相除法的基本步骤：第一步：用较大的数m除以较小的数n得到一个商q0和一个余数r0；第二步：若

6、r0＝0，则n为m，n的最大公约数；若r0≠0，则用除数n除以余数r0得到一个商q1和一个余数r1；第三步：若r1＝0，则r1为m，n的最大公约数；若r1≠0，则用除数r0除以余数r1得到一个商q2和一个余数r2；…………依次计算直至rn＝0，此时所得到的rn－1即为所求的最大公约数。程序框图：a=input(“a=”);b=input(“b=”);Whilemodulo(a,b)<>0,r=modulo(a,b);a=b;b=r;endd=b开始输入a,b求a除以b的余数ra=bb=rr=0?结束输出b是否程序：比

7、较辗转相除法与更相减损术的区别（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到。巩固运用求196和147的最大公约数回顾反思辗转相除法是当大数被小数除尽时，结束除法运算，较小的数就是最大公约数．更相减损术是当大数减去小数的差等于小数时减法停止．较小的数就是最大公约数．求三个以上(含三个数)的数的最大

8、公约数时，可依次通过求两个数的最大公约数与第三数的最大公约数来求得．