精华内容
下载资源
问答
  • #计算两个数的最大公约数 def Common_divisor(num1, num2): min = num1 if num1 < num2 else num2 i, final_num = 1, 1 while i <= min: if num1 % i == 0 and num2 % i == 0: final_num = i i += 1 return ...

    #计算两个数的最大公约数

    def Common_divisor(num1, num2):
        min = num1 if num1 < num2 else num2
        i, final_num = 1, 1
        while i <= min:
            if num1 % i == 0 and num2 % i == 0:
                final_num = i
            i += 1
        return final_num
    
    
    num1, num2 = input('请输入第一个数字'), input('请输入第二个数字')
    final_ = Common_divisor(int(num1), int(num2))
    print(final_)
    

    #数学类实现

    import math
    m = math.gcd(int(num1), int(num2))
    print(m)
    
    展开全文
  • Java编程实现计算两个数的最大公约数,如果最大公约数是1,则还需要输出互质
  • python计算两个数的最大公约数 def hcf(x, y): if x > y: smaller = y else: smaller = x hcf = 0 for i in range(2, smaller + 1): if x % i == 0 and y % i == 0: hcf = i return hcf

    python计算两个数的最大公约数

    def hcf(x, y):
        if x > y:
            smaller = y
        else:
            smaller = x
        hcf = 0
        for i in range(2, smaller + 1):
            if x % i == 0 and y % i == 0:
                hcf = i
    
        return hcf
    
    展开全文
  • 运动js递归的方法计算两个数字的最大公约数 <input type="text" name="" id="txt1"> <input type="text" name="" id="txt2"> <input type="button" name=""value="计算公约数" id="btn"> <...

    运动js递归的方法计算两个数字的最大公约数

    <input type="text" name="" id="txt1">
        <input type="text" name="" id="txt2">
        <input type="button" name=""value="计算公约数" id="btn">
        <input type="text" name="" id="txt3">
    var txt1=document.getElementById("txt1");
        var txt2=document.getElementById("txt2");
        var btn=document.getElementById("btn");
        var txt3=document.getElementById("txt3");
        btn.onclick=function(){
            var i=txt1.value;
            var j=txt2.value
            txt3.value=fn(i,j)
        }
        function fn(m,n){
                r=m%n;
                m=n;
                n=r;
                if (r==0) {
                    return m
                }else {
                    return fn(m,n)
                }
        }
    展开全文
  • 定义一个类,分别提供成员函数计算两个数的最大公约数和最小公倍数(c++)</p>
  • 计算两个数的最大公约数 2.题目分析 计算两个数的最大公约数,可以采用最大公约数的四种常用算法,分别是辗转相除法、穷举法、更相减损法、Stein算法。每种方法写一个函数,分别计算出最大公约数,主函数的菜单里...

    1.题目名称
    计算两个数的最大公约数

    2.题目分析
    计算两个数的最大公约数,可以采用最大公约数的四种常用算法,分别是辗转相除法、穷举法、更相减损法、Stein算法。每种方法写一个函数,分别计算出最大公约数,主函数的菜单里有选择功能,用户可以选择自行输入两个数,然后调用这四种方法的任一种;也可以选择程序的测试功能,通过自己选择的组数,计算机自动产生随机函数,然后调用四种方法的任一种,并计算出程序运行的时间。

    3.算法构造
    3.1辗转相除法

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

    3.2穷举法(利用数学定义)
    穷举法(也叫枚举法)穷举法求两个正整数的最大公约数的解题步骤:
    从两个数中较小数开始由大到小列举,直到找到公约数立即中断列举,得到的公约数便是最大公约数 。
    对两个正整数a,b如果能在区间[a,0]或[b,0]内能找到一个整数temp能同时被a和b所整除,则temp即为最大公约数。

    3.3更相减损法
    更相减损术,是出自《九章算术》的一种求最大公约数的算法,它原本是为约分而设计的,但它适用于任何需要求最大公约数的场合。《九章算术》是中国古代的数学专著,其中的“更相减损术”可以用来求两个数的最大公约数,即“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。以等数约之。”
    翻译成现代语言如下:
    第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。
    第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。
    则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
    其中所说的“等数”,就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。

    3.4 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 ,就用这个。

    4.算法实现
    4.1辗转相除法

    int max1(int a,int b)             //辗转相除法-------1.函数嵌套调用
    {
    	int temp;
    	if(a<b)                    //若存在a小于b的情况,则交换数值
    	{
    		temp=a;
    		a=b;
    		b=temp;
    	}
    	while(b!=0)          //直到b为0,通过赋值得到最大公约数为a的值
    	{
    		temp=a%b;           //temp为余数                      
    		a=b;                //将b的值赋给a
    		b=temp;            //将余数temp的值赋给b
    	}
    	return a;
    }
    int max2(int m,int n)        //辗转相除法-------2.函数递归调用
    {
    	if(m%n==0)          //若m和n取余后余数为0,则返回最大公约数n
    		return n;
    	else
    		return max2(n,m%n);     //返回到max2这个函数中,并给m,n赋值
    }
    

    4.2穷举法(利用数学定义)

    int max3(int x,int y)               //3.穷举法
    {
    	int temp;
    	if(x<y)                        //把较小的值赋给temp
    		temp=x;
    	else
    		temp=y;
    	while(temp>0)
    	{
    		if(x%temp==0&&y%temp==0)   //若大数取余小数余数为0,则结束循环,小数就是两个数的最大公约数
    			break;
    		else
    			temp--;                //两个数中较小的数temp减一,直到找到最大公约数或temp为0为止
    	}
    	return temp;
    }
    

    4.3更相减损法

    int max4(int c,int d)             //4.更相减损法
    {
    	int i=0;
    	int temp,x;
    	while(c%2==0&&d%2==0)    //检测c和d是否偶数,若是,则用2约简
    	{
    		c=c/2;                           
    		d=d/2;
    		i++;                 //计算c和d被2约了几次
    	}
    	if(c<d)                  //始终令c<d
    	{
    		temp=c;
    		c=d;
    		d=temp;
    	}
    	while(x)                //当x不等于0时
    	{
    		x=c-d;              //以较大的数减较小的数                        
    		c=(d>x)?d:x;        //把所得的差与较小的数比较
    		d=(d<x)?d:x;
    		if(x==d)           //所得的减数和差相等
    			break;
    	}
    	if(i)                                //当i不等于0
    		return (int)pow(2,i)*d;            //pow(2,i)表示2的i次方,即2的i次方与d的乘积就是最大公约数
    }
    

    4.4 Stein算法

    int max5(unsigned int x,unsigned int y)       //5.Stein算法
    {
    	int factor=0;
    	int temp;
    	if(x<y)                              //赋值令x>y
    	{
    		temp=x;
    		x=y;
    		y=temp;
    	}
    	if(0==y)
    	{
    		return 0;
    	}
    	while(x!=y)                       //当x和y不相等
    	{
    		if(x & 0x1 )                   //0x是十六进制的表示方式,这里表示十六进制的1,即x相与1,也就是判断x是奇数
    		{
    			if(y & 0x1 )              //如果x,y都是奇数
    			{
    				y=(x-y)>>1;         // (x-y)即两个奇数的差是偶数,>>表示右移/2
    				x-=y;
    			}
    			else                 //如果x是奇数,y是偶数
    			{
    				y>>=1;
    			}
    		}
    		else                         
    		{
    			if(y & 0x1 )           //如果x是偶数,y是奇数
    			{
    				x>>=1;
    				if(x<y)           //始终令x>y
    				{
    					temp=x;
    					x=y;
    					y=temp;
    				}
    			}
    			else               //如果x,y是两个偶数
    			{
    				x>>=1;
    				y>>=1;
    				++factor;
    			}
    		}
    	}
    	return (x<<factor);
    }
    
    ****4.5完整代码****
    
    

    在这里插入代码片

    
    #include<stdio.h>
    #include<math.h>                           //计算2的i次方的函数pow(2,i)的头文件
    #include<time.h>                          //计算程序运行时间和随机产生数的头文件
    #include<stdlib.h>
    int max1(int a,int b)                     //辗转相除法-------1.函数嵌套调用
    {
    	int temp;
    	if(a<b)                               //若存在a小于b的情况,则交换数值
    	{
    		temp=a;
    		a=b;
    		b=temp;
    	}
    	while(b!=0)                           //直到b为0,通过赋值得到最大公约数为a的值
    	{
    		temp=a%b;                        //temp为余数                      
    		a=b;                             //将b的值赋给a
    		b=temp;                          //将余数temp的值赋给b
    	}
    	return a;
    }
    int max2(int m,int n)                 //辗转相除法-------2.函数递归调用
    {
    	if(m%n==0)                        //若m和n取余后余数为0,则返回最大公约数n
    		return n;
    	else
    		return max2(n,m%n);          //返回到max2这个函数中,并给m,n赋值
    }
    int max3(int x,int y)               //3.穷举法
    {
    	int temp;
    	if(x<y)                        //把较小的值赋给temp
    		temp=x;
    	else
    		temp=y;
    	while(temp>0)
    	{
    		if(x%temp==0&&y%temp==0)   //若大数取余小数余数为0,则结束循环,小数就是两个数的最大公约数
    			break;
    		else
    			temp--;                //两个数中较小的数temp减一,直到找到最大公约数或temp为0为止
    	}
    	return temp;
    }
    int max4(int c,int d)                           //4.更相减损法
    {
    	int i=0;
    	int temp,x;
    	while(c%2==0&&d%2==0)                      //检测c和d是否偶数,若是,则用2约简
    	{
    		c=c/2;                           
    		d=d/2;
    		i++;                                  //计算c和d被2约了几次
    	}
    	if(c<d)                                   //始终令c<d
    	{
    		temp=c;
    		c=d;
    		d=temp;
    	}
    	while(x)                                 //当x不等于0时
    	{
    		x=c-d;                               //以较大的数减较小的数                        
    		c=(d>x)?d:x;                         //把所得的差与较小的数比较
    		d=(d<x)?d:x;
    		if(x==d)                            //所得的减数和差相等
    			break;
    	}
    	if(i)                                  //当i不等于0
    		return (int)pow(2,i)*d;            //pow(2,i)表示2的i次方,即2的i次方与d的乘积就是最大公约数
    }
    int max5(unsigned int x,unsigned int y)                    //5.Stein算法
    {
    	int factor=0;
    	int temp;
    	if(x<y)                              //赋值令x>y
    	{
    		temp=x;
    		x=y;
    		y=temp;
    	}
    	if(0==y)
    	{
    		return 0;
    	}
    	while(x!=y)                        //当x和y不相等
    	{
    		if(x & 0x1 )                   //0x是十六进制的表示方式,这里表示十六进制的1,即x相与1,也就是判断x是奇数
    		{
    			if(y & 0x1 )               //如果x,y都是奇数
    			{
    				y=(x-y)>>1;           // (x-y)即两个奇数的差是偶数,>>表示右移/2
    				x-=y;
    			}
    			else                      //如果x是奇数,y是偶数
    			{
    				y>>=1;
    			}
    		}
    		else                         
    		{
    			if(y & 0x1 )             //如果x是偶数,y是奇数
    			{
    				x>>=1;
    				if(x<y)            //始终令x>y
    				{
    					temp=x;
    					x=y;
    					y=temp;
    				}
    			}
    			else                   //如果x,y是两个偶数
    			{
    				x>>=1;
    				y>>=1;
    				++factor;
    			}
    		}
    	}
    	return (x<<factor);
    }
    
    void main()
    {
    	int x,y,p,i,n,N,m[1000];
    	int a,b,c,d,e;
    	printf("*********************你有两种选择********************\n");
    	printf("* 1.输入两个你想计算最大公约数的正整数并计算.       *\n");
    	printf("* 2.利用随机数测试最大公约数并计算程序运行时间.     *\n");
    	printf("*****************************************************\n");
    	printf("请选择你想要进行的操作:\n");
    	scanf("%d",&n);
    	while(n<1||n>2)
    	{
    		printf("没有这个选项!请重新输入:\n");
    		scanf("%d",&n);
    	}
    	if(n==1)
    	{
    	printf("请输入两个正整数:\n");     //用户自行输入两个数
    	scanf("%d%d",&x,&y);
    	while(x<0||y<0||x==0||y==0)
    	{
    		printf("请按要求输入正整数:\n");
    		scanf("%d%d",&x,&y);
    	}
    	printf("在这里你有5种方法计算最大公约数:\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("请输入你的选择(1-5):\n");
    		scanf("%d",&p);
    		while(p<1||p>5)
    		{
    			printf("输入错误!请重新输入:\n");
    			scanf("%d",&p);
    		}
    		switch(p)
    		{
    		case 1:
    				a=max1(x,y);
    				printf("你选择了辗转相除法中的函数嵌套调用.\n");
    				break;
    		case 2:
    	    		a=max2(x,y);
    		    	printf("你选择了辗转相除法中的函数递归调用.\n");
    			break;
    		case 3:
    				a=max3(x,y);
    				printf("你选择了穷举法.\n");
    				break;
    		case 4:
    				a=max4(x,y);
    				printf("你选择了更相减损法.\n");
    				break;
    		case 5:
    			
    	    		a=max5(x,y);
    		    	printf("你选择了Stein算法.\n");
    				break;
    		}
    		printf("用这种方法计算的最大公约数为%d:\n",a);
    	}
    }
    else if(n==2)
    {
    		clock_t start,finish;                  //计算随机函数
    		double duration;
    		srand((unsigned)time(NULL));
    		printf("你想测试多少组数据?\n");
    		scanf("%d",&N);
    		for(i=0;i<N;i++)                     //随机取20个数(1-100)
    		{
    			m[i]=rand()%100+1;
    			printf("%d\t",m[i]);
    		}
    		printf("\n");
    		printf("在这里你有5种方法计算最大公约数:\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("请输入你的选择(1-5):\n");
    			scanf("%d",&p);
    			while(p<1||p>5)
    			{
    				printf("输入错误!请重新输入:\n");
    				scanf("%d",&p);
    			}
    			switch(p)
    			{
    			case 1:
    				start=clock();                  //程序运行,开始计时
    				while(j<20)
    				{
    					x=m[j++];
    					y=m[j++];
    					a=max1(x,y);
    					printf("你选择了辗转相除法中的函数嵌套调用.\n");
    					printf("用这种方法计算的最大公约数为%d:\n",a);
    		
    				}
    				finish=clock();                                  //程序运行结束,结束计时
    				break;
    			case 2:
    				start=clock();
    				while(j<20)
    				{
    					x=m[j++];
    					y=m[j++];
    	    			b=max2(x,y);
    		    		printf("你选择了辗转相除法中的函数递归调用.\n");
    		    		printf("用这种方法计算的最大公约数为%d:\n",b);
    				}
    				finish=clock();
    				break;
    			case 3:
    				start=clock();
    				while(j<20)
    				{
    					x=m[j++];
    					y=m[j++];
    					c=max3(x,y);
    					printf("你选择了穷举法.\n");
    					printf("用这种方法计算的最大公约数为%d:\n",c);
    				}
    				finish=clock();
    				break;
    			case 4:
    				start=clock();
    				while(j<20)
    				{	
    					x=m[j++];
    					y=m[j++];
    					d=max4(x,y);
    					printf("你选择了更相减损法.\n");
    					printf("用这种方法计算的最大公约数为%d:\n",d);
    				}
    				finish=clock();
    				break;
    			case 5:
    			start=clock();
    			while(j<20)
    			{
    				x=m[j++];
    				y=m[j++];
    	    		e=max5(x,y);
    		    	printf("你选择了Stein算法.\n");
    		    	printf("用这种方法计算的最大公约数为%d:\n",e);
    			}
    			finish=clock();
    			break;
    		}
    			duration=(double)(finish-start)/1000;                  计算时间差,由于计算机计算的是毫秒,转换成秒要除以1000
    			printf("这个方法的运行时间是%f秒\n",duration);
    	}
    		}
    	}
    
    

    5.经验归纳
    5.1遇到的问题
    1.对随机函数不熟悉;
    2.测试环节,对计算程序运行时间不熟悉;
    3.在更相减损法的最后,用到了pow()函数,因没加头文件#include<math.h>而出错;
    4.因知识储备不足,对最后一种方法(Stein算法)不理解。
    PS:以上问题均已解决。

    5.2心得体会
    我觉得这四种方法里Stein算法我有点看不懂(可能是因为有>>运算符),还有随机数的生成和计算程序运行时间的函数都只是有一些印象,并不熟悉。(但是我可以查资料和问同学啊hhh~~~)
    主函数我改了很多次,就是想让界面更加美化一些,改完就发现程序出错了…其实就是赋值这么一个小细节,但就是发现不了(Emmmm),感觉自己还需要学很多东西,动手能力也要加强~~~
    总之就是~~~add oil!!!

    展开全文
  • 计算两个数的最大公约数。由于这两个算法很常见,小菜就不班门弄斧的介绍了 一、普通整数求最大公约数 一、辗转相除法 int gcd(int a,int b) { if(b==0) return a; return gcd(b,a%b); } 二、相减法 int ...
  • 创建类 Computer,该类中有一个计算两个数的最大公约数的方法,如果向该方法传递负整数,该方法就会抛出自定义异常。 二、实现 package com.eleven.csdn0103; import java.util.Scanner; /** * 创建类 Computer,该...
  • import java.util.ArrayList;... * Describe: 该类有6种方法计算两个数的最大公约数&amp;amp;amp;lt;br&amp;amp;amp;gt; * Detail: 方法public static int nonRecursiveDivisionAlgorithm(int a,int b)...
  • 题目:计算两个数字的最大公约数和最小公倍数 s=[0,0] print("Enter your number: ") for i in range(2): try: s[i]=eval(input()) except: print('something goes wrong,please enter again! ') a=...
  • 计算两个数的最大公约数: 算法: ⑴ 输入两个整数m、n,并求m除以n的余数k。 ⑵ 当k≠0,将除数n作为被除数m,余数k作为除数n,继续求m除以n的余数k;反复做第⑵步,直到余数为0结束循环。 ⑶ 结束循环后,...
  • 递归法计算两个数的最大公约数

    千次阅读 2018-12-14 00:59:20
    题目内容:利用最大公约数的...反复使用最大公约数的上述性质,直到a和b相等为止,这时,a或b就是它们的最大公约数。这三条性质,也可以表示为: 性质1 如果a&gt;b,则a和b与a-b和b的最大公约数相同,即Gcd(a, ...
  • 9.在数学计算或数字分析中,经常会用到计算两个数的最大公约数的问题。即:输入两个正整数,当两个数字有一个不是正整数时会产生异常。当输入非整数数字时,也产生异常。输入无错误后,可计算两个数的最大公约数。 ...
  • 最大公约数 if number1>number2: number3=number2 else: number3=number1 ... print('这两个数的最大公约数为:',i) break 最小公倍数 if number1>number2: number3=number1 else: nu
  • """ 两个或多个整数公有的倍数叫做它们的公倍数 """ ... """该函数返回两个数的最大公约数""" # 获取最小值 if x > y: smaller = y else: smaller = x for i in range(1, smaller + 1): ...
  • 文章目录计算最大公约数(暴力求解和辗转相除法)计算最小公倍数 计算最大公约数(暴力求解和辗转相除法) 方法一:暴力求解 def hcf(x,y): smaller = x if x<y else y for ii in range(1,x+1): if x%ii==0 ...
  • 输入两个正整数,打印出这两个数的最大公约数。 分析: 如果定义输入两个数为 x 与 y,最小公约数一定不大于两个数中最小的数,最小为1,即最大公约数max_common_divisor: 在 x > y 的情况下:1 <= max...
  • /** * 输入两个正整数m和n,求... * 例如:12和20的最大公约数是4,最小公倍数是60 */ public class MathTest { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); Syste...
  • #include<...//最大公约数 int calmin(int a, int b);//最小公倍数 int main(void) { int a,b; printf("请输入两个整数:"); scanf("%d %d",&a,&b); printf("两个整数的最大公约...
  • 欧几里得算法描述:以除数和余数反复做除法运算,当余数为 0 时,取当前算式除数为最大公约数。 例: 1997 / 615 = 3 (余 152) 615 / 152 = 4(余7) 152 / 7 = 21(余5) 7 / 5 = 1 (余2) 5 / 2 = 2 (余1) 2 / 1 = 2 ...
  • 利用辗转相除法 int Grial(int a, int b) { if (b == 0) return a; return Grial(b, a%b); }
  • step1:如果b等于0,计算结束,a就是最大公约数; step2:否则,计算a除以b余数,让a等于b,而b等于那个余数; step3:回到第一步。 表格演示: a b t 12 18 12 18 12 6 12 6 0 6 0 程序: # include&...
  • step4:则曾经记下的最大的能同时整除a和b的i就是最大公约数。 程序: # include<stdio.h> int main() { int a,b; scanf("%d %d",&a,&b); int ret=0; int min=0; if(a>b){ m
  • 目录 一、最大公约数和最小公倍数概念 1.1、最大公约数: 1.2、求解最大公约数的方法: 2.1、最小公倍数: ... 最大公因数,也称最大公约数、最大公因子,指两个或多个整数共有约数中最大...
  • 【题目描述】 给定m和n,计算m和n的最大公约数。 ...输出一个数表示m和n的最大公约数。 【输入样例】 12 18 【输出样例】 6 【数据范围限制】 1 <= m,n <2^63。提示:注意数据范围 代码 ...
  • 利用欧几里得算法(即辗转相除法)计算两个整数的最大公约数 #include<iostream> #include<algorithm> using namespace std; int gcb(int a,int b) { if(b==0) return a; else return ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,172
精华内容 468
关键字:

计算两个数的最大公约数