算法之计算 最大公共因子

最大公共因子

  • 真言

相见不如怀念,怀念不如无线,科技推动发展。

  • 引言

思考真的舒服,亢奋之后真的很累。一个精心设计的算法会让一切变得不同。

  • 思路

求两个数的最大公共因子。
算法如下
算法之计算 最大公共因子
算法之计算 最大公共因子

  • 实验

算法之计算 最大公共因子

算法之计算 最大公共因子

  • 代码

有时候我挺不喜欢递归的,缺点很多,虽然有时候代码比较简单,但是我喜欢非递归---能力的象征,并且直白,利索,干脆,还能更深入的了解算法的执行。
test1.cpp
#include<iostream>
using namespace std;

// function max common multiplier in recursion
int MCM_re(int a,int b);
// function max common multiplier in non-recursion
int MCM_nonre(int a,int b);


int main()
{
	int a,b,i=0;
	while( i<55 )
	{
		a = rand()%1000;
		b = rand()%1000;
		cout<<"a="<<a<<",\t b="<<b<<",\t MCM="<<MCM_re(a,b)<<endl;
		cout<<"a="<<a<<",\t b="<<b<<",\t MCM="<<MCM_nonre(a,b)<<endl;
		cout<<endl;
		i++;
	}
	system("pause");
	return 0;
}



// function max common multiplier in recursion
int MCM_re(int a,int b)
{
	if(a<=0 || b<=0)
	{
		return -1;
	}
	else
	{	
		if(a == b)
		{
			return a;
		}
		else if( a<b )
		{
			if( b%a == 0)
				return a;
			return MCM_re(a,b-a);
		}
		else if( a>b )
		{
			if( a%b == 0)
				return b;
			return MCM_re(a-b,a);
		}
	}
}

// function max common multiplier in non-recursion
int MCM_nonre(int a,int b)
{
	if(a<=0 || b<=0)
	{
		return -1;
	}
	else
	{	
		int max,min;
		while(a>1 && b>1)
		{
			max = a>b?a:b;
			min = a<b?a:b;
			if(max % min ==0)
			{
				return min;
			}
			else 
			{
				a = max - min ;
				b = min ;
			}
		}
		return 1;	
	}
}

test2.cpp
#include<iostream>
using namespace std;

// function max common multiplier in recursion
int MCM_re(int a,int b);
// function max common multiplier in non-recursion
int MCM_nonre(int a,int b);


int main()
{
	int a,b,i=0;
	while( i<55 )
	{
		a = rand()%1000;
		b = rand()%1000;
		cout<<"a="<<a<<",\t b="<<b<<",\t MCM="<<MCM_re(a,b)<<endl;
		cout<<"a="<<a<<",\t b="<<b<<",\t MCM="<<MCM_nonre(a,b)<<endl;
		cout<<endl;
		i++;
	}
	system("pause");
	return 0;
}



// function max common multiplier in recursion
int MCM_re(int a,int b)
{
	if(a <= 0 || b <= 0)
	{
		return -1;
	}
	else
	{
		if(a == b)
		{
			return a;
		}
		else if( a<b )
		{
			if( b%a == 0)
				return a;
			return MCM_re(a,b%a);
		}
		else if( a>b )
		{
			if( a%b == 0)
				return b;
			return MCM_re(a%b,b);
		}
	}
}

// function max common multiplier in non-recursion
int MCM_nonre(int a,int b)
{
	if(a<=0 || b<=0)
	{
		return -1;
	}
	else
	{	
		int max,min;
		while(a>1 && b>1)
		{
			max = a>b?a:b;
			min = a<b?a:b;
			if(max % min ==0)
			{
				return min;
			}
			else 
			{
				a = max % min ;
				b = min ;
			}
		}
		return 1;	
	}
}




算法之计算 最大公共因子

上一篇:VS2013使用GIT时排除NuGet的packages文件夹


下一篇:交换算法的实现