算法學習 - 歐幾裡得算法(輾轉相除法)（c++實現）

歐幾裡得算法

歐幾裡得算法也叫輾轉相除法，是求兩個整數最大公約數的算法。

當然也可以求最小公倍數。

算法實現

其實算法的實現原理就是，有整數a b兩個，每次求的一個數字r = a % b，然後把b放到a的位置，把r放到b的位置，遞歸調用。

就是gcd(a, b) { return gcd(b, a%b); }這個樣子的。

結束條件是當 a%b == 0的時候停止。

最大公約數

//
//  main.cpp
//  Euclidean
//
//  Created by Alps on 15/3/28.
//  Copyright (c) 2015年 chen. All rights reserved.
//

#include 

using namespace std;

int gcd(int a, int b){
    if (a%b == 0) {
        return b;
    }
    return gcd(b, a%b);
}

int main(int argc, const char * argv[]) {
    int a = 14, b = 18;
    printf("%d\n",gcd(a,b));
    return 0;
}

上面這個就是求的最大公約數的。其實通過這個也能求的最小公倍數。

最小公倍數

最小公倍數，就是a b的乘積除以它們兩個的最大公約數，就是它們的最小公倍數。代碼如下：

int MinMultiple( int a, int b){
    return (a * b)/gcd(a, b);
}

這樣子就可以了。