精华内容
下载资源
问答
  • 求多个数最大公因数算法 C语言

    千次阅读 2019-01-14 20:50:09
    我们用(a1,a2,....)表示最大公因数 [a1,a2,.....]表示最小公倍数 1、两个数的最大公因数 辗转相除法,可以直接使用C语言自带的 c = __...2、多个数以上的最大公因数 1、多次辗转相除法 1.使用辗转相除法a1...

    我们用(a1,a2,....)表示最大公因数  [a1,a2,.....]表示最小公倍数

    1、两个数的最大公因数

              辗转相除法,可以直接使用C语言自带的 c = __gcd(a,b);

              辗转相除法原理可以自行百度。

    2、多个数以上的最大公因数

             1、多次辗转相除法

                          1.使用辗转相除法求a1和a2的最大公因数(a1,a2)

                          2.使用辗转相除法求(a1,a2)和  a3 的最大公因数(a1,a2,a3);

                          3.重复,得到(a1,...,an)

       代码

    int Gcd(int a[],int n){	//多次辗转相处法
    	int ans = a[0];
    	for(int i=1;i<n;i++){
    		ans = __gcd(ans,a[i]);
    	} 
    	return ans;
    }

            2、变换法

                          1、找到a1,a2,..,an中的最小非零项aj,若有多个最小非零项则任取一个

                          2、 aj以外的所有其他非0项ak用ak mod aj代替;若没有除aj以外的其他非0项,则转到(4)

                          3、转到  1

                          4、 a1,a2,..,an的最大公约数为aj

    代码

    int Gcd2(int a[],int n){	//变换法
    	int Min=a[0],pos=0,conter=0;
    	while(conter<n-1){
    		for(int i=0;i<n;i++){
    			if(a[i] && a[i]<Min){
    				Min=a[i];
    				pos=i;
    			}
    		}
    		
    		for(int i=0;i<n;i++){
    			if(i==pos) continue;
    			a[i]=a[i]%Min;
    			if(!a[i]) conter++; 
    		}
    	}
    	
    	for(int i=0;i<n;i++)
    		if(a[i]) return a[i]; 
    } 

    3、两个数多的最小公倍数

            公式:a*b=[a,b]*(a,b)

    4、多个数的最小公倍数

              多个数的最小公倍数并无像两个数的最小公倍数的计算公式

              公式:[a1,a2,..,an]=M/(M/a1,M/a2,..,M/an)   其中M为a1,a2,..,an的乘积

             1、计算m=a1*a2*..*an

             2、把a1,a2,..,an中的所有项ai用m/ai代换

             3、找到a1,a2,..,an中的最小非零项aj,若有多个最小非零项则任取一个

             4、aj以外的所有其他非0项ak用ak mod aj代替;若没有除aj以外的其他非0项,则转到(6)

             5、转到(3)

             6、最小公倍数为m/aj
    代码:

    int Lcm(int a[],int n){
    	int m=1;
    	for(int i=0;i<n;i++)	//求积 
    		m*=a[i];
    	
    	for(int i=0;i<n;i++)
    		a[i]=m/a[i]; 
    		
    	int gcd=Gcd2(a,n);
    //  int gcd=Gcd(a,n);
    	return m/gcd;
    }

    嗯,就是这样。

    展开全文
  • 一、题目名称:求多个数最大公因数 二、算法设计: 1.输入数据 2.将数据用冒泡法由小到大排序; 3.将最小的数赋值给b; 4.判断是否所有的数是否能够整除b; 5.如果不能整除,b自减; 6.如果所有数都能整除b...

    一、题目名称:求多个数的最大公因数

    二、算法设计:

    1.输入数据
    2.将数据用冒泡法由小到大排序;
    3.将最小的数赋值给b;
    4.判断是否所有的数是否能够整除b;
    5.如果不能整除,b自减;
    6.如果所有数都能整除b,那么b为这些数的最大公因数;

    三、算法流程图:

    最大公因数
    在这里插入图片描述
    最小公倍数
    在这里插入图片描述

    四、代码部分

    #include<stdio.h>
    #include<stdlib.h>
    
    
    void get_number(int array[],int b)             //用来获取数据
    {
    	
    	int i=0;
    	
    	for (i=0;i<=b-1;i++)
    	{
    		printf("请输入第%d个数:",i+1);
    		scanf("%d",&array[i]);
    		while(array[i]<=0)
    		{
    			printf("请输入正整数\n");
    			scanf("%d",&array[i]);
    		}
    	}
    	printf("输入成功\n");
    	printf("\n");
    
    }
    
    void BubbleSort(int array[],int n)
    {
    	int i,j,temp;                    //外循环控制循环趟数
    
    	 for(i=0; i<n-1; i++)             //内循环选择要进行比较的数
    	{
    
    		for(j=0; j<n-1-i; j++)
    		{
    		   if(array[j]>array[j+1])
    		   {
    			temp=array[j];
    			array[j]=array[j+1];
    			array[j+1]=temp;
    		   }
    		}
    	}
    	printf("排序后的这几个数:");
    	for(i=0;i<n;i++) 
    	{
    		printf("\t%d",array[i]);
    	}
    	
    	
    }
    
    void manage(int array[],int b)                  //求取最大公因数
    {
    	int e; 
    	e=array[0];
    	int c=1;
    	int d=0;
    	int f;
    	f=array[b-1];
    	while(c!=0)
    	{
    		c=0;
    		for(d=0;d<b;d++)
    		{
    			if(array[d]%e==0)
    			{
    				c+=0;
    		
    			}
    			else
    			{
    				c+=1;
    			}
    		}
    		if(c!=0)	e--;
    	}
    	printf("\n");
    	printf("\n这几个数的最大公因数为:\t%d\n",e);
    
    	c=1;
    	while(c!=0)
    	{
    		c=0;
    		for(d=0;d<b;d++)
    		{
    			if(f%array[d]==0)
    			{
    				c+=0;
    		
    			}
    			else
    			{
    				c+=1;
    			}
    		}
    		if(c!=0)	f++;
    	}
    	printf("\n这几个数的最小公倍数为:\t%d\n\n\n\n",f);
    
    
    
    	
    }
    
    	
    
    
    
    void home()
    {
    	int a[50];
    	int b;
    
    	printf("求最大n个数的最大公因数");
    	printf("\n");
    	printf("请输入你要得到几个数的最大公因数:");
    	scanf("%d",&b);
    	get_number(a,b); 
    	BubbleSort(a,b);  
    	manage(a,b);         
    }
    
    int main()
    {
    	while(1)
    	{
    		home();
    	}
    	system("pause");
    	return 0;
    }
    
    
    

    五、运行结果截图

    1、正常运行
    在这里插入图片描述
    2、输入不正确的数后
    在这里插入图片描述

    六、测试部分

    测试不同个数在程序运行下的最大公因数和最小公倍数
    利用随机数函数生成n个随机数并且输入到数组中,求取数组中的数的最大公因数和最小公倍数。
    随机数的范围:1~dis;
    随机数个数:n;

    #include<stdio.h>
    #include<stdlib.h>
    #define Random(x) (rand() % x) //通过取余取得指定范围的随机数
    
    void get_number(int array[],int b)
    {
    		
            int i;
            int dis;       //产生[0, dis)之间的随机数,注意不包括dis  
    		printf("请输入随机数范围最大界限:");
    		scanf("%d",&dis);      
            for(i=0; i<b; i++)
            {   
            	array[i]=Random(dis)+1; 
            }
           
    } 
    
    void BubbleSort(int array[],int n)
    {
    	int i,j,temp;                    //外循环控制循环趟数
    
    	 for(i=0; i<n-1; i++)             //内循环选择要进行比较的数
    	{
    
    		for(j=0; j<n-1-i; j++)
    		{
    		   if(array[j]>array[j+1])
    		   {
    			temp=array[j];
    			array[j]=array[j+1];
    			array[j+1]=temp;
    		   }
    		}
    	}
    	printf("排序后的这几个数:");
    	for(i=0;i<n;i++) 
    	{
    		printf("\t%d",array[i]);
    	}
    	
    	
    }
    
    void manage(int array[],int b)                  //求取最大公因数
    {
    	int e; 
    	e=array[0];
    	int c=1;
    	int d=0;
    	long int f;
    	f=array[b-1];
    	while(c!=0)
    	{
    		c=0;
    		for(d=0;d<b;d++)
    		{
    			if(array[d]%e==0)
    			{
    				c+=0;
    		
    			}
    			else
    			{
    				c+=1;
    			}
    		}
    		if(c!=0)	e--;
    	}
    	printf("\n");
    	printf("\n这几个数的最大公因数为:\t%d\n",e);
    
    	c=1;
    	while(c!=0)
    	{
    		c=0;
    		for(d=0;d<b;d++)
    		{
    			if(f%array[d]==0)
    			{
    				c+=0;
    		
    			}
    			else
    			{
    				c+=1;
    			}
    		}
    		if(c!=0)	f++;
    	}
    	printf("\n这几个数的最小公倍数为:\t%d\n\n\n\n",f);
    
    	
    }
    
    
    void home()
    {
    	int a[50];
    	int b;
    
    	printf("求最大n个数的最大公因数");
    	printf("\n");
    	printf("请输入你要得到几个数的最大公因数:");
    	scanf("%d",&b);
    	get_number(a,b); 
    	BubbleSort(a,b);  
    	manage(a,b);         
    }
    
    int main()
    {
    	while(1)
    	{
    		home();
    	}
    	system("pause");
    	return 0;
    }
    
    
    
    
    

    测试结果:
    1~20之间的随机数
    2~5之间的数字量
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    1~40之间的随机数
    2~5之间的数量个数

    在这里说明一下,测试的随机数是伪随机数,但是由于输入的数量数目的不同,就可以解决伪随机数这个问题。虽然这个获取随机的函数方法是更具环境来决定的,但是我们在获取随机数的时候只要有一处是采用了随机的方法,我们便获取了随机数。本次测试便是如此。通过变换想要取得数量的个数以及范围的大小,获得随机数。

    这里也建议采用本次测试的方法的同学们,尽量将随机数个数和范围调小一点,不然计算机获取时间过长。

    七、出现问题及心得体会

    这次作业,本来感觉是比较简单的,但是整体实践下来,发现还是有不少问题对于现在的我来说还是比较困难的,自己的动手能力比较差,有些想法的实施缺乏经验,应该多加练习。
    遇到的第一个问题就是我在确定好我的思路后,没有模块化我的完成过程。所以我在第一遍完成我的代码时,出错了,却无法具体到某一部分,先对于繁杂的检查过程,我发现还是从新设计一下我的思路,将处理过程模块化,然后分布进行。这样在检查的过程中能够很好地检查错误,更能高效的完成处理过程。
    遇到的第二个问题便是我的核心处理过程。穷举法的思路出现了问题。还是过于自信,对于之前的2个数的最大公因数,我感觉很简单,但是发现实施还是有点困难。这次的多个数的最大公因数,需要解决的问题更多。
    原先代码:

    BubbleSort(a,i);  //冒泡法由小到大排序
    	b=a[0];    //取最小的数
    
    	while(c==0)
    	{
    		for(d=0;d<i;d++)
    		{
    			if(a[d]%b==0)
    			{
    				c=0;
    			//	d++;
    			}
    			else
    			{
    				c=1;
    			//	break;
    			}
    		}
    		b--;
    

    }
    改进后代码:

    	while(c!=0)
    	{
    		c=0;
    		for(d=0;d<b;d++)
    		{
    			if(array[d]%e==0)
    			{
    				c+=0;
    		
    			}
    			else
    			{
    				c+=1;
    			}
    		}
    		if(c!=0)	e--;
    	}
    

    这前后的改进过程我发现一个清晰的程序设计图是多么重要。
    本次实验我是采用数组的方式储存数据,然后用冒泡法进行排序,取组头最小数求最大公因数和去组尾求最小公倍数。但是从时间复杂度来说,利用这种排序法进行排序,然后利用穷举法求最大公因数和最小公倍数,不一定比我不给数组排序,直接从数组里面获得一个数实现穷举法获得结果要优化的多。我本想采用更加节省空间和时间的排序方法,但是回过头复习之前的课文,发现没有把它好好学到自己的脑子里面。平成作业应该要求自己用多种方法实现,及时发现自己在学习上的不足,然后快速补充。

    展开全文
  • 常用的辗转相除法,更相减损法多用于处理两个数上,如果碰到多个数字怎么来他的最大公约数和最小公倍数呢?

    做练习的时候碰到了这种问题,对于两个数的求法我们可以用辗转相除法

    return x if y==0 else gck(y,x%y) 
    

    求出它们的最大公因数,
    然后再用两数之积/最大公因数

    return x*y/gck(x,y)
    

    求出最小公倍数,那么对于多个数字,我们可不可以仿照这种方法来求解呢?

    分析

    如果把多个数字看作一个列表,我们要做的就是对其相邻的两个元素进行一个最小公倍数的运算,将得到的结果与下一位数字再进行运算,依此类推。
    但是这样进行的话可能会有一些问题,举例子来说
    [1,2,3,4,5]
    正常推理下最小公倍数为60
    但按照刚才的方法来做,其结果依次为

    [2,3,4,5]
    [6,4,5]
    [24,5]
    [120]
    

    为什么会这样呢?
    究其原因,是因为列表中的[2,4]这两个存在倍数关系,他们的最小公约数为2,但在列表中的公约数为1,致使所得结果多乘了2,所以,我们要先对列表中的数字进行一些处理

    列表处理

    		for i in range(len(x)):        #对列表元素进行操作
                if x[i] == 1:      #如果列表元素为1,不进行任何操作
                    continue
                else:  
                #新建一个列表,若其中没有任何元素,将x[]中第一个不为1的元素插入
                    if len(y) == 0:  
                        y.append(x[i])
                    for j in range(len(y)):		#对列表y[]进行处理
                        if x[i]<y[j]:#如果后插入比先插入要小,则互换
                            temp = x[i]
                            x[i] = y[j]
                            y[j] = temp
                        if x[i] % y[j] != 0:	#如果x中元素对y中元素取余不为0
                            if j == len(y) - 1:  #判断当前元素是否是y[]最后一个元素,即x[i]是否被y[j]全部元素取余
                                y.append(x[i])
                            continue
                        else:     #如果找到有倍数关系的值,将大的值加入y[]中
                            if x[i] > y[j]: 
                                y[j] = x[i]
                            break
    

    处理方法如上,在这我简单的再说一下,
    1.第一个插入y[]的元素不为1,因为1能被全部数整除
    2.将含有倍数关系的较大值插入进来代替较小值
    3.必须保证后进的值要大于当前比较元素

    如对x[1,2,3,4,5]进行操作
    首先取1,不符合条件,继续向下执行
    取得2,此时y[]中为空,将2插入,继续执行
    取得3,y[]不为空,取y[]长度为1,进行取余操作,3%2!=0,将3插入,继续执行
    取得4,y[]不为空,取y[]长度为2,进行取余操作,4%2==0,判断4>2,将2替换为4,继续执行
    取得5,5%4!=0,5%3!=0,插入
    最终结果为[4,3,5]

    最大公约数

    对列表处理完成之后,我们开始进行最大公约数的处理

            for i in range(len(y) - 1):
                z.append(y[i])
                z.append(y[i + 1])
                while (z[i + 1] > 0):
                    l = z[0] % z[i + 1]
                    z[0] = z[i + 1]
                    z[i + 1] = l
    

    首先取得y[]中前两位元素,将其插入新列表z
    而后进行两位数的公约数算法
    如果后一位数不为0,将第一位数%后一位数,取得的结果设为l,同时对数据进行交换,正如文章开头写的那行代码一样,直到后一位数为0,代表此时的两个数已经可以整除,此时的前一位数即为两数最大公因数

    稍后我会解释为什么在这里要用z[0]来进行比较

    而后我们进行公倍数的计算

    最小公倍数

    lcm = y[i] * y[i + 1] // z[0]
                w.append(lcm)
            if len(w) != 1:
                get_lcm(w)
    

    在这里已经能明显看到,z[0]是整个列表的最大公因数,因为每进行一次处理,z[]的后一位值就会变成0。
    我们新建了一个w列表,用来存放所求得的最小公倍数,如果w的长度为1,说明里面只有一位数字,那就是我们要求的最小公倍数,如果不是,则递归调用,直到完成。

    完整代码

    def get_lcm(x):
            y=[]
            z=[]
            w=[]
            #列表处理
            for i in range(len(x)):
                if x[i] == 1:
                    continue
                else:
                    if len(y) == 0:
                        y.append(x[i])
                    for j in range(len(y)):
                        if x[i]<y[j]:
                            temp = x[i]
                            x[i] = y[j]
                            y[j] = temp
                        if x[i] % y[j] != 0:
                            if j == len(y) - 1:
                                y.append(x[i])
                            continue
                        else:
                            if x[i] > y[j]:
                                y[j] = x[i]
                            break
            #求公因数
            for i in range(len(y) - 1):
                z.append(y[i])
                z.append(y[i + 1])
                while (z[i + 1] > 0):
                    l = z[0] % z[i + 1]
                    z[0] = z[i + 1]
                    z[i + 1] = l
     			#求公倍数
                l = y[i] * y[i + 1] // z[0]
                w.append(l)
            if len(w) != 1:
                get_lcm(w)   #继续递归执行
    

    附上几个例子
    1.x[1,2,3,4,5,2]
    在这里插入图片描述
    2.x[2,4,8,6]
    在这里插入图片描述3.x[15,25,30]

    在这里插入图片描述
    如果我有什么不对的地方,请大家帮我指正出来,我会再细致的考虑一下,谢谢大家。

    展开全文
  • Sample Input 4 18 12 24 30 Sample Output 6 14 俩数的最大公因数可以用辗转相除法(自己写gcd函数或者用algorithm中的__gcd( , )函数),求多个数最大公因数可以先找出这些数中的最小的数,然后用for循环从...

    Time Limit: 1000 MS Memory Limit: 32768 KB

    Description
    The company have n(n<=100) long cables(the length is not necessarily the same),we assume that the length of every long cable is an integer and not exceeded 10000 meters. Now we cut them into short cables with the same length. We are required not to waste every long cable and the length of the short cable is the longer the better. Please calculate the longest length of short cable and how many short cables after cutting.

    Input
    The input contains two lines.
    The first line is n, represents the number of long cables.
    The second line has n positive integers separated by spaces, represent the length of long cable.

    Output
    The first line represent the longest length of short cable.
    The second line represent the number of short cables.

    Sample Input
    4
    18 12 24 30

    Sample Output
    6
    14

    求俩数的最大公因数可以用辗转相除法(自己写gcd函数或者用algorithm中的__gcd( , )函数),求多个数的最大公因数可以先找出这些数中的最小的数,然后用for循环从那个最小的数遍历到0,若中途遍历到的一个数可以被所有那些数整除,那么此时遍历到的那个数就是那些数的最大公因数。下面是代码:

    #include<iostream>
    #include<vector>
    using namespace std;
    int main()
    {
    	vector<int> vt;
    	int n,a,min=99999999,flag=1,mi,ans=0;
    	cin>>n;
    	for(int i=1;i<=n;++i)
    	{
    		cin>>a;
    		if(a<min) min=a;
    		vt.push_back(a);
    	}
    	//cout<<min<<endl;
    	for(int i=min;i>=0;--i)
    	{
    		//cout<<" "<<endl;
    		//cout<<vt.size()<<endl;
    		//cout<<flag<<endl;
    		for(int j=0;j<vt.size();++j)
    		{
    			if(vt[j]%i!=0)
    			{
    				flag=0;
    				break;
    			}
    		}
    		if(flag)
    		{
    			mi=i;
    			break;
    		}
    		flag=1;
    	}
    	cout<<mi<<endl;
    	for(int i=0;i<vt.size();++i)
    	{
    		ans+=vt[i]/mi;
    	}
    	cout<<ans<<endl;
    	return 0;
    }
    
    展开全文
  • def Common_multiple(number1, number2): # 两个数的最小倍数 while number1 % number2 !...def Maximum_common_divisor(*number): # 任意多个数的最小倍数 while len(number) > 1: numbe...
  • 最大公因数

    2017-04-20 11:08:00
    时候我们要处理两个数最大公因数,比如分数化简。因此需要一种高效率的方法找到最大公因数。 朴素法: void Gcd(int &a, int &b) { int i, j, curr = min(a,b); //从两数最小值开始 for...
  • 小学数学电子课本电子课本丨在线课堂习题试卷丨教辅资料求最大公因数是小学重点掌握的知识点,不仅关系到小学重要考试,在初中数学学习中,也是很重点知识点的学习根基。很同学认为在小学课本中,最大公约数已学...
  • 这道题其实不难,但是我想复杂了 我想的是把每个数质因数分解,然后每次就枚举每个质因数 来最小公倍数。 然后想了想这样复杂度将...之后对最大公因数的限制就越少。 所以我们可以把因数从大到小枚举,来答案...
  • 求最大公约数: (1)找到a1,a2,..,an中的最小非零项min,若有多个最小非零项则任取一个 (2) min以外的所有其他非0项ak用ak modmin代替;若没有除min以外的其他非0项,则转到(4) (3)转到(1) (4)a1,a2,...
  • 常见算法题(1)求最大公因数

    千次阅读 2018-06-22 14:26:59
    求最大公因数的算法有: (1)辗转相除法 有两整数a和b: ① a%b得余数c ② 若c=0,则b即为两的最大公约数 ③ 若c≠0,则a=b,b=c,再回去执行① 例如求27和15的最大公约数过程为: 27÷15 余12 15÷12余3 12÷3...
  • 最大公因数数gcd模板

    2019-09-26 00:11:57
    最大公因数那,顾名思义就是两个数共有的因数里最大的那个,辗转相除求最大公因数所用的原理就是两个数的最大公因数等于这两个数中【较小的那个数】和【两数之差】的最大公因数,证明如下:    描述:关于辗转...
  • C语言案例---求最大公约数和最小公倍数 --if、while 语句应用1、最大公约数,也称最大公因数、最大公因子,是一种数学概念,指两个或多个整数共有约数中最大的一个。2、最小公倍数是一种数学概念,是指两个或多个...
  • Common Divisors(算多个数公因数个数) ** *链接:*https://codeforces.com/problemset/problem/1203/C 题意:寻找所有可以整除以上数字的约数,并且记录个数。 思路:这道题,我们用最小的数字与其余数字...
  • 也称最大公因数、最大公因子,a, b的最大公约数记为(a,b),同样的,a,b,c. 求最大公约数有多种方法,常见的有质因数分解法、短除法、辗转相除法、更相减损法。”方法1:辗转相除法(欧几里得算法)  欧几里德...
  • 求最大公因数的方法有很,除了辗转相除法,再给大家说一种:先求出两个数中最小的,用两个数分别除以最小数到2,如果都能除尽,说明这数为最大公因数;用两个数除以最大公因数的两个商*最大公因数即为最小公倍数。#...
  • 两个或多个自然数的共有约数中最大的一个,叫做它们的最大公约数,也称最大公因数最大公因数求最大公约数有多种方法,常见的有质因数分解法、短除法、辗转相除法、辗转相减法、更相减损法等。【问题】输入两个正...
  • 通常应用压力不大,一般人按照感觉能大差不差的求得两个数的最小公倍数的正确答案但是严谨的套路可能未必能够想起来,这里老调重弹一下8与16的最大公因数是8,最小公倍数是16,没有争议严格的步骤呢?首先要把两个数...
  • 定义:公因数只有1的两个数,叫做互质数。2.法:(1)两个质数的互质数:5和7(2)两个合数的互质数:8和9(3) 一质一合的互质数:7和8(4)两数互质的特殊情况:1和任何自然数互质;相邻两个自然数互质;两个...
  • 两个数的最大公约数 function fn (a, b) { if (b===0) { return a } else { ...多个数的最大公约数 ...先出两个的最大公因数,然后再用出来的最大公因数和第三个,依次类推 f...
  • C语言 个数最大公约数

    千次阅读 2019-03-18 22:53:47
    个数的最大公约数。 最大公约数定义: 如果a,b是非零整数,而整数q同时是a,b的因数,我们便把q叫做a,b的公因数。...我们把a,b的所有公因数中最大的一个公因数d,叫做a,b的最大公因数,记作 d = (a,b)。 (摘抄自...
  • 最大公因数,也称最大公约数、最大公因子,指两个或多个整数共有约数中最大的一个。a,b的最大公约数记为(a,b),同样的,a,b,c的最大公约数记为(a,b,c),多个整数的最大公约数也有同样的记号。求最大公约数...

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 164
精华内容 65
关键字:

多个数求最大公因数