欧几里德算法

---

【问题描述】输入任意两个自然数，求它们的最大公约数。

【样例输入】

8 40

【样例输出】

8

---

问题解析：

今天我们讲一个数学技巧，欧几里德算法。

（1）欧几里德算法也叫辗转相除法，是指用于计算两个正整数a，b的最大公约数。

（2）算法原理：

对于任意两个正整数a和b，如果a/b = q...r（a除以b的商是q，余数是r），那么a和b的最大公约数等于b和r的最大公约数。

具体的算法过程如下：

（1）a/b = q1...r1。

（2）如果r1=0，则a和b的最大公约数为b。

如果r1≠0，则继续除法运算：b/r1=q2...r2。

（3）如果r2=0，则a和b的最大公约数为r1。

 如果r2≠0，则继续除法运算：r1/r2=q3...r3。

（4）重复执行上述过程，直到能够整除为止。余数为0时的除数就是a和b的最大公约数。

 

所以根据欧几里德算法，求解a和b的最大公约数也就是重复执行除法运算并判断余数是否为0的过程。

---

首先我们使用while循环来模拟上述过程：

【参考程序】

#include

using namespace std;

int main(){

    int a1,b1,a,b,r;

    cin >> a1 >> b1;

    a = max(a1,b1);

    b = min(a1,b1);

    r = a%b;

    while(r!=0) {

        a = b;

        b = r;

        r = a%b;

    }

    cout < b=""><>

    return 0;

}

 

---

上面的算法过程其实也是一个递归的过程，递归关系式为：gcd(a,b)=gcd(b,r)。

接下来我们使用递归算法来模拟上述过程：

【参考程序】

#include

using namespace std;

int gcd(int a,int b){

    int r = a % b;

    if(r == 0){

        return b;

    }else{

        return gcd(b,r);

    }

}

int main(){

    int a1,b1,a,b;

    cin >> a1 >> b1;

    a = max(a1,b1);

    b = min(a1,b1);

    cout < gcd(a,b)=""><>

    return 0;

}