基于歐幾里德算法的使用

2020-01-26 16:18:44

字體：大中小

供稿：網(wǎng)友

歐幾里德算法稱為輾轉(zhuǎn)相除法，用來求已知m、n兩個自然數(shù)的公因數(shù)。結(jié)合程序說明一下輾轉(zhuǎn)相除的具體情況。

首先看遞歸實現(xià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、對輸入的兩個自然數(shù)m > n取余數(shù)r，使得0<= r < n

2、如果r為0，n即為所求結(jié)果，直接返回

3、r不為0，則賦值m=n,n=r從步驟1開始重新執(zhí)行

　　兩自然數(shù)的公因數(shù)的定義說明了計算結(jié)果產(chǎn)生的條件。如果步驟1中計算出的余數(shù)r = 0，則較小的數(shù)為公因數(shù)。如果r!=0則自然數(shù)m、n的關(guān)系可表示為：m = kn + r（其中k為自然數(shù)），等式可以證明能整除m的任何數(shù)必定能整除n和r；等式進一步可變形為：r = m - kn，說明同時整除m、n的任何數(shù)也必定能整除r。也就是說，能整除m、n的數(shù)的集合與整除n、r的數(shù)的集合相等。所以輾轉(zhuǎn)相除的方法成立。

再發(fā)布一個循環(huán)實現(xiàn)歐幾里德算法的版本。

復(fù)制代碼代碼如下:

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;
 }