算法步骤
第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。
使用递归实现，代码如下：
#include <iostream>
using namespace std;
int gcd(int m,int n)
{
if(m==n) return m;
if(m>n) return gcd(n,m-n);
return gcd(m,n-m);
}
int main()
{
int a,b,x=1;
cin>>a>>b;
cout << gcd(a,b)<<endl;
return 0;
} 
全部评论
(0) 回帖