[讀書筆記] 歐幾裡得算法與該算法的擴充 C#

歐幾裡得算法 解決的問題是：尋找兩個給定的正整數m和n的最大公約數  
下面是C#代碼的 歐幾裡得算法

 

  public int MaxDivisor(int a, int b)
        ...{
            int max=a>=b?a:b;//得到最大數
            int min=a<b?a:b;//得到最小數
            int r=1;    //余數
            while (r> 0)
            ...{
                r = max % min;  //求模
                max = min;
                min = r;
            }
            return max;
        }

 

 

歐幾裡得算法的擴展，問題描述如下：
尋找兩個給定的正整數m和n的最大公約數d 和兩個整數，使得a*m+b*n=d 

下面是C#的 歐幾裡得算法擴展的代碼

 

 public int MaxDivisorex(int sum1, int sum2, out int a, out int b)
        ...{
            int tmp_b=a = 0;
            int tmp_a=b = 1; //tmp_b tmp_a 是 輔助變量
            int max = sum1 >= sum2 ? sum1 : sum2;//得到最大數
&nbsp;           int min = sum1 < sum2 ? sum1 : sum2;//得到最小數
            int q = 0;  //商
            int r = 1;    //余數
            q = max / min;
            r = max % min;
            max = min;
            min = r;
            while (r > 0)
            ...{
               
                int tmp = tmp_a;
                tmp_a = a;
                a = tmp - q * a;
                tmp = tmp_b;
                tmp_b = b;
                b = tmp - q * b;
                q = max / min;
                r = max % min;
                max = min;
                min = r;
            }
            return max;
        }
結果驗證

int a, b;
            int r = MaxDivisorex(1769, 551, out a, out b);
       MessageBox .Show(string.Format ("{0} * 1769 + {1} *551 = {2}",a,b,(a*1769+b*551)));這個算法不是很復雜，不過要清楚還真是費事，等我可以解釋得很簡單的時候我再解釋好了，現在相當於我自己的讀書筆記。
如果有人能簡單的解釋出來的話，也麻煩留下言。謝謝。。。