学步园

课程首页地址：http://blog.csdn.net/sxhelijian/article/details/7910565

【项目2扩展——最大公约数】
　　分别用非递归函数和递归函数，用辗转相除法求两个正整数a和b的最大公约数，并体会迭代法和递归法在处理问题上各自的思路。

　　参考解答：

//迭代解法
#include "iostream"
using namespace std;
int gcd(int x, int y);
void main()
{
	int m,n;
	cout<<"输入两个自然数: ";
	cin>>m>>n;
	cout<<"最大公约数:";
	cout<<gcd(m,n)<<endl;
}


int gcd(int a, int b)
{
	int t,r;
	if (a < b) 
		t=a,a=b,b=t;  //其实，这一步可以不要，a和b的大小无所谓
	while (b!= 0)   //如果上面不交换，第一次循环实际就在交换a和b
	{
		r=a%b;
		a=b; 
		b=r;
	}
	return a;
}

//递归解法
#include "iostream"
using namespace std;
int gcd(int x, int y);
void main()
{
	int m,n;
	cout<<"输入两个数字:";
	cin>>m>>n;
	cout<<"最大公约数:";
	cout<<gcd(m,n)<<endl;
}


int gcd(int a, int b)
{
	int t,g;
	//if (a < b) t=a,a=b,b=t;   //无所谓大小
	if (b==0)
		g=a;
	else
		g=gcd(b,a%b);
	return g;
}