|
【问题描述】输入任意两个自然数，求它们的最大公约数。 【样例输入】 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; }
|
|
|
