精华内容
下载资源
问答
  • #include <stdio.h> int main() { int a, b, t; scanf("%d %d", &a, &b); t = a<...b%t==0))/*当a,b对t余不能同时为零时,t-1*/ { t--; } printf("%d", t); return 0; }
  • 公约数中最大的一个公约数,称为这几个自然数的最大公约数穷举法(for循环实现) 按照从大(两个整数中较小的数)到小(到最小的整数1)的顺序出第一个能同时整除两个整数的自然数,即为所。 #include...

    简介

    如果有一个自然数a能被自然数b整除,则称a为b的倍数,b为a的约数。几个自然数公有的约数,叫做这几个自然数的公约数。公约数中最大的一个公约数,称为这几个自然数的最大公约数。

    穷举法(for循环实现)

    按照从大(两个整数中较小的数)到小(到最小的整数1)的顺序求出第一个能同时整除两个整数的自然数,即为所求。

    #include<stdio.h>
    int main()
    {
     int max,min,tmp,i;
     printf("请输入第一个数:");
     scanf("%d",&max);
     printf("请输入第二个数:");
     scanf("%d",&min);
     if(min>max)
     {
      tmp=max;
      max=min;
      min=tmp;
     }
     /*穷举法按照从大到小的顺序寻找同时满足两个除法表达式无余数的自然数,自然第一个数就是最大的公约数*/
     for(i=min;i>0;i--)
     {
      if(max%i==0&&min%i==0)
      {
       printf("%d与%d的最小公倍数:%d",max,min,i);
       break;
      }
     } 
     return 0;
    }

    输出:
    在这里插入图片描述

    辗转相除法(while循环实现)

    1、原理:
    欧几里德算法是用来求两个正整数最大公约数的算法。是由古希腊数学家欧几里德在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里德算法。
    扩展欧几里德算法可用于RSA加密等领域。
    假如需要求 18和 12两个正整数的最大公约数,用欧几里德算法,是这样进行的:
    18(被除数)/12(除数)=1(商)- - - -6(余数)
    12/(被除数)/6(除数)=2(商)- - - -0(余数)

    除数余数反复做除法运算,当余数为 0 时,取当前算式除数为最大公约数,所以就得出了 18和 12的最大公约数 6。
    2、算法描述:

    • 将两个正整数存放到变量m和n中
    • 求余数:用较大的m对较小的n求余,将所得余数存放到变量r中
    • 判断余数是否为0:若为0,执行第五步,否则执行第四步
    • 更新m和n:将n的值存放到m,将r的值存放到n中,并转向第(2)步继续循环执行
    • 输出n的当前值,算法结束

    3、算法流程图
    在这里插入图片描述

    4、代码:

    #include<stdio.h>
    int main()
    {
     int m,n,r;
     printf("请输入第一个数:");
     scanf("%d",&m);
     printf("请输入第二个数:");
     scanf("%d",&n);
     r=m%n;
     while(r!=0) 
     {
      m=n;
      n=r;
      r=m%n;
     }
     printf("最大公约数是:%d\n",n);
     return 0;
    }
    

    输出同上

    展开全文
  • 求最大公约数最常见的算法有枚举法和辗转相除法,在这里梳理一下求最大公约数的四种算法。 求最大公约数的四种算法分别是: 1.辗转求余法 2.穷举法 3.更相减损法 4."Stein"算法 1.辗转求余法 算法描述 用...

    求最大公约数最常见的算法有枚举法和辗转相除法,在这里梳理一下求最大公约数的四种算法。

    求最大公约数的四种算法分别是:

    1.辗转求余法

     2.穷举法

     3.更相减损法

     4."Stein"算法

    1.辗转求余法

    算法描述

    用大数除以小数得到余数,然后用前一步的除数除以前一步的余数,相除得到新余数,如此往复,直到余数为0为止,此时的除数就是最大公约数。

    eg:求125和45的最大公约数

    125%45=35

    45%35=10

    35%10=5

    10%5=0

    最大公约数:5

    伪代码描述

    ①嵌套调用

    a=大数;

    b=小数;

    while(t不为0)

    {

       t=a%b;

       a=b;

       b=t;

    }

    ②递归调用

    gcd ( a,b)

    {  

    if( a % b不为0)

            return b;   

    else  

            return gcd(b,a%b);

      }

    辗转相除法流程图

                 

    辗转相除法

    代码实现           

    //辗转相除法1-函数嵌套调用
    int GCD1(int a,int b)
    {
    	int t=0;
    	if( a < b)//交换a,b,保证大数放在a中,小数放在b中
    	{
    		t=a;
    		a=b;
    		b=t;
    	}
    	while(b)//辗转相除  若b(除数)不为0
    	{
    		t=a % b;//求a/b的余数
    		a=b; 
    		b=t;
    	}
    	return a;//返回求得的最大公约数
    }

     

    //辗转相除法2-函数递归调用
    int GCD2(int a,int b)
    {
    	return !(a%b)? b : GCD2(b,a%b); 
    }

    2.穷举法

    算法描述

    从两数中的较小数开始,由大到小列举,直到找到最大公约数为止,中断列举,得到的公约数便是最大公约数。

    eg:求12和的最大公约数

    从8开始列举:

    8能同时被12,8整除吗? N

    7能同时被12,8整除吗? N

    6能同时被12,8整除吗? N

    5能同时被12,8整除吗? N

    4能同时被12,8整除吗? Y!

    最大公约数:4

    伪代码描述

    t=小数;

    while(t>0)

    {

       if(t同时被a和b整除)

           break;

       else

           t--;

    }

    穷举法流程图

    穷举法

    代码实现

    //穷举法
    int GCD3(int a,int b)
    {
    	int t=(a>b)? b:a;//把两个数的较小值赋给t
    	while(t>0)
    	{
    		if(a%t==0&&b%t==0)
    		{
    			break;//只要找到一个数能同时被a,b整除,就终止循环
    		}
    		t--;
    	}
    	return t;
    }

    3.更相减损法

    算法描述:

    任意给定两个正整数,判断它们是否都是偶数。若是,则用2约简;若不是则执行II。

    II 用较大数减较小数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止
    则I中约掉的若干个2与II中等数的乘积就是所求的最大公约数,得到的“等数”就是最大公约数。

    eg:求24和6的最大公约数

    24和6能同时被2整除整除吗? Y   用2约简

    12和3能同时被2整除吗?   N  转到第二步

    12-3=9

    9-3=6

    6-3=3           3=3

    最大公约数:2*3=6

    伪代码描述:

    while(a和b能同时被2整除)

    {

        用2约简a,b

        t++;

    }

     while(a != b)

    {

       更相减损;

    }

    return 2*t*a;

    更相减损法流程图:

    更相减损法

     

    代码实现

    //更相减损法
    int GCD4(int a,int b)
    {
    	int  t=0;
    	while(a%2==0 && b%2==0)//判断a和b能被多少个2整除 
    	{
    		a/=2;
    		b/=2; 
    		t++;
    	}
    
    	 while(a != b) //更相减损 
    	{
    		(a>b)? a-=b : b-=a ;
    	}
    	return t==0? a : 2*t*a;
    } 

    4."Stein"算法

    算法描述:

    计算一个偶数和一个奇数的最大公约数时,可以先将偶数除以2。

    设置A1 = A、B1=B和C1 = 1

    如果An=Bn,An(Bn)是最大公约数,算法结束

    1.如果An和Bn都是偶数,则A(n+1) =An /2,B(n+1) =Bn /2,C(n+1) =Cn *2(乘2把整数左移一位即可,除2把整数右移一位) ,fac++

    2.如果An是偶数,Bn是奇数,则A(n+1) =An /2,B(n+1) =Bn ,C(n+1) =Cn

    3.如果An是奇数,Bn是偶数,则B(n+1) =Bn /2,An+1 =An ,C(n+1) =Cn

    4.如果An和Bn都是奇数,则A(n+1) =|An -Bn|,B(n+1) =min(An,Bn),C(n+1) =Cn

    5.转1

    6. a<<factor是最大公约数,算法结束

    eg:求84和7的最大公约数

    A1=84  B1=7  C1=1

    84是偶数 7是奇数  A2=A1/2=84/2=42       B2=B1=7          C2=C1=1   

    42是偶数 7是奇数  A3=A2/2=41/2=21       B3=B2=7          C3=C2=1

    21是奇数 7是奇数  A4=|A3-B3|=21-7=14     B4=min(A3,B3)=7  C4=C3=1

    14是偶数 7是奇数  A5=A4/2=14/2=7        B5=B4=7          C5=C4=1

    A5=B5=7           

    最大公约数:7

    伪代码描述:

    while(a和b不相等)

    {

       if(a是偶数)

           b是偶数?  a,b右移一位 : (a右移一位,fac++)

       if(a是奇数)

           b是奇数? (a=|a-b|,b=min(a,b);) : b右移一位

    }

    最大公约数=a<<factor;

    流程图描述

    Stein算法

    代码实现

    //Stein算法1-非递归 
    int GCD5(int a,int b)
    {
    	int factor = 0,t;
    	if(a<b)//保证a存放大数 
    	{
    		t=a;
    		a=b;
    		b=t;
    	}
    	while(a!=b)
    	{
    		if(a%2)//当a是奇数时
    		{
    			if(b%2)//当a和b都是奇数时 
    			{
    				b=(a-b)>>1;
    				a-=b;
    			}
    			else//当a是奇数b是偶数时 
    			{
    				b>>=1;
    			}
    		}
    		else //当a是偶数时 
    		{
    			if(b%2)//当a是偶数b是奇数时 
    			{
    				a>>=1;
    				 if(a < b)
    				 {
    				 	t=a;
    				 	a=b;
    				 	b=t;
    				 }
    			}
    			else//当a和b都是偶数时 
    			{
    				a>>=1;
    				b>>=1;
    				++factor;
    			}
    		
    		}
    	}
    	return a<<factor;
    } 
    //Stein算法1-非递归 
    int GCD5(int a,int b)
    {
    	int factor = 0,t;
    	if(a<b)//保证a存放大数 
    	{
    		t=a;
    		a=b;
    		b=t;
    	}
    	if(!b)
    	{
    		return 0;
    	}
    	while(a!=b)
    	{
    		if(a%2)//当a是奇数时
    		{
    			if(b%2)//当a和b都是奇数时 
    			{
    				b=(a-b)>>1;
    				a-=b;
    			}
    			else//当a是奇数b是偶数时 
    			{
    				b>>=1;
    			}
    		}
    		else //当a是偶数时 
    		{
    			if(b%2)//当a是偶数b是奇数时 
    			{
    				a>>=1;
    				 if(a < b)
    				 {
    				 	t=a;
    				 	a=b;
    				 	b=t;
    				 }
    			}
    			else//当a和b都是偶数时 
    			{
    				a>>=1;
    				b>>=1;
    				++factor;
    			}
    		
    		}
    	}
    	return a<<factor;
    } 

    最后一种算法本人还没有太理解,所以可能代码本身还存在一定的问题,仅供参考......

    附:程序源代码

    #include<stdio.h>
    #include<stdlib.h>
    #include<time.h>
    #include<iostream>
    using namespace std;
    
    //辗转相除法1-函数嵌套调用
    int GCD1(int a,int b)
    {
    	int t=0;
    	if( a < b)//交换a,b,保证大数放在a中,小数放在b中
    	{
    		t=a;
    		a=b;
    		b=t;
    	}
    	while(b)//辗转相除  若b(除数)不为0
    	{
    		t=a % b;//求a/b的余数
    		a=b; 
    		b=t;
    	}
    	return a;//返回求得的最大公约数
    }
    
    //辗转相除法2-函数递归调用
    int GCD2(int a,int b)
    {
    	return !(a%b)? b : GCD2(b,a%b); 
    }
    
    //穷举法
    int GCD3(int a,int b)
    {
    	int t=(a>b)? b:a;//把两个数的较小值赋给t
    	while(t>0)
    	{
    		if(a%t==0&&b%t==0)
    		{
    			break;//只要找到一个数能同时被a,b整除,就终止循环
    		}
    		t--;
    	}
    	return t;
    }
    
    //更相减损法
    int GCD4(int a,int b)
    {
    	int  t=0;
    	while(a%2==0 && b%2==0)//判断a和b能被多少个2整除 
    	{
    		a/=2;
    		b/=2; 
    		t++;
    	}
    
    	 while(a != b) //更相减损 
    	{
    		(a>b)? a-=b : b-=a ;
    	}
    	return t==0? a : 2*t*a;
    } 
    
    //Stein算法1-非递归 
    int GCD5(int a,int b)
    {
    	int factor = 0,t;
    	if(a<b)//保证a存放大数 
    	{
    		t=a;
    		a=b;
    		b=t;
    	}
    	if(!b)
    	{
    		return 0;
    	}
    	while(a!=b)
    	{
    		if(a%2)//当a是奇数时
    		{
    			if(b%2)//当a和b都是奇数时 
    			{
    				b=(a-b)>>1;
    				a-=b;
    			}
    			else//当a是奇数b是偶数时 
    			{
    				b>>=1;
    			}
    		}
    		else //当a是偶数时 
    		{
    			if(b%2)//当a是偶数b是奇数时 
    			{
    				a>>=1;
    				 if(a < b)
    				 {
    				 	t=a;
    				 	a=b;
    				 	b=t;
    				 }
    			}
    			else//当a和b都是偶数时 
    			{
    				a>>=1;
    				b>>=1;
    				++factor;
    			}
    		
    		}
    	}
    	return a<<factor;
    } 
    
    
    //Stein算法2-递归
    int GCD6(int a,int b)
    {
    	int t;
        if(a < b){
            t = a;
            a = b;
            b = t;
        }
        if(!b) return a;
        if(a % 2 == 0 && b % 2 == 0)
    	{
           return 2 * GCD6(a / 2, b / 2);
        } 
    	else if(a % 2 == 0 && b % 2 != 0)
    	{
            return GCD6(a / 2, b);
        } 
    	else if(a % 2 != 0 && b % 2 == 0)
    	{
            return GCD6(a, b / 2);
        } 
    	else
    	{
            return GCD6(a-b, b);
    	}
    } 
     
    
    int main(void)
    {
    	int tMax;//tMax存放最大公约数 
    	int c1,s;//c存放算法操作选择符,s存放数据规模(要测试多少组数据) 
    	int p,q;//p、q存放要测试的每组数据区间的最大最小值 
    	clock_t start,end;//start和end用来计算程序运行时间
    	double cost;//cost存放一段算法的运行时间
    	int flag=0,c2;//判断是否继续测试 
    	double avgcost=0;//计算平均运行时间
    	int cnt=0;//循环累加器 
    	while(1)
    	{
    		printf("请输入要测试多少组数据:") ;
    		scanf("%d",&s);
    		int data[s][2];
    		printf("请输入要测试的每组数据的范围:") ;
    		scanf("%d%d",&p,&q);
    		
    		printf("利用随机数生成的数组:\n");
    		//打印随机生成的二维数组 
    		for(int i=0;i<s;i++)
    		{
    			for(int j=0;j<2;j++)
    			{
    				data[i][j]=rand() % (q - p + 1) + p;//公式,求a到b之间的随机数 rand() % (b - a + 1) + a;
    				//printf("%5d",a[i][j]);	
    			}
    			//printf("\n");		
    		}  
    	
    		//算法性能测试 
    		printf("请选择要测试的算法:\n");
    		printf("1.辗转相除(嵌套调用)\n2.辗转相除(递归调用)\n3.穷举法\n4.更相减损法\n5.Stein算法(非递归)\n6.Stein算法(递归)\n");
    		scanf("%d",&c1);
    		start=clock();
    		for(int i=0;i<s;i++)
    		{	
    			switch(c1){
    				case 1:tMax=GCD1( data[i][0] , data[i][1] );	break; 
    				case 2:tMax=GCD2( data[i][0] , data[i][1] );	break;
    				case 3:tMax=GCD3( data[i][0] , data[i][1] );	break;
    				case 4:tMax=GCD4( data[i][0] , data[i][1] );	break;
    				case 5:tMax=GCD5( data[i][0] , data[i][1] );	break;
    				case 6:tMax=GCD6( data[i][0] , data[i][1] );	break;
    				default: printf("输入错误!\n");	break;
    			}
    			printf("%3d和%3d:%3d\n",data[i][0],data[i][1],tMax);  		
    		} 			
    		end=clock();
    		cost=double(end-start)/CLOCKS_PER_SEC;
    		printf("算法%d:\t数据规模:%d\t数据范围:[%d,%d]\t运行时间:%f secs\n",c1,s,p,q,cost);
    		avgcost=(avgcost+cost)/++cnt;
    		printf("算法%d平均运行时间:%f secs\n",c1,avgcost);
    		printf("按1继续测试,按2退出:");
    		scanf("%d",&c2); 
    		if(c2-1)
    		{
    			break;
    		}
    	}
    	return 0;
    }

     

    展开全文
  • 求最大公约数的算法多以求两个正整数的最大公约数为例加以说明,并且求两个正整数的最大公约数的方法有辗转相除法、穷举法、更相减损法和Stein算法。最大公约数概念如下:如果有一个自然数a能被自然数b整除,则称a为...

    第一次上机作业 程序的算法设计
    1.题目分析
    求最大公约数的算法多以求两个正整数的最大公约数为例加以说明,并且求两个正整数的最大公约数的方法有辗转相除法、穷举法、更相减损法和Stein算法。最大公约数概念如下:如果有一个自然数a能被自然数b整除,则称a为b的倍数,b为a的约数。几个自然数公有的约数,叫做这几个数的公约数。公约数中最大的一个公约数,称为这几个数的最大公约数。
    一.辗转相除法(又名欧几里德法)C语言中用于计算两个正整数a,b的最大公约数和最小公倍数,实质它依赖于下面的定理:
    a b=0

    gcd(a,b) =

    gcd(b,a mod b) b!=0
    根据这一定理可以采用函数嵌套调用和递归调用形式进行求两个数的最大公约数和最小公倍数,现分别叙述如下:
    ①函数嵌套调用
    其算法过程为: 前提:设两数为a,b设其中a 做被除数,b做除数,temp为余数
    1、大数放a中、小数放b中;
    2、求a/b的余数;
    3、若temp=0则b为最大公约数;
    4、如果temp!=0则把b的值给a、temp的值给a;
    5、返回第二步;
    启示:请注意算法中变量数值之间的相互交换方法、如何取模、怎样进行自定义函数及主调函数与被调函数间的相互关系,函数参数的定义及对应关系特点,利用控制语句如何实现。

    ②函数递归调用
    启示:采用递归调用法要注意递归终止条件的描述,只有找到递归变化的规律,才能有效地解决问题。
    二.穷举法(利用数学定义)
    穷举法(也叫枚举法)穷举法求两个正整数的最大公约数的解题步骤:从两个数中较小数开始由大到小列举,直到找到公约数立即中断列举,得到的公约数便是最大公约数 。
    ①定义1:对两个正整数a,b如果能在区间[a,0]或[b,0]内能找到一个整数temp能同时被a和b所整除,则temp即为最大公约数。
    ②定义2:对两个正整数a,b,如果若干个a之和或b之和能被b所整除或能被a所整除,则该和数即为所求的最小公倍数。
    三.更相减损法
    更相减损术,是出自《九章算术》的一种求最大公约数的算法,它原本是为约分而设计的,但它适用于任何需要求最大公约数的场合。《九章算术》是中国古代的数学专著,其中的“更相减损术”可以用来求两个数的最大公约数,即“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。以等数约之。”
    翻译成现代语言如下:
    第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。
    第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。
    则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
    其中所说的“等数”,就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。
    四.Stein算法
    Stein算法由J. Stein 1961年提出,这个方法也是计算两个数的最大公约数。来研究一下最大公约数的性质,发现有 gcd( kx,ky ) = kgcd( x,y ) 这么一个非常好的性质。试取 k=2,则有 gcd( 2x,2y ) = 2 * gcd( x,y )。很快联想到将两个偶数化小的方法。那么一奇一个偶以及两个奇数的情况如何化小呢?
    先来看看一奇一偶的情况: 设有2x和y两个数,其中y为奇数。因为y的所有约数都是奇数,所以 a = gcd( 2x,y ) 是奇数。根据2x是个偶数不难联想到,a应该是x的约数。我们来证明一下:(2x)%a=0,设2x=n
    a,因为a是奇数,2x是偶数,则必有n是偶数。又因为 x=(n/2)*a,所以 x%a=0,即a是x的约数。因为a也是y的约数,所以a是x和y的公约数,有 gcd( 2x,y ) <= gcd( x,y )。因为gcd( x,y )明显是2x和y的公约数,又有gcd( x,y ) <= gcd( 2x,y ),所以 gcd( 2x,y ) = gcd( x,y )。至此,我们得出了一奇一偶时化小的方法。
    再来看看两个奇数的情况:设有两个奇数x和y,不妨设x>y,注意到x+y和x-y是两个偶数,则有 gcd( x+y,x-y ) = 2 * gcd( (x+y)/2,(x-y)/2 ),那么 gcd( x,y ) 与 gcd( x+y,x-y ) 以及 gcd( (x+y)/2,(x-y)/2 ) 之间是不是有某种联系呢?为了方便设 m=(x+y)/2 ,n=(x-y)/2 ,容易发现 m+n=x ,m-n=y 。设 a = gcd( m,n ),则 m%a=0,n%a=0 ,所以 (m+n)%a=0,(m-n)%a=0 ,即 x%a=0 ,y%a=0 ,所以a是x和y的公约数,有 gcd( m,n )<= gcd(x,y)。再设 b = gcd( x,y )肯定为奇数,则 x%b=0,y%b=0 ,所以 (x+y)%b=0 ,(x-y)%b=0 ,又因为x+y和x-y都是偶数,跟前面一奇一偶时证明a是x的约数的方法相同,有 ((x+y)/2)%b=0,((x-y)/2)%b=0 ,即 m%b=0 ,n%b=0 ,所以b是m和n的公约数,有 gcd( x,y ) <= gcd( m,n )。所以 gcd( x,y ) = gcd( m,n ) = gcd( (x+y)/2,(x-y)/2 )。
    整理一下,对两个正整数 x>y :
    1.均为偶数 gcd( x,y ) =2gcd( x/2,y/2 );
    2.均为奇数 gcd( x,y ) = gcd( (x+y)/2,(x-y)/2 );
    2.x奇y偶 gcd( x,y ) = gcd( x,y/2 );
    3.x偶y奇 gcd( x,y ) = gcd( x/2,y ) 或 gcd( x,y )=gcd( y,x/2 );
    现在已经有了递归式,还需要再找出一个退化情况。注意到 gcd( x,x ) = x ,就用这个。
    2.算法构造
    绘制出所有算法的流程图以及N-S盒图。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    3.算法实现
    一、1.辗转相除法中的函数嵌套调用

    #include "stdio.h"    /*输入输出类头文件*/
    #include <windows.h>
    int divisor (int a,int b)    /*自定义函数求两数的最大公约数*/
    {
      int  temp;          /*定义整型变量*/
      if(a<b)             /*通过比较求出两个数中的最大值和最小值*/
        { temp=a;a=b;b=temp;} /*设置中间变量进行两数交换*/
       while(b!=0)           /*通过循环求两数的余数,直到余数为0*/
        {
          temp=a%b;
          a=b;              /*变量数值交换*/
          b=temp;
        }
      return (a);            /*返回最大公约数到调用函数处*/ 
    }
    int main()  
    {
        int z[2][20] = {{1,1},{31,43,46,65,43,58,55,54,55,56,98,78,96,54,78,85,57,12,36,15}};
    	int i = 0;
    	double run_time;
    	LARGE_INTEGER time_start;	//开始时间
    	LARGE_INTEGER time_over;	//结束时间
    	double dqFreq;		//计时器频率
    	LARGE_INTEGER f;	//计时器频率
        int m,n,t1,t2;     /*定义整型变量*/
     QueryPerformanceFrequency(&f);
    	dqFreq=(double)f.QuadPart;
    	QueryPerformanceCounter(&time_start);	//计时开始
    	for( i = 0; i < 20; i++){
    		t1 = divisor (z[0][i],z[1][i]);
    	printf("The higest common divisor is %d\n",t1);
    	}
    	QueryPerformanceCounter(&time_over);	//计时结束
    	run_time=1000000*(time_over.QuadPart-time_start.QuadPart)/dqFreq;
    	//乘以1000000把单位由秒化为微秒,精度为1000 000/(cpu主频)微秒
    	printf("\nrun_time:%fus\n",run_time);
    	return 0;
    }
    

    2.辗转相除法中的函数递归调用

    #include "stdio.h"
    #include <windows.h>
    int gcd (int a,int b)
    { 
    	if(a%b==0)
    		return b;
    	else
     		return gcd(b,a%b);
      }
    int main()
    {   
    intz[2][20] ={{1,1},{31,43,46,65,43,58,55,54,55,56,98,78,96,54,78,85,57,12,36,15}};
    	int i = 0;
    	double run_time;
    	LARGE_INTEGER time_start;	//开始时间
    	LARGE_INTEGER time_over;	//结束时间
    	double dqFreq;		//计时器频率
    	LARGE_INTEGER f;	//计时器频率
    	int m,n,t1;
    	getch(); 
       QueryPerformanceFrequency(&f);
    	dqFreq=(double)f.QuadPart;
    	QueryPerformanceCounter(&time_start);	//计时开始
    	for( i = 0; i < 20; i++){
    		t1 = gcd(z[0][i],z[1][i]);
    		printf("The higest common divisor is %d\n",t1);
    	}
    	QueryPerformanceCounter(&time_over);	//计时结束
    	run_time=1000000*(time_over.QuadPart-time_start.QuadPart)/dqFreq;
    	//乘以1000000把单位由秒化为微秒,精度为1000 000/(cpu主频)微秒
    	printf("\nrun_time:%fus\n",run_time);
    	return 0;
    }
    

    二、1.穷举法定义1

    #include "stdio.h"
    #include <windows.h>
    int divisor (int a,int b) /*自定义函数求两数的最大公约数*/
    {
        int  temp;          /*定义义整型变量*/
        temp=(a>b)?b:a;    /*采种条件运算表达式求出两个数中的最小值*/
        while(temp>0)     
        {
           if (a%temp==0&&b%temp==0) /*只要找到一个数能同时被a,b所整除,则中止循环*/
              break;    
           temp--;      /*如不满足if条件则变量自减,直到能被a,b所整除*/
        }
      return (temp); /*返回满足条件的数到主调函数处*/
    }
    int main()
    {  int z[2][20] = {{1,1},{31,43,46,65,43,58,55,54,55,56,98,78,96,54,78,85,57,12,36,15}};
    	int i = 0;
    	double run_time;
    	LARGE_INTEGER time_start;	//开始时间
    	LARGE_INTEGER time_over;	//结束时间
    	double dqFreq;		//计时器频率
    	LARGE_INTEGER f;	//计时器频率
     int m,n,t1;
     getch();
     QueryPerformanceFrequency(&f);
    	dqFreq=(double)f.QuadPart;
    	QueryPerformanceCounter(&time_start);	//计时开始
    	for( i = 0; i < 20; i++){
    		t1 = divisor(z[0][i],z[1][i]);
    		printf("The higest common divisor is %d\n",t1);
    	}
    	QueryPerformanceCounter(&time_over);	//计时结束
    	run_time=1000000*(time_over.QuadPart-time_start.QuadPart)/dqFreq;
    	//乘以1000000把单位由秒化为微秒,精度为1000 000/(cpu主频)微秒
    	printf("\nrun_time:%fus\n",run_time);
    	return 0;
    }
    

    二、2.穷举法中的定义

    #include "stdio.h"
    #include <windows.h>
    int multiple(int a,int b)
    {
      int p,q,temp;
      p=(a>b)?a:b;   /*求两个数中的最大值*/
      q=(a>b)?b:a;  /*求两个数中的最小值*/
      temp=p;      /*最大值赋给p为变量自增作准备*/
      while(1)   /*利用循环语句来求满足条件的数值*/
      {
        if(p%q==0)
          break;  /*只要找到变量的和数能被a或b所整除,则中止循环*/
        p+=temp;   /*如果条件不满足则变量自身相加*/
      }
      return  (p);
    }
    int main()
    {int z[2][20] = {{1,1},{31,43,46,65,43,58,55,54,55,56,98,78,96,54,78,85,57,12,36,15}};
    	int i = 0;
    	double run_time;
    	LARGE_INTEGER time_start;	//开始时间
    	LARGE_INTEGER time_over;	//结束时间
    	double dqFreq;		//计时器频率
    	LARGE_INTEGER f;	//计时器频率
     int m,n,t2;
     getch();
     QueryPerformanceFrequency(&f);
    	dqFreq=(double)f.QuadPart;
    	QueryPerformanceCounter(&time_start);	//计时开始
    		for( i = 0; i < 20; i++){
    		t2 = multiple (z[0][i],z[1][i]);
    		printf("The lowest common multiple is %d\n", t2);
    	}
    	QueryPerformanceCounter(&time_over);	//计时结束
    	run_time=1000000*(time_over.QuadPart-time_start.QuadPart)/dqFreq;
    	//乘以1000000把单位由秒化为微秒,精度为1000 000/(cpu主频)微秒
    	printf("\nrun_time:%fus\n",run_time);
    	return 0;
    }
    

    三、更相减损法

    #include "stdio.h"
    #include <windows.h>
    #include<math.h>
    int gcd(int m,int n)
    {
    	int i=0,temp,x;
    	while(m%2==0 && n%2==0)  //判断m和n能被多少个2整除
    	{
    		m/=2;
    		n/=2;
    		i+=1;
    	}
    	if(m<n)     //m保存大的值
    	{
    		temp=m;
    		m=n;
    		n=temp;
    	}
    	while(x)
    	{
    		x=m-n;
    		m=(n>x)?n:x;
    		n=(n<x)?n:x;
    		if(n==(m-n))
    			break;
    	}
    	if(i==0)
    		return n;
    	else 
    		return (int)pow(2,i)*n;
    }
    int main()
    {
    	 int z[2][20] = {{1,1},{31,43,46,65,43,58,55,54,55,56,98,78,96,54,78,85,57,12,36,15}};
    	int i = 0;
    	double run_time;
    	LARGE_INTEGER time_start;	//开始时间
    	LARGE_INTEGER time_over;	//结束时间
    	double dqFreq;		//计时器频率
    	LARGE_INTEGER f;	//计时器频率
    	int m,n,t1;
     getch();
      QueryPerformanceFrequency(&f);
    	dqFreq=(double)f.QuadPart;
    	QueryPerformanceCounter(&time_start);	//计时开始
    	for( i = 0; i < 20; i++){
    		t1 = gcd (z[0][i],z[1][i]);
    		printf("The higest common divisor is %d\n",t1);
    	}
    	QueryPerformanceCounter(&time_over);	//计时结束
    	run_time=1000000*(time_over.QuadPart-time_start.QuadPart)/dqFreq;
    	//乘以1000000把单位由秒化为微秒,精度为1000 000/(cpu主频)微秒
    	printf("\nrun_time:%fus\n",run_time);
    	return 0;
    } 
    

    四、1.Stein算法函数递归调用

    #include "stdio.h"
    #include <windows.h>
    int gcd(int u,int v)
    {
    	if(u==0)	return v;
    	if(v==0)	return u;
    	if(~u&1)
    	{
    		if(v&1)
    		return gcd(u>>1,v);
    		else
    		return gcd(u>>1,v>>1)<<1;
    	}
    	if(~v&1)
    		return gcd(u,v>>1);
    	if(u>v)
    		return gcd((u-v)>>1,v);
    	return gcd((v-u)>>1,u);
    }
    int main()
    {
    int z[2][20] = {{1,1},{31,43,46,65,43,58,55,54,55,56,98,78,96,54,78,85,57,12,36,15}};
    	int i = 0;
    	double run_time;
    	LARGE_INTEGER time_start;	//开始时间
    	LARGE_INTEGER time_over;	//结束时间
    	double dqFreq;		//计时器频率
    	LARGE_INTEGER f;	//计时器频率
    	int m,n,t2;
    getch();
      QueryPerformanceFrequency(&f);
    	dqFreq=(double)f.QuadPart;
    	QueryPerformanceCounter(&time_start);	//计时开始
    	for( i = 0; i < 20; i++){
    		t2=  gcd(z[0][i],z[1][i]);
    		printf("The higest common divisor is %d\n",t2);
    	}
    	QueryPerformanceCounter(&time_over);	//计时结束
    	run_time=1000000*(time_over.QuadPart-time_start.QuadPart)/dqFreq;
    	//乘以1000000把单位由秒化为微秒,精度为1000 000/(cpu主频)微秒
    	printf("\nrun_time:%fus\n",run_time);
    	return 0;
    } 
    

    2.Stein算法函数函数非递归调用

    #include "stdio.h"
    #include <windows.h>
    int Stein(int x,int y)
      /*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)
    		{
    		if(y&0x1)
    		{
    			y=(x-y)>>1;
    			x-=y;
    		}
    		else
    		{
    			y>>=1;
    		}
    	 } 
    else
     {
     	if(y&0x1)
    	{
    	 	x>>=1;
    		if(x<y)
    	 	{
    	 	temp=x;
    	 	x=y;
    	 	y=temp;
    		}
    	}
    	else
    	{
    	 	x>>=1;
    		y>>=1;
    	 	++factor;
    		}	
     	}
    	} 
    return (x<<factor);
    }
    int main()
    {
    	int z[2][20] = {{1,1},{31,43,46,65,43,58,55,54,55,56,98,78,96,54,78,85,57,12,36,15}};
    	int i = 0;
    	double run_time;
    	LARGE_INTEGER time_start;	//开始时间
    	LARGE_INTEGER time_over;	//结束时间
    	double dqFreq;		//计时器频率
    	LARGE_INTEGER f;	//计时器频率
    	int m,n,t2;
    getch();
      QueryPerformanceFrequency(&f);
    	dqFreq=(double)f.QuadPart;
    	QueryPerformanceCounter(&time_start);	//计时开始
    	for( i = 0; i < 20; i++){
    		t2 = Stein(z[0][i],z[1][i]);
    		printf("The higest common divisor is %d\n",t2);
    	}
    	QueryPerformanceCounter(&time_over);	//计时结束
    	run_time=1000000*(time_over.QuadPart-time_start.QuadPart)/dqFreq;
    	//乘以1000000把单位由秒化为微秒,精度为1000 000/(cpu主频)微秒
    	printf("\nrun_time:%fus\n",run_time);
    	return 0;
    } 
    

    4.调试、测试及运行结果
    测试与调试:
    先以辗转相除法中函数嵌套调用(版本1)求取最大公约数为例:如图1;
    在这里插入图片描述
    图1:辗转相除法中函数嵌套调用(版本1)求取最大公约数程序运行结果
    这个时候,需要人为输入一组数据,来测试程序运行时间较为复杂,如果为提高试验的精确性,需要输入20组数据加以验证则显得极为麻烦,所以采取了便捷省力的方法,那就是引入了二维数组的概念。
    再以辗转相除法中函数嵌套调用(版本2)求取最大公约数为例:
    这个时候我引入了二维数组,并以加入了20组数据,能方便的得出20组测试数据的情况下的运行时间。如图2;
    在这里插入图片描述
    图2:辗转相除法中函数嵌套调用(版本2)采用20组数据测试,求取最大公约数程序运行结果
    附加说明:由于以微秒为单位计时比毫秒计时更为精确,故本实验采用了更为精确的以为妙为单位的计时。
    运行结果:
    辗转相除法中函数嵌套调用(版本1)求取最大公约数程序运行结果如图3;
    在这里插入图片描述
    图3:辗转相除法中函数嵌套调用(版本1)求取最大公约数程序运行结果
    辗转相除法中函数嵌套调用(版本2)采用20组数据测试,求取最大公约数程序运行结果如图4:;

    在这里插入图片描述
    图4;辗转相除法中函数嵌套调用(版本2)采用20组数据测试,求取最大公约数程序运行结果
    辗转相除法中函数递归调用采用20组数据测试,求取最大公约数程序运行结果如图5;
    在这里插入图片描述
    图5:辗转相除法中函数递归调用采用20组数据测试,求取最大公约数程序运行结果

    穷举法中采用定义1使用20组数据测试,求取最大公约数程序运行结果如图6;
    在这里插入图片描述
    图6:穷举法中采用定义1使用20组数据测试,求取最大公约数程序运行结果
    穷举法中采用定义2求取最小公倍数程序运行结果如图7;
    在这里插入图片描述
    图7:穷举法中采用定义2求取最小公倍数程序运行结果
    Stein函数递归调用中采用20组数据测试求取最小公倍数程序运行结果如图8;
    在这里插入图片描述

    图8:Stein函数递归调用中采用20组数据测试求取最小公倍数程序运行结果
    Stein函数非递归调用中采用20组数据测试求取最小公倍数程序运行结果如图9;
    在这里插入图片描述
    图9:Stein函数非递归调用中采用20组数据测试求取最小公倍数程序运行结果
    5.经验归纳
    刚开始做这个实验时,起初使用简单的想法,每次输入一组数据来测试程序运行时间,五种算法输入相同的20组数据。但是,这种想法不仅有悖于程序设计方法学中便捷高效的思想,还为自己增加了计算所造成的负担。因此对程序进行了改编,给五种算法引入二维数组来进行测试程序运行时间。还有,在测试程序运行时间时需要自己查资料,学习如何获取程序运行时间方面的知识,在调用相关方面函数时,一定要记得添加与之相关的头文件。此外辗转相除法中函数递归调用、辗转相除法中函数递归调用、辗转相除法、Stein函数递归调用求取最大公约数及测试程序运行时间没出现问题,但穷举法1及Stein函数非递归调用求取最大公约数在引用20组数据方面出现了问题,即使运行结果体现了利用20组数据测试程序运行时间的效果,但还是存在着不严谨的地方,并没有正确的利用算法获取最大公约数。这也是以后在编程时应注意的问题,更应该思考着解决这些问题的方法、精益求精。
    1.注意算法中变量数值之间的相互交换方法、如何取模、怎样进行自定义函数及主调函数与被调函数间的相互关系,函数参数的定义及对应关系特点,利用控制语句如何实现。
    2.采用递归调用法要注意递归终止条件的描述,只有找到递归变化的规律,才能有效地解决问题。
    3.根据数学定义求任意两个正整数的最大公约数和最小公倍数,相对辗转相除法来说,易懂,容易被接受,但要注意强制退出循环过程的条件、变量的特点及控制语句的使用。
    4.欧几里得算法在处理较小数字时优势是明显的,但对于大整数时,高精度的整除和取余运算就显得非常复杂,所以Stein算法的优点就在于只需要进行移位(位运算)和减法操作,处理高精度GCD问题时相对简便。

    展开全文
  • C语言求两数最大公约数的四种算法

    千次阅读 2019-03-12 20:07:28
    实验目的 ...两数的最大公约数,常用的算法有辗转相除法、穷举法、更相减损法、Stein算法等。将每一种算法用一个函数实现,再在主函数中用switch()语句调用任意一种算法,并且在主函数中利用ra...

    实验目的

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

    实验内容

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

    题目分析

    求两数的最大公约数,常用的算法有辗转相除法、穷举法、更相减损法、Stein算法等。将每一种算法用一个函数实现,再在主函数中用switch()语句调用任意一种算法,并且在主函数中利用rand()、srand()函数来产生随机函数进行每种算法平均运行时间的测试。

    算法构造

    辗转相除法

    算法过程: 前提设两数为a,b设其中a 做被除数,b做除数,temp为余数
    1、大数放a中、小数放b中;
    2、求a/b的余数;
    3、若temp=0则b为最大公约数;
    4、如果temp!=0则把b的值给a、temp的值给a;
    5、返回第二步。
    流程图
    图1.辗转相除法算法流程图
    代码

     int divisor1(int a,int b)  //自定义函数求两数的最大公约数
    {
    	int temp;       //定义整型变量
    	if(a<b)         //通过比较求出两数中的最大数和最小数
    	{
    		temp=a;     //设置中间变量进行两数交换
    		a=b;
    		b=temp;
    	}
    	while(b!=0)     //通过循环求两数的余数,直到余数为0
    	{
    		temp=a%b;
    		a=b;        //变量数值交换
    		b=temp;
    	}
    return (a);         //返回最大公约数到调用函数处
    }
    //辗转相除法(2.函数递归调用)
    int divisor2(int a,int b)
    {
    	if(a%b==0)     //若a,b取余后余数为0,则返回最大公约数b
    		return b;
    	else
    		return divisor2(b,a%b); //否则递归调用,继续取余
    }
    

    穷举法

    算法过程:对两个正整数a,b如果能在区间[a,0]或[b,0]内能找到一个整数temp能同时被a和b所整除,则temp即为最大公约数。
    流程图
    在这里插图2.穷举法算法流程图入图片描述
    代码

    int divisor3(int a,int b)
    {
    	int temp;
    	temp=(a>b)?b:a;  //采用条件运算表达式求出两数中的最小值
    	while(temp>0)
    	{
    		if(a%temp==0&&b%temp==0)   //只要能找到一个数能同时被a,b整除,则中止循环
    			break;
    		temp--;     //如不满足if条件则变量自减,直到能被a,b整除
    	}
    	return (temp);
    }
    

    更相减损法

    算法过程:第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。
    第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。
    则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。其中所说的“等数”,就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。
    流程图
    在这里插入图片描述
    代码

     int divisor4(int m,int n)
    {	int i=0,temp,x;
    	while(m%2==0&&n%2==0)  //判断a,b是否都是偶数,若是则用2约简
    	{
    		m/=2;
    		n/=2;
    		i+=1;  //约简2的个数
    	}
    	if(m<n)  //a保存最大值
    	{
    		temp=m;
    		m=n;
    		n=temp;
    	}
    	while(x)       //当x不为0时
    	{
    		x=m-n;           //较大数减较小数
    		m=(n>x)?n:x;    //所得差与较小数比取大值
    		n=(n<x)?n:x;    //所得差与较小数比取小值
    		if(n==(m-n))    //所得差与减数相等
    			break;
    	}
    	if(i==0)
    		return n;
    	else
    		return (int)pow(2,i)*n;
    }
    

    Stein算法

    算法过程:Stein算法由J. Stein 1961年提出,这个方法也是计算两个数的最大公约数。最大公约数的性质有 gcd( kx,ky ) = k*gcd( x,y ) 这么一个非常好的性质。试取 k=2,则有 gcd( 2x,2y ) = 2 * gcd( x,y )。很快联想到将两个偶数化小的方法,对两个正整数 x>y :
    1.均为偶数 gcd( x,y ) =2gcd( x/2,y/2 );
    2.均为奇数 gcd( x,y ) = gcd( (x+y)/2,(x-y)/2 );
    2.x奇y偶 gcd( x,y ) = gcd( x,y/2 );
    3.x偶y奇 gcd( x,y ) = gcd( x/2,y ) 或 gcd( x,y )=gcd( y,x/2 );
    现在已经有了递归式,还需要再找出一个退化情况。注意到 gcd( x,x ) = x ,就用这个。

    流程图
    在这里插入图片描述
    代码

    int Stein(int x,int y)
    {
    	int factor=0;
    	int temp;
    	if(x<y)
    	{
    		temp=x;
    		x=y;
    		y=temp;
    	}
    	if(y==0)
    		return 0;   //0能被任何非0数整除
    	while(x!=y)
    	{
    		if(x&0x1)    //0x表示16进制
    		{
    			if(y&0x1)   //x,y同为奇数
    			{
    				y=(x-y)>>1;
    				x=x-y;
    			}
    			else
    			{
    				y>>=1;   //x为奇数,y为偶数
    			}
    		}
    		else
    		{
    			if(y&0x1)   //x为偶数,y奇数
    			{
    				x>>=1;
    				if(x<y)
    				{
    					temp=x;
    					x=y;
    					y=temp;
    				}
    			}
    			else     //x,y同为偶数
    			{
    				x>>=1;
    				y>>=1;
    				++factor;
    			}
    		}
    	}
    	return (x<<factor);
    }
    

    源代码

    #include<stdio.h>
    #include<stdlib.h>
    #include<math.h>     //pow(2,i)的头文件
    #include<time.h>     //计算程序运行时间及随机产生数的头文件
    //辗转相除法(1.函数嵌套调用)
    int divisor1(int a,int b)  //自定义函数求两数的最大公约数
    {
    	int temp;       //定义整型变量
    	if(a<b)         //通过比较求出两数中的最大数和最小数
    	{
    		temp=a;     //设置中间变量进行两数交换
    		a=b;
    		b=temp;
    	}
    	while(b!=0)     //通过循环求两数的余数,直到余数为0
    	{
    		temp=a%b;
    		a=b;        //变量数值交换
    		b=temp;
    	}
    return (a);         //返回最大公约数到调用函数处
    }
    //辗转相除法(2.函数递归调用)
    int divisor2(int a,int b)
    {
    	if(a%b==0)     //若a,b取余后余数为0,则返回最大公约数b
    		return b;
    	else
    		return divisor2(b,a%b); //否则递归调用,继续取余
    }
    //穷举法
    int divisor3(int a,int b)
    {
    	int temp;
    	temp=(a>b)?b:a;  //采用条件运算表达式求出两数中的最小值
    	while(temp>0)
    	{
    		if(a%temp==0&&b%temp==0)   //只要能找到一个数能同时被a,b整除,则中止循环
    			break;
    		temp--;     //如不满足if条件则变量自减,直到能被a,b整除
    	}
    	return (temp);
    }
    //更相减损法
    int divisor4(int m,int n)
    {
    	int i=0,temp,x;
    	while(m%2==0&&n%2==0)  //判断a,b是否都是偶数,若是则用2约简
    	{
    		m/=2;
    		n/=2;
    		i+=1;  //约简2的个数
    	}
    	if(m<n)  //a保存最大值
    	{
    		temp=m;
    		m=n;
    		n=temp;
    	}
    	while(x)       //当x不为0时
    	{
    		x=m-n;           //较大数减较小数
    		m=(n>x)?n:x;    //所得差与较小数比取大值
    		n=(n<x)?n:x;    //所得差与较小数比取小值
    		if(n==(m-n))    //所得差与减数相等
    			break;
    	}
    	if(i==0)
    		return n;
    	else
    		return (int)pow(2,i)*n;
    }
    //Stein算法
    int Stein(int x,int y)
    {
    	int factor=0;
    	int temp;
    	if(x<y)
    	{
    		temp=x;
    		x=y;
    		y=temp;
    	}
    	if(y==0)
    		return 0;//0能被任何非0数整除
    	while(x!=y)
    	{
    		if(x&0x1)//0x表示16进制
    		{
    			if(y&0x1)//x,y同为奇数
    			{
    				y=(x-y)>>1;
    				x=x-y;
    			}
    			else
    			{
    				y>>=1;//x为奇数,y为偶数
    			}
    		}
    		else
    		{
    			if(y&0x1)//x为偶数,y奇数
    			{
    				x>>=1;
    				if(x<y)
    				{
    					temp=x;
    					x=y;
    					y=temp;
    				}
    			}
    			else//x,y同为偶数
    			{
    				x>>=1;
    				y>>=1;
    				++factor;
    			}
    		}
    	}
    	return (x<<factor);
    }
    void main()
    {
    	int x,y,temp;
    	int m,n,p,i,N,s[100];
    	printf("--------------You have two options-------------\n");
    	printf("       1.求两数最大公约数的操作\n");
    	printf("       2.计算程序运行时间及随机数测试操作\n");
    	printf("-----------------------------------------------\n");
    	printf("Please input a number you want:\n ");
    	scanf("%d",&n);
    	if(n<1||n>2)
    	{
    		printf("error! Please input again!\n");
    		scanf("%d",&n);
    	}
    	if(n==1)
    	{  
    		printf("请输入两个正整数(用逗号隔开):\n");
    		scanf("%d,%d",&x,&y);
    		printf("There are five ways to find the greatest common divisor,you can choose one:\n");
    		printf("-----------------选择方法-------------------\n");
    		printf("      1.辗转相除法(函数嵌套调用)     \n");
    		printf("      2.辗转相除法(函数递归调用)     \n");
    		printf("      3.穷举法                         \n");
    		printf("      4.更相减损法                     \n");
    		printf("      5.Stein算法                      \n");
    		printf("--------------------------------------------\n");
            while(1)
    		{
    			printf("Please input the way of you choice:\n");
    			scanf("%d",&m);
    				switch(m)
    				{
    				case 1:
    					printf("The way you choice is first(辗转相除法-函数嵌套调用)\n");
    					temp=divisor1(x,y);
    					printf("The greatest common divisor is %d\n",temp);
    					break;
    				case 2:
    					printf("The way you choice is second(辗转相除法-函数递归调用)\n");
                        temp=divisor2(x,y);
                        printf("The greatest common divisor is %d\n",temp);
    					break;
    				case 3:
                        printf("The way you choice is third(穷举法)\n");
    					temp=divisor3(x,y);
    					printf("The greatest common divisor is %d\n",temp);
    					break;
    				case 4:
    					printf("The way you choice is fourth(更相减损法 )\n");
    					temp=divisor4(x,y);
    					printf("The greatest common divisor is %d\n",temp);
    					break;
    				case 5:
    					printf("The way you choice is fifth(Stein算法 )\n");
    					temp=Stein(x,y);
    					printf("The greatest common divisor is %d\n",temp);
    					break;
    				}
    			}
    	}
       else	if(n==2)
       {
    		clock_t start,finish;               
    		double T;
    		srand((unsigned)time(NULL));
    		printf("你想测试多少组数据:\n");
    		scanf("%d",&N);
    		for(i=0;i<N;i++)                     
    		{
    			s[i]=rand()%500+1;
    			printf("%d  ",s[i]);
    		}
    		printf("\n");
    		printf("There are five ways to find the greatest common divisor,you can choose one:\n");          //选择菜单
    	    printf("-----------------选择方法-------------------\n");
    		printf("      1.辗转相除法(函数嵌套调用)     \n");
    		printf("      2.辗转相除法(函数递归调用)     \n");
    		printf("      3.穷举法                         \n");
    		printf("      4.更相减损法                     \n");
    		printf("      5.Stein算法                      \n");
    		printf("--------------------------------------------\n");
    		while(1)
    		{
    			int j=0;
    	    	printf("Please input the way of you choice:\n");
    			scanf("%d",&p);
    			while(p<1||p>5)
    			{
    				printf("输入错误!请重新输入:\n");
    				scanf("%d",&p);
    			}
    			switch(p)
    			{
    			case 1:
    				start=clock();                  //程序运行,开始计时
    				while(j<N)
    				{
    					x=s[j++];
    					y=s[j++];
    					temp=divisor1(x,y);
    					printf("The greatest common divisor is %d\n",temp);
    		
    				}
    				finish=clock();                //程序运行结束,结束计时
    				break;
    			case 2:
    				start=clock();
    				while(j<N)
    				{
    					x=s[j++];
    					y=s[j++];
    	    			temp=divisor2(x,y);
                        printf("The greatest common divisor is %d\n",temp);
    				}
    				finish=clock();
    				break;
    			case 3:
    				start=clock();
    				while(j<N)
    				{
    					x=s[j++];
    					y=s[j++];
    					temp=divisor3(x,y);
    					printf("The greatest common divisor is %d\n",temp);
    				}
    				finish=clock();
    				break;
    			case 4:
    				start=clock();
    				while(j<N)
    				{	
    					x=s[j++];
    					y=s[j++];
    			    	temp=divisor4(x,y);
    					printf("The greatest common divisor is %d\n",temp);
    				}
    				finish=clock();
    				break;
    			case 5:
    			start=clock();
    			while(j<N)
    			{
    				x=s[j++];
    				y=s[j++];
    	    		temp=Stein(x,y);
    				printf("The greatest common divisor is %d\n",temp);
    			}
    			finish=clock();
    			break;
    		}
    			T=(double)(finish-start)/1000;    //计算时间差,由于计算机计算的是毫秒,转换成秒要除以1000
    			printf("这个方法的运行时间是%f秒\n",T);
    	}
    }
    }
    

    调试、测试及运行结果

    运行结果
    运行结果
    调试结果
    在这里插入图片描述
    测试运行时间
    在这里插入图片描述

    经验总结

    遇到的问题
    1.对于Stein算法自己没有理解清楚,看了程序也是似懂非懂,但想了一下觉得还是要弄明白,所以又在csdn上查了很多资料,也请教了身边的同学,对于这个算法是最后弄明白的。
    2.对于在不同规模测试数据的情况下比较四种算法的运行时间,刚开始并没有想到用随机函数来产生数据,而是想手动输入,但这样的做法显然有局限性,对于随机函数也是参考了很多资料。
    总结
    四种算法相对来说,前两种方法比较简单,也容易理解,后两种算法确实需要思考、查资料,其中对于第三种更相减损法,我想的是:可不可以不用判断两数是否是偶数,直接在循环中大数减小数,直到两数相等。自己动手试了一下,这样确实也可以求出最大公约数,而且比较简单、容易理解。所以,通过这个例子,我觉得每一次的问题的答案都不应该是唯一的,我们应该勇于尝试新的方法。

    展开全文
  • 2.求最大公约数 1.穷举法 两个数的最大公约数必然是小于等于最小的数的,故从最小的数开始每次1开始寻找能同时整除两个数的,找到为止,即为最大公约数。 2.相减法 利用如下性质: 3.欧几里得辗转相除法 ...
  • C语言求最大公约数和最小公倍数的各种算法的总结,辗转相除法,穷举法等等
  • 实验题目:运行最大公约数的常用算法,并进行程序的调式与测试,要求程序设计风格良好,并添加异常处理模块(如输入非法等)。 分析:运用四种算法分别计算最大公约数,并选择手动输入数据验证算法正确和随机产生...
  • 辗转相除(又名欧几里德C语言中用于计算两个正整数a,b的最大公约数和最小公倍数,实质它依赖于下面的定理: a b=0 gcd(a,b) = { gcd(b,a mod b) b!=0 根据这一定理可以采用函数嵌套调用形式进行两个数的...
  • 求最大公约数的三种方法,穷举法,相减法,辗转相除法 公式法求最小公倍数:a*b/gcd(a,b) */ #include int GCD(int,int); static int GCD1(int n1,int n2); static int GCD2(int a,int b); int main() { int n1, ...
  • 求最大公约数与最小公倍数一.最大公约数:最大公约数目前有三种求法:更相减损术、辗转相除法以及穷举法。1.更相减损术:算法介绍:设两个整数数a和b,以较大数减较小数,得出的差与减数比较大小,再次使用较大数减较...
  • 利用辗转相除法、穷举法、更相减损术、Stein算法出两个数的最大公约数或者/和最小公倍数。 最大公约数:指两个或多个整数共有约数中最大的一个。 例如:【12和24】12的约数有:1、2、3、4、6、12;24的约数有...
  • c语言求最大公约数三种算法

    千次阅读 2017-03-20 19:27:26
    算法设计思路: 1. 用辗转相除法求两个数的最大公约数 输入两个整数m,n,将大的值给m,小的值给n。令t=m%n,当t不为0,m=n,n=t,当余数为0时,n的值为最大公约数。...穷举法求两个数最大公约数 输入
  • 任意两个正整数的最大公约数(GCD)。 问题分析 如果有一个自然数a能被自然数b整除,则称a为b的倍数,b为a的约数。几个自然数公有的约数,叫做这几个自然数的公约数。公约数中最大的一个公约数,称为这几个...
  • C语言求最大公约数的算法(三种)

    万次阅读 多人点赞 2017-12-12 01:38:46
    1、相减法 2、穷举法 3、辗转相除法
  • C语言求最大公约数

    2017-03-22 20:02:05
    /*************************...求最大公因数 创建时间:2017.03.18 创建人:卫薇(1508010107) 主要功能:用三种方法(1:穷举法;2:辗转相除法;3:相减法)求两个数的最大公因数及最小公倍数 **********************
  • 求最大公约数与最小公倍数 一.最大公约数: 最大公约数目前有三种求法:更相减损术、辗转相除法以及穷举法。 1.更相减损术: 算法介绍:设两个数a和b,以较大数减较小数,得出的差与减数比较大小,再次使用较大数减较...
  • * 最大公约数:辗转相除法实现 辗转相减法实现 穷举法实现 * 最小公倍数:穷举法实现 * @author 李政 &amp;amp;lt;1244109467@qq.com&amp;amp;gt; */ #include&amp;amp;lt;stdio.h&amp;amp;gt; int...
  • 求最大公约数有多种方法,常见的有质因数分解法、短除法、辗转相除法、更相减损法。 在C语言里,我们常用辗转相除法和更相减损法来写;但我们通过计算机的计算能力也可以使用暴力穷举法! 一、暴力穷举法: 我们先...
  • C++实现的:最大公约数C语言或其他语言同理。 多回头看看 很有帮助。1、 最大公约数 <1> 题目描述:求解两个整数(不能是负数)的最大公约数(要求两数不能同时为0) <2> 方法一:穷举法 <3> 方法二:相减法 <4> ...
  • 四种方法分别为:辗转相除...穷举法(也叫枚举法)穷举法求两个正整数的最大公约数的解题步骤:从两个数中较小数开始由大到小列举,直到找到公约数立即中断列举,得到的公约数便是最大公约数 。 ①定义1:对两个正整...
  • 给定两个数,这两个数的最大公约数 最大公约数,也称最大公因数、最大公因子,指两个或多个整数共有约数中最大的一个。求解的方式比较多,暴力穷举、辗转相除法、更相减损法、Stein算法。 1.暴力穷举法 如果大数...
  • 三种方法求最大公约数C语言版)

    万次阅读 多人点赞 2017-03-21 23:20:53
    问题描述:用三种方法两个的整数的最大公约数。 算法分析: 1.相减法:输入两整数a和b,(1)如果a>b,a=a-b;(2)如果a  (4)如果a!=b,则再执行(1)或(2) 程序实现如下图: 2.穷举法:输入两个整数a和b,(1)...
  • 又称辗转相除,依据定理gcd(a,b)=gcd(b,a%b) 实现过程演示: sample:gcd(15,10)=gcd(10,5)=gcd(5,0)=5 C语言实现: 1 int Euclid_GCD(int a, int b) 2 { 3 return b?Euclid_GCD(b, a%b):a; 4 }
  • 1.两个数的最大公约数 方法一:穷举法 //打印100-200之间的素数 #include<stdio.h> #include<windows.h> #include<math.h> #pragma warning(disable:4996) int GreatCommonDivisor(int _x, in...
  • //定义穷举法的函数 int main() { int a, b,cd; printf(“Please input two number:”); scanf_s("%d%d", &a, &b); cd= Exhaustion( a, b); printf("%d", cd); return 0; } //穷举法 int Exhaustion(int a, ...
  • 以下我来介绍几种求最大公约数的方法: 1.暴力穷举法: 此方法是理解难度最低的办法,就是两个数从两个数字的较小者循环递减到1,看第一个满足两个数取余数皆为0的数字,并输出。 int num1=0; int num2=0; printf(...
  • C语言求两个数中最大公约数

    千次阅读 2016-06-11 18:49:56
    C语言中如何两个数的最大公约数呢?下面用三种方法进行求解。方法一:穷举法。 先比较两个数的大小,然后找出较小数t,最后判断t为何值时两个数都能整除,此方法效率较低。代码如下:#include int main() {  ...

空空如也

空空如也

1 2 3
收藏数 56
精华内容 22
关键字:

c语言穷举法求最大公约数

c语言 订阅