更相减损术原理.ppt

《更相减损术原理.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、更相减损术原理—研究性学习求98与63的最大公约数方法一：79863149方法二：更相减损术是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。更相减损术的原理：(a,b)=(a-b,b)这里将gcd(a,b)简记为(a,b).更相减损术是辗转相除法（欧几里德算法，Euclidalgorithm）的一个特例，它的原理是(a,b)=(a-nb,b)下面我们来证明：(a,b)=(a-nb,b)证：不妨设d是a,b的最大公因子。即a=rd,b=sd,并且其中(r,s)

2、=1,即存在x,y,使得xr+ys=1.从而a-nb=(r-ns)d,b=sd,且x(r-ns)+(xn+y)s=xr+ys=1,即(r-ns,s)=1于是:d=(a-nb,b)于是得证。九章算术可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。——《九章算术》翻译成现代语言如下：第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，

3、则这个等数就是所求的最大公约数。其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法，实际上就是辗转相除法。第一步，给定两个正整数m，n(m>n).第二步，计算m-n所得的差k.第三步，比较n与k的大小，其中大者用m表示，小者用n表示.第四步，若m=n，则m，n的最大公约数等于m；否则，返回第二步.该算法的程序框图如何表示？开始输入m，nn>km=n是输出m结束m≠nk=m-n是否=m=k否INPUTm，nWHILEm>nk=m-nIFn>kTHENn=kELSEm=kENDIFWENDPRINTm

4、ENDm=n该程序框图对应的程序如何表述?用更相减损术求98与63的最大公约数解：由于63不是偶数，把98和63以大数减小数，并展转相减98-63=3563-35=2835-28=728-7=2121-7=1414-7=7所以，98和63的最大公约数等于7。理论迁移：用更相减损术求168与93的最大公约数。更相减损术:168-93=75，93-75=18，75-18=57，57-18=39，39-18=21，21-18=3，18-3=15，15-3=12，12-3=9，9-3=6，6-3=3.所以168与93的最大

5、公约数是3