辗转相除法求最大公约数和最小公倍数及其c语言实现.doc_第1页
辗转相除法求最大公约数和最小公倍数及其c语言实现.doc_第2页
辗转相除法求最大公约数和最小公倍数及其c语言实现.doc_第3页
辗转相除法求最大公约数和最小公倍数及其c语言实现.doc_第4页
全文预览已结束

下载本文档

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

文档简介

辗转相除法 又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯至3000年前。在数学中，辗转相除法，又称欧几里得算法，是求最大公约数的算法。辗转相除法首次出现于欧几里得的几何原本（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的九章算术。 两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相减法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如，252和105的最大公约数是21（252 = 21 12；105 = 21 5）；因为252 105 = 147，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如21 = 5 105 + (2) 252。这个重要的等式叫做贝祖等式。简单的想法设两数为a、b(ab)，b最大公约数(a，b)的步骤如下：用b除a，得a=bq.r1(0r1)。若r1=0，则(a，b)=b；若r10，则再用r1除b，得b=r1q.r2 (0r2).若r2=0，则(a，b)=r1，若r20，则继续用r2除r1,如此下去，直到能整除为止。其最后一个非零除数即为(a，b)。原理及其详细证明设两数为a、b(b1)，则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)dc，b=nc=ycd，故a与b最大公约数成为cd，而非c】 从而可知gcd(b,r)=c，继而gcd(a,b)=gcd(b,r)。证毕。自然语言描述辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的： 1. 若 r 是 a b的余数, 则gcd(a,b) = gcd(b,r)， 2. a 和其倍数之最大公因子为a。 另一种写法是： 1. a b，令r为所得余数（0rb） 若 r = 0，算法结束；b 即为答案。 2. 互换：置 ab，br，并返回第一步。 （程序框图）C语言程序实现#include#includeint main()int a,b,temp;printf(Input a,b:);scanf(%d%d,&a,&b);a=(int)fabs(a);b=(int)fabs(b);/确保下面运算时a和b大于0；if(ab；while(b!=0)temp=a%b;a=b;b=temp;printf(%5dn,a);return 0;由此也可以求出最小公倍数首先我们要引入一个定理：两个数的最大公约数乘以这两个数的最小公倍数等于这两个数的乘积。证明：设两个数为x和y,其最大公约数为
人人文库> 全部分类> 应用文书 > 技术指导

温馨提示

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

最新文档

评论

0/150

提交评论