最大公约数算法比较

最大公约数算法比较

edit time:2019 03 07

一.代码编写目的

1明确算法的概念和特点。
2通过对问题的分析，设计合理的算法解决问题

二.代码内容

运行最大公约数的常用算法，并进行程序的调式与测试，要求程序设计风格良好，并添加异常处理模块（如输入非法等）

三.分析

通过对最大公约数四种算法的编程实现，以多组随机数作为测试数据，测试相同功能代码在大数据输入情况下不同算法的时间效率，从而比较这四种算法的优劣性。同时在代码实现过程中了解自己写代码时算法优劣的重要性，思考如何提升代码效率及实现效果。

四.算法构造

1. 辗转相除

设两数为a,b设其中a 做被除数,b做除数，temp为余数1、大数放a中、小数放b中；
求a/b的余数；
若temp=0则b为最大公约数；
如果temp!=0则把b的值给a、temp的值给a；
返回第二步
)

2. 穷举法

对两个正整数a,b如果能在区间[a,0]或[b,0]内能找到一个整数temp能同时被a和b所整除，则temp即为最大公约数。
)

3. 更相减损术

第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
)

4. stein

如果An=Bn,那么An(或Bn)Cn是最大公约数,算法结束
如果An=0，Bn是最大公约数，算法结束
如果Bn=0，An是最大公约数，算法结束
设置A1=A、B1=B和C1=1
如果An和Bn都是偶数，则An+1=An/2，Bn+1=Bn/2，Cn+1=Cn2(注意，乘2只要把整数左移一位即可，除2只要把整数右移一位即可)
如果An是偶数，Bn不是偶数，则An+1=An/2，Bn+1=Bn，Cn+1=Cn(很显然啦，2不是奇数的约数)
如果Bn是偶数，An不是偶数，则Bn+1=Bn/2，An+1=An，Cn+1=Cn(很显然啦，2不是奇数的约数)
如果An和Bn都不是偶数，则An+1=|An-Bn|/2，Bn+1=min(An,Bn)，Cn+1=Cn
n加1，转1

五． 算法实现

/**
*auther:@却水
*edit time:2019-03-07
*@xi'an University of science & technology
*@Software engineering 1703 17408070828

*/



#include<iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <Windows.h>
#define N 5000

using namespace std;
//辗转相除法嵌套调用
int divisor(int a,int b)//最大公约数

{
	
	int temp;
	if(a>b)
	{
		temp=a;a=b;b=temp;
	}
	while(b!=0)
	{
		temp=a%b;
		a=b;
		b=temp;
	}
   
	return (a);  
}
int multiple(int a,int b)//最小公倍数
{
	int divisor(int a,int b);
		int temp;
	temp=divisor(a,b);
	return(a*b/temp);
}

int gcd (int a,int b)//递归调用
   
	{
	if(a%b==0)
		return b;
	else
		return gcd(b,a%b);
}


//穷举法
int divisor1(int a,int b)
{ 
	int temp;
	temp=(a>b)?b:a;
	while(temp>0)
	{if(b%temp==0&&a%temp==0)
		break;
	temp--;
	} 
	
return(temp);
}
int multiple1(int a,int b)
{
	int p,q,temp;
	p=(a>b)?a:b;//较大值
	q=(a>b)?b:a;//较小值
	temp=p;
	while(1)
	{
		if(p%q==0)
			break;
		p+=temp;
	}
	
return p;
}
//更相减损术
int gcd1(int a,int b)
{
	int i=0,temp,x;
	while(a%2==0&&b%2==0)//两数都是偶数
	{a/=2;
	b/=2;
	i++;//计算共有几个2
	}
	if(a<b)
	{
		temp=a;
		a=b;
		b=temp;
	}
	while(x)
	{
		x=a-b;
		a=(b>x)?b:x;
		b=(b<x)?b:x;
		if(b==(a-b))
			break;
	}
	if(i=0)
		return b;
	else
		return (int)pow(2,i)*b;//计算更相减损后的乘积

}
//stein
int Stein(unsigned int x,unsigned int y)//返回a,b中的最大公约数

/* return the greatest common divisor of x and y */
{
  int factor = 0;
  int temp;

  if ( x < y )
{
     temp = x;
     x = y;
     y = temp;                      
 }                  
  if ( 0 == y )    
    {
    return 0;            
   }         
   while ( x != y )     
   {     
    if ( x & 0x1 )            
  {//x为偶数              
     if ( y & 0x1 )                   
    {/* when x and y are both odd */                    
        y = ( x - y ) >> 1;                        
          x -= y;                      
   }                     
    else                    
 {/* X为偶数y为奇数 */                       
y >>= 1;                                
       }                 
    }            
    else             
  {/* x为奇数 */              
    if ( y & 0x1 )                    
  {/* x为奇数y为偶数 */                      
   x >>= 1;                             
   if ( x < y )                             
   {                             
     temp = x;                                   
      x = y;                                  
       y = temp;                                 
     }                           
      }                  
   else                     
{/* when x and y are both even */                        
 x >>= 1;                               
  y >>= 1;                              
  ++factor;                              
      }                  
    }            
}        
return ( x << factor );        

}


int gcd_run(int u,int v)//stein递归
{
    if (u == 0) return v;
    if (v == 0) return u;
    // look for factors of 2
    if (~u & 1) // u is even
    {
        if (v & 1) // v is odd
            return gcd(u >> 1, v);
        else // both u and v are even
            return gcd(u >> 1, v >> 1) << 1;
    }
     if (~v & 1) // u is odd, v is even
        return gcd(u, v >> 1);
     // reduce larger argument
    if (u > v)
        return gcd((u - v) >> 1, v);
     return gcd((v - u) >> 1, u);
}
void main()
{
int i,a;
cout<<"请输入测试数据组数"<<endl;
/*
数据异常处理

*/
    int ret;
    ret = scanf("%d",&a);
    while (ret != 1)
    {
        while (getchar() != '\n');
		printf("error input,please again.\n");
        ret = scanf("%d",&a);
    }//直到输入的值为整数
	 
int arr[N] ;
srand((unsigned)time(NULL));//调用time函数来获取随机数
for (i = 0; i< N; i++)
{
arr[i] = rand(); //随机数组


}cout<<"                       检验数据是否随机"<<endl;
for(i=0;i<10;i++)
{
cout<<"                        ********"<<arr[i]<<"********"<<endl;
}
//计时函数
    double time=0;
    double counts=0;
    LARGE_INTEGER nFreq;
	LARGE_INTEGER nBeginTime;
	LARGE_INTEGER nEndTime;
	QueryPerformanceFrequency(&nFreq);

QueryPerformanceCounter(&nBeginTime);
for(i=0;i<2*a;i++){
divisor(arr[i],arr[i+2]);//调用辗转相除法函数
}
QueryPerformanceCounter(&nEndTime);//停止计时
time=(double)(nEndTime.QuadPart-nBeginTime.QuadPart)/(double)nFreq.QuadPart;//计算程序执行时间单位为s
cout<<"辗转相除法(非递归)时间为："<<time*1000<<"ms"<<endl;

QueryPerformanceCounter(&nBeginTime);
for(i=0;i<2*a;i++)
{
gcd(arr[i],arr[i+2]);//辗转相除递归调用

}
QueryPerformanceCounter(&nEndTime);//停止计时
time=(double)(nEndTime.QuadPart-nBeginTime.QuadPart)/(double)nFreq.QuadPart;//计算程序执行时间单位为s
cout<<"辗转相除法(递归)时间为："<<time*1000<<"ms"<<endl;

QueryPerformanceCounter(&nBeginTime);
for(i=0;i<2*a;i++)
{
divisor1(arr[i],arr[i+2]);//穷举法函数调用QueryPerformanceCounter(&nEndTime);//停止计时

}time=(double)(nEndTime.QuadPart-nBeginTime.QuadPart)/(double)nFreq.QuadPart;//计算程序执行时间单位为s
cout<<"穷举法时间为："<<(-time*1000)<<"ms"<<endl;

QueryPerformanceCounter(&nBeginTime);
for(i=0;i<2*a;i++)
{
	gcd1(arr[i],arr[i+2]);//更相减损术算法

}
QueryPerformanceCounter(&nEndTime);//停止计时
time=(double)(nEndTime.QuadPart-nBeginTime.QuadPart)/(double)nFreq.QuadPart;//计算程序执行时间单位为s
cout<<"更相减损术算法时间为："<<time*1000<<"ms"<<endl;

QueryPerformanceCounter(&nBeginTime);
for(i=0;i<2*a;i++)
{
Stein(arr[i],arr[i+2]);//Stein
}
QueryPerformanceCounter(&nEndTime);//停止计时
time=(double)(nEndTime.QuadPart-nBeginTime.QuadPart)/(double)nFreq.QuadPart;//计算程序执行时间单位为s
cout<<"Stein算法时间为："<<time*1000<<"ms"<<endl;

QueryPerformanceCounter(&nBeginTime);
for(i=0;i<2*a;i++)
{i+=1;gcd_run(arr[i],arr[i+2]);//Stein递归调用
}
QueryPerformanceCounter(&nEndTime);//停止计时
time=(double)(nEndTime.QuadPart-nBeginTime.QuadPart)/(double)nFreq.QuadPart;//计算程序执行时间单位为s
cout<<"Stein（递归）时间为："<<time*1000<<"ms"<<endl;
}

七． 个人经验总结

本次实验立足算法的代码实现，侧重于编程及算法构造能力，通过对算法时间的统计，清晰明了看到解决相同问题时不同算法的时间效率，为自己写程序使用最优代码时刻提醒。
收获：熟悉了C语言随机数生成机制及函数调用方法掌握了时间计算的三种函数，如头文件#include<time.h>下的clock函数#include<windows.h>下的gettimeofday(&start, NULL)和QueryPerformanceCounter(&nEndTime)
函数。在随机数生成方面因为以前做课设时不够认真掌握不足，所以在本次程序设计中花费了不少功夫，时间。虽然花费了时间但是收获很大，补上了前面应该学却没学到的东西。在异常处理方面了解到了scanf()返回值的特性，并利用了其函数特性实现了非整数输入的排错功能。
不足之处及改进：冰冻三尺非一日之寒，以前下的功夫不够，以至于编程实践能力欠缺，以后要抓住这样的机会锻炼自己的代码能力及算法设计能力。另外，程序设计方面封装性差，要多学习优秀代码，养成好的编程风格。

打赏