精华内容
下载资源
问答
  • 最大公约数和最小公倍数(C语言)

    千次阅读 2019-03-23 21:01:28
    基本要求: 求N个数的最大公约数和最小公倍数。用C或C++或java或python语言实现程序解决问题。 题目分析 辗转相除法(又名欧几里德法)C语言中用于计算两个正整数a,b的最大公约数和最小公倍数,实质它依赖于下面的...

     

    基本要求: 求N个数的最大公约数和最小公倍数。用C或C++或java或python语言实现程序解决问题。

    1. 题目分析

    辗转相除法(又名欧几里德法)C语言中用于计算两个正整数a,b的最大公约数和最小公倍数,实质它依赖于下面的定理:

     

                                a                     b=0

     

    gcd(a,b) =

     

                            gcd(b,a mod b)         b!=0

     求N个数的最大公约数和最小公倍数思想和其一样,通过调用函数实现。

    2.算法构造

      最大公约数和最小公倍数的关系:假设有a,b两个数,p,q分别是它们的最大公约数和最小公倍数,则有:q=(a*b)/p。要求n个数的最大公约数,只需先求出两个数的最大公约数,然后再将这两个数求出的结果和下一个数求最大公约数就可以了,如此往复,即可求出这n个数的最大公约数。

    3.算法实现程序源代码

    #include <stdio.h>
    #include<stdlib.h>
    /*辗转相除法*/
    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;            /*返回最大公约数到调用函数处*/ 
    }
    int divisor2(int t[],int n)    /*求n个数的最大公约数*/
    {
    	int i;
    	int c=t[0];
    	for(i=1;i<n;i++)
    	{
    		c=divisor1(c,t[i]);
    	}
    	return c;
    }
    int multiple1(int a,int b)  /*自定义函数求两数的最小公倍数*/
    {
      int divisor1(int a,int b); /*自定义函数返回值类型*/
      int temp;
      temp=divisor1(a,b);  /*再次调用自定义函数,求出最大公约数*/
      return  (a*b/temp); /*返回最小公倍数到主调函数处进行输出*/
    }
    int multiple2(int t[],int n)    /*求n个数的最小公倍数*/
    {
    	int i;
    	int d=1;
    	for(i=0;i<n;i++)
    	{
    		d=multiple1(d,t[i]);
    	}
    	return d;
    }
    int main()
    {	int N,n,m,i,a[100],b[4],sum=0,x=0;
    	printf("您要求几个数字的最大公约数:\n");
    	scanf("%d",&n);
        printf("请输入%d个数字:\n",n);
    	for(i=0;i<n;i++)
    	{
    		scanf("%d",&a[i]);
    		if(a[i]<0)
    		{
    			printf("请重新输入第%d个数:\n",i+1);
    			scanf("%d",&a[i]);
    		}
    	}
    	printf("这%d个数的最大公约数为%d\n",n,divisor2(a,n));
        printf("这%d个数的最小公倍数为%d\n",n,multiple2(a,n));
    	//提高要求
    	printf("您要输入几组数据:\n");
    	scanf("%d",&N);
    	printf("请输入数据:\n");
    		for(;N>0;N--)                
    		{
    			for(m=0;m<4;m++)        
    		{
    			scanf("%d",&b[m]);
    		}
    		
    		if(b[0]%b[1]||b[3]%b[2])      //判断是否满足题目条件
    	
    			printf("输入不符合条件,请重新输入:\n");
    			for(m=0;m<4;m++)
    			{
    				scanf("%d",&b[m]);
    			}
    		
    		for( x;x<=b[3];x++)          //循环计算有多少个满足条件的数
    		{
    			if(divisor1(x,b[0])==b[1]&&multiple1(x,b[2])==b[3])   //调用计算最大公约数和最小公倍数的函数
    				sum++;
    		}
    		printf("一共有%d个数满足条件\n",sum);
                                
    		}
    
    }

    4.调试、测试及运行结果

    1. 调试结果

    输入3,9,12

    在multiple2()函数出调试,截图如下所示

     

    1. 测试结果

    1.测试最大公约数

    #include <stdio.h>
    #include<stdlib.h>
    /*辗转相除法*/
    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;            /*返回最大公约数到调用函数处*/ 
    }
    
    int divisor2(int t[],int n)    /*求n个数的最大公约数*/
    {
    	int i;
    	int c=t[0];
    	for(i=1;i<n;i++)
    	{
    		c=divisor1(c,t[i]);
    	}
    	return c;
    }
    int main()
    {
    	int n,i,a[100];
    	printf("您要求几个数字的最大公约数:\n");
    	scanf("%d",&n);
        printf("请输入%d个数字:\n",n);
    	for(i=0;i<n;i++)
    	{
    		scanf("%d",&a[i]);
    		if(a[i]<0)
    		{
    			printf("请重新输入第%d个数:\n",i+1);
    			scanf("%d",&a[i]);
    		}
    	}
    	printf("这%d个数的最大公约数为%d\n",n,divisor2(a,n));
    	return 0;
    }	

     截图如下所示:

     

    1. 测试最小公倍数
    #include <stdio.h>
    #include<stdlib.h>
    /*辗转相除法*/
    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;            /*返回最大公约数到调用函数处*/ 
    }
    
    int multiple1(int a,int b)  /*自定义函数求两数的最小公倍数*/
    {
      int divisor1(int a,int b); /*自定义函数返回值类型*/
      int temp;
      temp=divisor1(a,b);  /*再次调用自定义函数,求出最大公约数*/
      return  (a*b/temp); /*返回最小公倍数到主调函数处进行输出*/
    }
    int multiple2(int t[],int n)    /*求n个数的最小公倍数*/
    {
    	int i;
    	int d=1;
    	for(i=0;i<n;i++)
    	{
    		d=multiple1(d,t[i]);
    	}
    	return d;
    }
    int main()
    {
    	int n,i,a[100];
    	printf("您要求几个数字的最大公约数和最小公倍数:\n");
    	scanf("%d",&n);
        printf("请输入%d个数字:\n",n);
    	for(i=0;i<n;i++)
    	{
    		scanf("%d",&a[i]);
    		if(a[i]<0)
    		{
    			printf("请重新输入第%d个数:\n",i+1);
    			scanf("%d",&a[i]);
    		}
    	}
    	printf("这%d个数的最小公倍数为%d\n",n,multiple2(a,n));
    	return 0;
    }

     截图如下所示:

     

     

    1. 运行结果

    1.输入两个互质的自然数,截图如下所示

     2.输入两个自然数

     

    3.输入三个有公约数的自然数

    4.输入三个互质的自然数

    5.经验归纳

    此次实验在上次求两个最大公约数的基础上进行了扩展,相对来说比较简单,通过调用函数来实现求N个最大公约数和最小公倍数的功能,在上次实验的基础上做此次实验,就感觉比较简单,所以还是要多多练习,不断实践!Hankson问题基本要求实现了,但是还是没有代码可读性不高,还需继续完善修改。具体完善后再修改~~~Fighting  

     

    展开全文
  • 最大公约数和最小公倍数:两个自然数的最大公约数与它们的最小公倍数的乘积等于这两个数的乘积 1.质因数分解法: 把每个数分别分解质因数,再把各数中的全部公有质因数提取出来连乘,所得的积就是这几个数的最大公...
    最大公约数和最小公倍数:两个自然数的最大公约数与它们的最小公倍数的乘积等于这两个数的乘积
        1.质因数分解法:
            把每个数分别分解质因数,再把各数中的全部公有质因数提取出来连乘,所得的积就是这几个数的最大公约数
                例如:求24和60的最大公约数,先分解质因数,得24=2×2×2×3,60=2×2×3×5,24与60的全部公有的质因数是2、2、3,它们的积是2×2×3=12,所以,(24,60)=12
            把几个数先分别分解质因数,再把各数中的全部公有的质因数和独有的质因数提取出来连乘,所得的积就是这几个数的最小公倍数
                例如:求6和15的最小公倍数。先分解质因数,得6=2×3,15=3×5,6和15的全部公有的质因数是3,6独有质因数是2,15独有的质因数是5,2×3×5=30,
                     30里面包含6的全部质因数2和3,还包含了15的全部质因数3和5,且30是6和15的公倍数中最小的一个,所以[6,15]=30
    
        2.短除法:
            短除法求最大公约数,先用这几个数的公约数连续去除,一直除到所有的商互质为止,然后把所有的除数连乘起来,所得的积就是这几个数的最大公约数
            求最大公因数便乘一边,求最小公倍数便乘一圈。
            短除法的本质就是质因数分解法,只是将质因数分解用短除符号来进行
            短除符号就是除号倒过来。短除就是在除法中写除数的地方写两个数共有的质因数,然后落下两个数被公有质因数整除的商,之后再除,以此类推,直到结果互质为止(两个数互质)。
            而在用短除计算多个数时,对其中任意两个数存在的因数都要算出,其它没有这个因数的数则原样落下。直到剩下每两个都是互质关系。
            无论是短除法,还是分解质因数法,在质因数较大时,都会觉得困难。这时就需要用新的方法
    
        3.辗转相除法:求两个自然数的最大公约数的一种方法,也叫欧几里德算法
            377 ÷ 319 =1...58
            319 ÷ 58  =5...29
            58  ÷ 29  =2   ∴(319,377)=29
            用辗转相除法求几个数的最大公约数,可以先求出其中任意两个数的最大公约数,再求这个最大公约数与第三个数的最大公约数,依次求下去,直到最后一个数为止。
            最后所得的那个最大公约数,就是所有这些数的最大公约数
    
        4,更相减损法:
            第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。
            第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。
            则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数
            其中所说的“等数”,就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。
    package factor;
    
    import org.junit.Before;
    import org.junit.Test;
    
    import java.util.ArrayList;
    import java.util.List;
    
    public class FactorTest {
    
        /**
         * 最大公约数和最小公倍数:两个自然数的最大公约数与它们的最小公倍数的乘积等于这两个数的乘积
         *     质因数分解法:
         *         把每个数分别分解质因数,再把各数中的全部公有质因数提取出来连乘,所得的积就是这几个数的最大公约数
         *             例如:求24和60的最大公约数,先分解质因数,得24=2×2×2×3,60=2×2×3×5,24与60的全部公有的质因数是2、2、3,它们的积是2×2×3=12,所以,(24,60)=12
         *         把几个数先分别分解质因数,再把各数中的全部公有的质因数和独有的质因数提取出来连乘,所得的积就是这几个数的最小公倍数
         *             例如:求6和15的最小公倍数。先分解质因数,得6=2×3,15=3×5,6和15的全部公有的质因数是3,6独有质因数是2,15独有的质因数是5,2×3×5=30,
         *                  30里面包含6的全部质因数2和3,还包含了15的全部质因数3和5,且30是6和15的公倍数中最小的一个,所以[6,15]=30
         *
         *     短除法:
         *         短除法求最大公约数,先用这几个数的公约数连续去除,一直除到所有的商互质为止,然后把所有的除数连乘起来,所得的积就是这几个数的最大公约数
         *         求最大公因数便乘一边,求最小公倍数便乘一圈。
         *         短除法的本质就是质因数分解法,只是将质因数分解用短除符号来进行
         *         短除符号就是除号倒过来。短除就是在除法中写除数的地方写两个数共有的质因数,然后落下两个数被公有质因数整除的商,之后再除,以此类推,直到结果互质为止(两个数互质)。
         *         而在用短除计算多个数时,对其中任意两个数存在的因数都要算出,其它没有这个因数的数则原样落下。直到剩下每两个都是互质关系。
         *         无论是短除法,还是分解质因数法,在质因数较大时,都会觉得困难。这时就需要用新的方法
         *
         *     辗转相除法:求两个自然数的最大公约数的一种方法,也叫欧几里德算法
         *         377 ÷ 319 =1...58
         *         319 ÷ 58  =5...29
         *         58  ÷ 29  =2   ∴(319,377)=29
         *         用辗转相除法求几个数的最大公约数,可以先求出其中任意两个数的最大公约数,再求这个最大公约数与第三个数的最大公约数,依次求下去,直到最后一个数为止。
         *         最后所得的那个最大公约数,就是所有这些数的最大公约数
         *
         *     更相减损法:
         *         第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。
         *         第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。
         *         则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数
         *         其中所说的“等数”,就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。
         *
         */
    
        @Test
        public void method1() {
            System.out.println("质因数分解法:\n" +
                    "        把每个数分别分解质因数,再把各数中的全部公有质因数提取出来连乘,所得的积就是这几个数的最大公约数\n" +
                    "            例如:求24和60的最大公约数,先分解质因数,得24=2×2×2×3,60=2×2×3×5,24与60的全部公有的质因数是2、2、3,它们的积是2×2×3=12,所以,(24,60)=12\n" +
                    "        把几个数先分别分解质因数,再把各数中的全部公有的质因数和独有的质因数提取出来连乘,所得的积就是这几个数的最小公倍数\n" +
                    "            例如:求6和15的最小公倍数。先分解质因数,得6=2×3,15=3×5,6和15的全部公有的质因数是3,6独有质因数是2,15独有的质因数是5,2×3×5=30,\n" +
                    "                 30里面包含6的全部质因数2和3,还包含了15的全部质因数3和5,且30是6和15的公倍数中最小的一个,所以[6,15]=30");
            int a = 60, b = 30;
            List<Integer> a1 = getPrimeFactors(a);
            List<Integer> b1 = getPrimeFactors(b);
    
            //得到他们的公有质因数:
            //求积
            a1.retainAll(b1);
            int max = 1, min = 1;
            for (Integer x : a1) {
                if (b1.contains(x)) {
                    b1.remove(x);
                    max *= x;
                } else {
                    min *= x;
                }
    
            }
    
            System.out.println("最大公因数:" + max);
    
    /*        int quadrature2 = gcd;
            for (Integer x : a1) {
                if (!commonFactorList.contains(x)) {
                    quadrature2 *= x;
                }
            }
            for (Integer x : b1) {
                if (!commonFactorList.contains(x)) {
                    quadrature2 *= x;
                }
            }*/
    
            System.out.println("最小公倍数:" + min);
        }
    
        /**
         * @param num
         * @return 存储质因子序列的数组
         * @描述 返回一个数的质因子序列, 这里不考虑 1
         */
        private List<Integer> getPrimeFactors(int num) {
            List<Integer> factorList = new ArrayList<>();
    
            num = Math.abs(num);
            int i = 2;
            int k = 2;
            while (num >= k) {
                if (num == k) {
                    factorList.add(k);
                    break;
                } else if (num % k == 0) {
                    factorList.add(k);
                    num = num / k;
                } else {
                    k++;
                }
            }
    
            /*int start = 2;
            while (start < num) {
                if (num % start == 0) {
                    factorList.add(start);
                    num /= start;
                //    start = 2;
                } else {
                    start++;
                }
            }
            factorList.add(num);    //*/
            return factorList;
        }
    
    
        @Test
        public void method2() {
            System.out.println("短除法:\n" +
                    "        短除法求最大公约数,先用这几个数的公约数连续去除,一直除到所有的商互质为止,然后把所有的除数连乘起来,所得的积就是这几个数的最大公约数\n" +
                    "        求最大公因数便乘一边,求最小公倍数便乘一圈。\n" +
                    "        短除法的本质就是质因数分解法,只是将质因数分解用短除符号来进行\n" +
                    "        短除符号就是除号倒过来。短除就是在除法中写除数的地方写两个数共有的质因数,然后落下两个数被公有质因数整除的商,之后再除,以此类推,直到结果互质为止(两个数互质)。\n" +
                    "        而在用短除计算多个数时,对其中任意两个数存在的因数都要算出,其它没有这个因数的数则原样落下。直到剩下每两个都是互质关系。\n" +
                    "        无论是短除法,还是分解质因数法,在质因数较大时,都会觉得困难。这时就需要用新的方法");
            int a = 24, b = 240;
            int gcd = 1;
            for (int i = 2; i <= Math.min(a, b); i++) {
                if (a % i == 0 && b % i == 0) {
                    gcd *= i;
                    a = a / i;
                    b = b / i;
                    i--;
                }
            }
            System.out.println("最大公因数:" + gcd);
            System.out.println("最小公倍数:" + (gcd * a * b));
        }
    
        @Test
        public void method3() {
            System.out.println("辗转相除法:求两个自然数的最大公约数的一种方法,也叫欧几里德算法\n" +
                    "        377 ÷ 319 =1...58\n" +
                    "        319 ÷ 58  =5...29\n" +
                    "        58  ÷ 29  =2   ∴(319,377)=29\n" +
                    "        用辗转相除法求几个数的最大公约数,可以先求出其中任意两个数的最大公约数,再求这个最大公约数与第三个数的最大公约数,依次求下去,直到最后一个数为止。\n" +
                    "        最后所得的那个最大公约数,就是所有这些数的最大公约数");
            int a = 60, b = 24;
            int quadrature = a * b;
            int gcd = 1, remainder;
            for (; ; ) {
                int max = Math.max(a, b);
                int min = Math.min(a, b);
                remainder = max % min;
                if (remainder == 0) {
                    gcd = min;
                    break;
                }
                a = min;
                b = remainder;
            }
            System.out.println("最大公因数:" + gcd);
            System.out.println("最小公倍数:" + (quadrature / gcd));
        }
    
        /**
         * 辗转相除法(欧几里得算法)
         * 思路:取两个数中最大的数做除数,较小的数做被除数,用最大的数除较小数,如果余数为0,则较小数为这两个数的最大公约数,如果余数不为0,用较小数除上一步计算出的余数,直到余数为0,则这两个数的最大公约数为上一步的余数。
         * 1、递归
         *
         * @param a
         * @param b
         * @return
         */
        private static int gcd(int a, int b) {
            return (b == 0) ? a : gcd(b, a % b);
        }
    
        /**
         * 辗转相除法(欧几里得算法)
         * 2、非递归形式
         *
         * @param a
         * @param b
         * @return
         */
        private static int gcd2(int a, int b) {
            int rem = 0;
            while (b != 0) {
                rem = a % b;
                a = b;
                b = rem;
            }
            return a;
        }
    
        @Test
        public void method4() {
            System.out.println("更相减损法:\n" +
                    "        第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。\n" +
                    "        第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。\n" +
                    "        则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数\n" +
                    "        其中所说的“等数”,就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法");
            int a = 60, b = 24;
            int quadrature = a * b;
            int gcd = 1;
            while ((a & 1) == 0 && (b & 1) == 0) {  //如果a和b都是偶数
                gcd = gcd << 1;
                a = a >> 1;
                b = b >> 1;
            }
            while (a != b) {
                if (a > b) {
                    a -= b;
                } else {
                    b -= a;
                }
            }
            gcd *= a;
            System.out.println("最大公因数:" + gcd);
            System.out.println("最小公倍数:" + (quadrature / gcd));
        }
    
    }
    

     

    展开全文
  • C语言求最大公约数和最小公倍数

    千次阅读 2020-01-24 17:05:19
    //本程序要求的是最大公约数和最小公倍数 //最大公约数的求法是:先求出最小的数,然后大数开始除以较小的数,然后减一,一直到2 //如果除的时候出现最大的数字除以某个数字是等于0,或者是除到2依然没有等于0,那么...
    //本程序要求的是最大公约数和最小公倍数
    //最大公约数的求法是:先求出最小的数,然后大数开始除以较小的数,然后减一,一直到2
    //如果除的时候出现最大的数字除以某个数字是等于0,或者是除到2依然没有等于0,那么最大公约数就是1
    //最小公倍数的求法是:
    //如果大数字除以小数字等于0,那么最小公倍数就是最大的数字
    //如果不等于0,那么开始加一加一的求最小公倍数
    //本程序在C语言官网上的输出结果是50%的错误。现在尚不清楚是什么原因
    #include<stdio.h>
    int min(int a,int b);
    int maxa(int l,int o);
    int main()
    {
    	int a,b,d,e;
    	//其中a,b是输入的两个数字,d,e是最大和最小的两个数字
    	scanf("%d %d",&a,&b);
    	d=min(a,b);//求出两个数中最小的数字
    	e=maxa(a,b);//求出两个数中最大的数字
    	int flag=0;//设置flag=0;
    	//开始求最大公约数
    	int flag1=0;//作用是退出两层for()循环
    	for(int i=d;i>=2;i--)
    	{
    		if(e%d==0)
    		{
    			printf("%d ",d);
    			flag=1;
    			break;
    		}
    	}
    	if(flag==0)
    	{
    		printf("1 ");
    	}
    	//求毕最大公约数
    	//开始求最小公倍数
    	if(e%d==0)
    	{
    		printf("%d",e);
    	}
    	else
    	{
    		for(int k=1;k<=d;k++)
    		{
    			for(int f=1;f<=d;f++)
    			{
    				if(f*e==k*d)
    				{
    					printf("%d",f*e);
    					flag1=1;
    					break;
    				}
    			}
    			if(flag1==1)
    			{				
    				break;
    			}			
    		}
    		if(flag1==0)
    		{
    			printf("%d",e*d);
    		}
    	}
    	//最小公倍数求毕
    	return 0;
    }
    //判断最小的数字
    int min(int m,int n)
    {
    	int c=0;
    	if(m>=n)
    	{
    		c=n;
    	}
    	else
    	{
    		c=m;
    	}
    	return c;
    }
    //求较大的数字,以后可以直接用宏定义替换
    int maxa(int m,int n)
    {
    	int c=0;
    	if(m<=n)
    	{
    		c=n;
    	}
    	else
    	{
    		c=m;
    	}
    	return c;
    }

     

    展开全文
  • 最大公约数和最小公倍数(C++)

    千次阅读 2018-09-06 23:26:30
    编写程序求出两个或三个数的最大公约数和最小公倍数 要求: 1.用三种以上算法解决两个正整数最大公约数问题。 2. 求3个正整数的最大公约数和最小公倍数。 思路分析: 三种求最大公约数的方法分别是:辗转相除法...

    编写程序求出两个或三个数的最大公约数和最小公倍数
    要求:
    1.用三种以上算法解决两个正整数最大公约数问题。
    2. 求3个正整数的最大公约数和最小公倍数。
    思路分析:
    三种求最大公约数的方法分别是:辗转相除法;相减法;穷举法。
    求三个整数的最大公约数和最小公倍数编码时,通过if条件语句找出a,b,c三个数中最小的数,再通过穷举法得出三个数的最小公倍数与最大公约数。


    源代码:

    #include<iostream>
    using namespace std;
    class My{
    public:
        int a;//三个正整数
        int b;
        int c;
        int temp;
        int t;
        int x;//选择
        My();//构造函数
        int Max1(int x,int y);//辗转相除法
        int Max2(int x,int y);//相减法
        int Max3(int x,int y);//穷举法
        int Max_Min(int x,int y,int z);//求三个数的最大公约数和最小公倍数
    };
    My::My()//构造函数初始化
    {
        a=0;
        b=0;
        c=0;
        temp=0;
         t=0;
        x=0;//选择
    }
    
    int My::Max1(int x,int y)//辗转相除法
    {
        int a1=0;
        int b1=0;
        //int temp;
        if(a<b)//判断a,b大小,若b>a则交换
        {
            temp=a;
            a=b;
            b=temp;
        }
        a1=a;
        b1=b;
        while(a%b!=0)//b不是a的质因数
        {
            temp=a%b;//大数除以小数取余,直到余数为零,终止循环
            a=b;
            b=temp;
        }
        cout<<"辗转相除法求得的两个数的最大公约数为:"<<b<<endl;
        cout<<"最小公倍数为:"<<a1*b1/b<<endl;
        return 0;
    }
    int My::Max2(int x,int y)//相减法
    {
        int a1=0;
        int b1=0;
        /*(1)如果a>b,a=a-b;(2)如果a<b,b=b-a;(3)如果a=b,a或b就为这两个整数的最大公约数
     (4)如果a!=b,则再执行(1)或(2)*/
         /* a, b不相等,大数减小数,直到相等为止。*/ 
        a1=a;
        b1=b;
       while ( a!=b)
       {
             if (a>b)  
                 a=a-b;     
             else 
                 b=b-a;
       }
        cout<<"相减法求得的两个数的最大公约数为:"<<b<<endl;
        cout<<"最小公倍数为:"<<a1*b1/b<<endl;
        return b;
    }
    int My::Max3(int x,int y)//穷举法
    {
    
        int a1=0;
        int b1=0;
        if(a<b)
        {
            temp=a;
            a=b;
            b=temp;
        }
        a1=a;
        b1=b;
                /*余数都为0时结束循环*/
        for(temp=b;a%temp||b%temp;temp--);//
        cout<<"穷举法求得的两个数的最大公约数为:"<<temp<<endl;
        cout<<"最小公倍数为:"<<a1*b1/temp<<endl;
        return 0;
    }
    /*三个正整数求最大公约数与最小公倍数*/
    int My::Max_Min(int x,int y,int z)
    {
        int i=0;
        temp=a;
        //找出三个数中最小的数
        if(temp>b)
        {
            temp=b;
        }
        if(temp>c)
        {
            temp=c;
        }
        //
        //for(int i=0;i<=temp;i++)
        //{
        for(i=temp;a%i||b%i||c%i;i--);//穷举法直到余数为0停止循环
                //t=i;  //break;
        //}
        cout<<"三个数的最大公约数为:"<<i<<endl;
        cout<<"三个数的最小公倍数为:"<<a*b*c/i<<endl;
        return temp;
    }
    int main()
    {
        My m;//定义类对象m
        //int x=0;
        //int a=0;
        //int b=0;
        cout<<"请选择算法"<<endl;
        cout<<"1.辗转相除法,2.相减法3.穷举法,4.求三个数"<<endl;
        cin>>m.x;//将输入的值传给x选择计算方法
        switch(m.x)
        {
        //输入为1,选择辗转相除法
        case 1:
            cout<<"请输入需要计算的两个数"<<endl;
            cin>>m.a;
            cin>>m.b;
            m.Max1(m.a,m.b);
            break;
            //输入为2,选择相减法
        case 2:
            cout<<"请输入需要计算的两个数"<<endl;
            cin>>m.a;
            cin>>m.b;
            m.Max2(m.a,m.b);
            break;
            //输入为3,选择穷举法
        case 3:
            cout<<"请输入需要计算的两个数"<<endl;
            cin>>m.a;
            cin>>m.b;
            m.Max3(m.a,m.b);
            break;
            //输入为4,计算三个数
        case 4:
            cout<<"请输入需要计算的三个数"<<endl;
            cin>>m.a;
            cin>>m.b;
            cin>>m.c;
            m.Max_Min(m.a,m.b,m.c);
            break;
        }
        return 0;
    }

    辗转相除法的算法思想:
    两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数,如果用gcd(a,b)来表示a和b的最大公约数,那么根据辗转相除法的原理,gcd(a,b)=gcd(b,a mod (b)),其中mod()表示模运算,并且不妨让a>b,这样方便于模运算

     a%b得余数cc=0,则b即为两数的最大公约数c0,则a=b,b=c,再回去执行1

    相减法的算法思想:
    辗转相减法,即尼考曼彻斯法,

     如果a>b,a=a-b;
    如果a<b,b=b-a;
    如果a=b,a或b就为这两个整数的最大公约数
    如果a!=b,则再执行(1)或(2

    穷举法的算法思想:

           i= a(或b)
           若a,b能同时被i整除,则i即为最大公约数,结束
           i--,再回去执行2* 
    展开全文
  • C语言求最大公约数最小公倍数 1. 最大公约数 1.1 定义 ​ 最大公约数(Greatest Common Divisor,GCD),也称最大公因数最大公因子,是一种数学概念,指两个或多个整数共有约数中最大的一个。 1.2 解法一:常规...
  • 利用辗转相除法、穷举法、更相减损术、Stein算法求出两个数的最大公约数或者/和最小公倍数最大公约数:指两个或多个整数共有约数中最大的一个。 例如:【1224】12的约数有:1、2、3、4、6、12;24的约数有...
  • printf("下面求两个正整数的最大公约数和最小公倍数\n"); printf("请输入两个正整数(中间用空格间隔):"); scanf("%lf%lf",&m0,&n0); while((m0<0||n0<0)||(m0!=int(m0))||(n0!=int(n0))) { ...
  • 用LabVIEW求最大公约数和最小公倍数。可以自行选择数据。
  • 求n个数的最大公约数和最小公倍数C++

    千次阅读 多人点赞 2019-03-22 18:23:35
    求n个数的最大公约数和最小公倍数。 二、解题思路 1、首先我们可以利用辗转相除法编写一个函数gcd(int a,int b)来求出两个数的最大公约数,然后将输入的n个数放进数组a[100]中,编写一个函数GCD(int a[],int n)...
  • 【笔记|C++】最大公约数最小公倍数的四种求法

    千次阅读 多人点赞 2021-07-26 12:07:14
    前言 Hello!小伙伴! 非常感谢您阅读海轰的文章,倘若文中有错误的地方,欢迎您...最大公约数:也称最大公因数最大公因子,指两个或多个整数共有约数中最大的一个 最小公倍数:两个或多个整数公有的倍数叫做它们的
  • 求N个数的最大公约数和最小公倍数以及Hankson"逆问题"(python) 一、题目要求 1.基本要求: 求N个数的最大公约数和最小公倍数。用C或C++或java或python语言实现程序解决问题 2.提高要求: 已知正整数a0,a1,b0,b1,...
  • 递归求最大公约数和最小公倍数 最大公约数(GCD) int gcd(int a, int b) { return a % b ? gcd(b, a % b) : b; } 用辗转相除法求最大公约数,用递归写的代码会比循环简洁一些。 先判断a除以b...
  • C语言——求两个数的最大公约数和最小公倍数

    万次阅读 多人点赞 2018-05-03 21:51:56
    求两个数的最大公约数的常用方法:※“辗转相除法”,又名欧几里得算法。基本方法如下:设两数为ab(a&gt;b),用a除以b,得a÷b=q......r,若r=0 ,则最大公约数为b;若r≠0 ,则再用b÷r,得b÷r=q......r',若...
  • 输入a,b求出最大公约数和最小公倍数 解法:先求最大公约数 1.判断a,b最大最小值 2.ab分别两数的最小值相除,如果值都为0,即,两数的最小值为最大公约数,如果两数不为0,就将最小值减1设为z,然后ab再...
  • ①先判断两个数的大小,如果两数相等,则这个数本身就 是就是它的最大公约数。 ②如果不相等,则用大数减去小数,然后用这个较小数与它们相减的结果相比较,如果相等,则这个差就是它们的最大公约数,而如果不相等,...
  • 1 最小公倍数 1. 辗转相除法(欧几里得算法) 1.1 最大公约数算法 前提、定义两个数ab,a做被除数,b做除数,temp为余数; 第一步:将较大的数放在a中,较小的放在b中; 第二步:求a/b的余数temp; 第三步:temp=...
  • c语言求最大公约数和最小公倍数

    千次阅读 多人点赞 2021-02-25 16:19:55
    #include<stdio.h>...b,就要先进行交换,因为在取余的时候是固定格式c=a%b,(用小的数去取余大的数才会有余数)所以如论如何要把这两个数的最大值交给a*/ t = a; a = b; b = t; m = a * b
  • 【C语言】求最小公倍数和最大公约数(辗转相除法)

    万次阅读 多人点赞 2018-11-19 15:02:00
    用到的名词:最小公倍数,最大公约数,辗转相除法 一、名词解释: 1).最小公倍数: 最小公倍数(Least Common Multiple,LCM),如果有... 最小公倍数=两数的乘积/最大公约(因)数,解题时要避免和最大公约(因)...
  • 如何判断一个数是几位数呢?这个题目是灵活应用运算关系符的典型例题,开拓解决问题的思维方式,下面来看看是怎么做的吧!
  • 本文我就来给大家讲解讲解最大公约数和最小公倍数的实现
  • 任意给出两个数,求出它的最大公约数和最小公倍数 判断条件: 最小公倍数 = (num1 * num2) / 最大公约数 代码块: #1.接收两个数字 num1 = int(input('Num1: ')) num2 = int(input('Num2: ')) #2.找出两个数中...
  • 问题是:给出两个正整数,求出它们的最大公约数和最小公倍数。 输入 第一行输入一个整数n(0 随后的n行输入两个整数i,j(0 输出 输出每组测试数据的最大公约数和最小公倍数 样例输入 3 6 6 12 11 33 22 样例输出 6 6...
  • python中求最大公约数和最小公倍数

    千次阅读 2019-03-05 16:49:20
    最小公倍数 = 两个整数的乘积 / 最大公约数 所以我们首先要求出两个整数的最大公约数, 求两个数的最大公约数思路如下: 求最大公约数算法: 整数A对整数B进行取整, 余数用整数C来表示 举例: C = A % B 如果C等于...
  • 多个数求最大公约数和最小公倍数

    千次阅读 2019-03-22 23:20:58
    多个数求最大公约数和最小公倍数 问题描述 求N个数的最大公约数和最小公倍数,提供友好的输入输出,并进行输入数据的正确性验证 解题思路 N个数的最大公约数最小公倍数求解首先在输入数据时应该是无限的,用一个...
  • 求两个数的最大公约数和最小公倍数 最小公倍数=(i + j)/最大公约数 i = int(raw_input('请输入第一个数:')) j = int(raw_input('请输入第二个数:')) num_min = min (i,j) 求最小值 for n in range(1,num_min+1...
  • Java:求最大公约数和最小公倍数 话不多说直接上代码 public class TestGcd { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int a = scan.nextInt(); int b = scan....
  • c/c++语言求最大公约数最小公倍数

    千次阅读 多人点赞 2018-08-14 17:24:57
    本文将讲解如何求最大公约数和最小公倍数。 我将以3个部分进行讲解: 1.概念 2.原理 3.代码 一、概念 最大公约数的概念:如果有一个自然数a能被自然数b整除,则称a为b的倍数,b为a的约数。几个自然数公有的...
  • Java如何求解两个数的最大公约数和最小公倍数?如果是多个数又该怎么求解呢? 辗转相除法、穷举法、更相减损术来求解最大公约数,利用最大公约数来求解最小公倍数
  • 题目:从键盘输入两个正整数 a b,求其最大公约数和最小公倍数。 算法思想: 利用格式输入语句将输入的两个数分别赋给 a b,然后判断 a b 的关系,如果 a 小于 b,则利用中间变量 t 将其互换。再利用...
  • 基本要求:1.程序风格良好(使用自定义注释模板),两种以上算法解决...求3个正整数的最大公约数和最小公倍数。 #辗转相除法 def fun1(a,b): if a&lt;b: #如果a&lt;b则将a,b两数调换使大数作为被除数 a,b =...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,634
精华内容 3,853
关键字:

判断最大公约数和最小公倍数