服务器之家

服务器之家 > 正文

基于欧几里德算法的使用

时间:2020-11-22 23:15     来源/作者:C语言教程网

欧几里德算法称为辗转相除法,用来求已知m、n两个自然数的公因数。结合程序说明一下辗转相除的具体情况。

首先看递归实现:

复制代码 代码如下:

int getcd(int m,int n)
 {
     if (m < 0 || n <0) {
         return 0;
     }
     if(m < n)
     {
         int t = m;
         m = n;
         n = t;
     }
     if(m % n)
     {
         return getcd(n,(m % n));
     }
     else
     {
         return n;
     }
 }


主要计算过程分为三个步骤:

 

1、对输入的两个自然数m > n取余数r,使得0<= r < n

2、如果r为0,n即为所求结果,直接返回

3、r不为0,则赋值m=n,n=r从步骤1开始重新执行

  两自然数的公因数的定义说明了计算结果产生的条件。如果步骤1中计算出的余数r = 0,则较小的数为公因数。如果r!=0则自然数m、n的关系可表示为:m = kn + r(其中k为自然数),等式可以证明能整除m的任何数必定能整除n和r;等式进一步可变形为:r = m - kn,说明同时整除m、n的任何数也必定能整除r。也就是说,能整除m、n的数的集合与整除n、r的数的集合相等。所以辗转相除的方法成立。
 

再发布一个循环实现欧几里德算法的版本。

复制代码 代码如下:

int getcd2(int m,int n)
 {
     if (m < 0 || n <0) {
         return 0;
     }
     if(m<n)
     {
         int t=m;
         m=n;
         n=t;
     }
     int cd = 1;
     while(1){
         int r = m % n;
         if(0==r)
         {
             cd = n;
             break;
         }
         else {
             m=n;
             n=r;
         }
     }
     return cd;
 }

 

标签:

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
Intellij idea2020永久破解,亲测可用!!!
Intellij idea2020永久破解,亲测可用!!! 2020-07-29
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享 2020-04-07
电视剧《琉璃》全集在线观看 琉璃美人煞1-59集免费观看地址
电视剧《琉璃》全集在线观看 琉璃美人煞1-59集免费观看地址 2020-08-12
最新idea2020注册码永久激活(激活到2100年)
最新idea2020注册码永久激活(激活到2100年) 2020-07-29
返回顶部