比较4种求最大公约数的方法

一、题目内容
运行最大公约数的常用算法，并进行程序的调试与测试，要求程序设计风格良好，并添加异常处理模块。
二、题目分析
1、写出4种算法，并验证每一种算法的正确性。
2、加入时间函数，算出运行程序的时间。
3、分别用20组，40组，60组1到1000的数对每一种方法进行测试。算出他们的平均运行时间。
三、算法构造
辗转相除法

比较4种求最大公约数的方法
穷举法

更相减损法

Stein算法

四、调试截图：

验证辗转相除法的正确性
验证穷举法的正确性
验证更相减损法的正确性
验证Stein算法的正确性
加入时间函数，并验证其正确性

源代码：

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#define MAX 10000
int divisor(int a,int b)      //辗转相除法
{	
	if(a%b==0)
		return b;
	else
		return divisor(b,a%b);
}
int divisor1(int a,int b)         //穷举法 
{
	int temp;
	temp=(a>b)?b:a;
	while(temp>0)
	{	
		if(a%temp==0&&b%temp==0)
			break;
			temp--;
	}	
	return temp;
}
int divisor2(int a,int b)            //更相减损法
{
	int i=1,temp,x;
	if(a<b)
	{
		temp=a;a=b;	b=temp;
	}
	while(a%2==0&&b%2==0)
	{
		a=a/2;b=b/2;i=i*2;
	}
	while(x)
	{
		x=a-b;
		a=(b>x)?b:x;
		b=(b>x)?x:b;
		if(b==(a-b))
			break;
	}
	if(i==0)
		return b;
	else
		return i*b;
}
int stein(int a,int b)     // stein算法
{
	int factor=0;
	int temp;
	if(a<b)
	{
		temp=a;a=b;	b=temp;
	}
	if(0==b)
	{
		return 0;
	}
	while(a!=b)
	{
		if(a&0x1)
		{
			if(b&0x1)
			{
				b=(a-b)>>1;
				a-=b;
			}
		else 
			b>>=1;
		}
		else
		{
			if(b&0x1)
			{
				a>>=1;
				if(a<b)
				{
					temp=a;	a=b;b=temp;
				}
			}
			else 
			{
				a>>=1;
				b>>=1;
				++factor;
			}
		}
	}
	return (a<<factor);
}
void main()
{
	int time1;    //时间变量，保存程序运行的时间
	int n,j,max,min,select;        
	int array1[MAX],array2[MAX],array3[MAX];   //设定3个数组，第一个数组放第一个数，第二个数组放第二个数，第三个数组放他们的最小公倍数
	clock_t start,finish;
	srand(time(0));         //设定随机数种子
	printf("请输入数据量大小\n");
	scanf("%d",&n);
	printf("请输入测试数据的最大值和最小值：");
	scanf("%d%d",&min,&max);
	for(int i=0;i<n;i++)
	{
		array1[i]=min+rand()%(max-min+1);
		array2[i]=min+rand()%(max-min+1);
	}                                               //往前两个数组存放随机数
	printf("请选择计算的方法：\n");
	printf("1.辗转相除法    2.穷举法\n");
	printf("3.更相减损法    4.Stein算法\n");
	scanf("%d",&select);
	switch(select)
	{
		case 1: 
			start=clock();
			for( j=0;j<n;j++)
			{
				array3[j]=divisor(array1[j],array2[j]);
				printf("%3d  %3d  最大公约数是%3d  最小公倍数是%d\n",array1[j],array2[j],array3[j],array1[j]*array2[j]/array3[j]);
			}
			finish=clock();
			time1=finish-start;
			printf("耗时%d毫秒\n",time1);
			break;
		case 2:
			start=clock();
			for( j=0;j<n;j++)
			{
				array3[j]=divisor1(array1[j],array2[j]);
				printf("%3d  %3d  最大公约数是%3d  最小公倍数是%d\n",array1[j],array2[j],array3[j],array1[j]*array2[j]/array3[j]);
			}
			finish=clock();
			time1=finish-start;
			printf("耗时%d毫秒\n",time1);
			break;
		case 3:
			start=clock();
			for( j=0;j<n;j++)
			{
				array3[j]=divisor2(array1[j],array2[j]);
				printf("%3d  %3d  最大公约数是%3d  最小公倍数是%d\n",array1[j],array2[j],array3[j],array1[j]*array2[j]/array3[j]);
			}
			finish=clock();
			time1=finish-start;
			printf("耗时%d毫秒\n",time1);
			break;
		case 4:
			start=clock();
			for( j=0;j<n;j++)
			{
				array3[j]=stein(array1[j],array2[j]);
				printf("%3d  %3d  最大公约数是%3d  最小公倍数是%d\n",array1[j],array2[j],array3[j],array1[j]*array2[j]/array3[j]);
			}
			finish=clock();
			time1=finish-start;
			printf("耗时%d毫秒\n",time1);
			break;
	}	        
}

比较4种求最大公约数的方法

相关推荐