程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 算法學習 - 歐幾裡得算法(輾轉相除法)(c++實現)

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

編輯:C++入門知識

算法學習 - 歐幾裡得算法(輾轉相除法)(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);
}

這樣子就可以了。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved