更相减损术原理_第1页
更相减损术原理_第2页
更相减损术原理_第3页
更相减损术原理_第4页
更相减损术原理_第5页
已阅读5页，还剩8页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

更相减损术原理

—研究性学习2021/12/21更相减损术原理求98与63的最大公约数方法一：79863149方法二：

2021/12/22更相减损术原理更相减损术是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。2021/12/23更相减损术原理更相减损术的原理：(a,b)=(a-b,b)这里将gcd

(a,b)简记为(a,b).更相减损术是辗转相除法（欧几里德算法，Euclidalgorithm）的一个特例，它的原理是(a,b)=(a-nb,b)2021/12/24更相减损术原理下面我们来证明：(a,b)=(a-nb,b)证：不妨设d是a,b的最大公因子。即a=rd,b=sd,并且其中(r,s)=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)于是得证。2021/12/25更相减损术原理九章算术可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。——《九章算术》翻译成现代语言如下：第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。

第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法，实际上就是辗转相除法。2021/12/26更相减损术原理第一步，给定两个正整数m，n(m>n).

第二步，计算m-n所得的差k.第三步，比较n与k的大小，其中大者用m表 示，小者用n表示.

第四步，若m=n，则m，n的最大公约数等于 m；否则，返回第二步.2021/12/27更相减损术原理该算法的程序框图如何表示？开始输入m，nn>km=n是输出m结束m≠nk=m-n是否=m=k否2021/12/28更相减损术原理INPUTm，nWHILEm>nk=m-nIFn>kTHENn=kELSEm=kENDIFWENDPRINTmENDm=n该程序框图对应的程序如何表述?2021/12/29更相减损术原理用更相减损术求98与63的最大公约数解：由于63不是偶数，把98和63以大数减小数，并展转相减

98-63=3563-35=2835-28=728-7=2121-7=1414-7=7

所以，98和63的最大公约数等于7。2021/12/210更相减损术原理理论迁移：用更相减损术求168与93的最大公约数。2021/12/211更相减损术原理更相减损术: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，

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论