求N个数的最大公约数和最小公倍数

骑猪看日落 2022-02-28 00:04 232阅读 0赞

## 标题：求N个数的最大公约数和最小公倍数 ##

一． 题目分析

求N个数的最大公约数和最小公倍数

二． 算法构造

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70]

三． 算法实现

#include<iostream>
    
    using
    namespace std;
    
    //求两个数的最小公倍数 
    
    int
    MIN(int x,int y)                       
    //先求两个数的最小公倍数的函数
    
    {          
    
        int i,z,min,max;     
    
        if(x==0)  
    
          return
    y;                                //先考虑x,y为0的情况，在这儿出过错    
    
           if(y==0)  
    
           return x;
    
           if(x<y)     
    
              
    z=x;
    
           else 
    
              
    z=y;
    
        for(i=z;i>=1;i--)
    
           {                        
    
              
    if(x%i==0&&y%i==0)         
    
                  {                                     //求出两个数的最大公约数数              
    
                         max=i;           
    
                         break;            
    
                  }      
    
           }      
    
           min = (x/max)*y;                          //x*y=min*max 
    
           return min;    
    
    }  
    
    //求两个数的最大公约数 
    
    int
    MAX(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 n;      
    
        int x[100];
    
          int
    i,min,maxx;
    
          cout<<"How
    many numbers :"<<endl;
    
                 while(cin>>n)
    
                        {      
    
                    cout<<"The numbers
    in the array:"<<endl;
    
                             for(i=0;i<=n-1;i++)      
    
                             {             
    
                                    cin>>x[i];               //先把要输的数存到数组中       
    
                                }
    
                                   min=MIN(x[0],x[1]);       //先把前两个数比较 
    
                                       maxx=MAX(x[0],x[1]);
    
                                    if(n>2)    
    
                                       {                       
    
                                        for(i=2;i<=n-1;i++)          
    
                                             { 
    
                                                  min=MIN(min,x[i]);
    
                                                     maxx=MAX(maxx,x[i]);            
    
                                              }      
    
                                       }
    
                                cout<<"The
    lowest common multiple is："<<endl; 
    
                                cout<<min<<endl;
    
                                cout<<"The
    greatest common divisor is："<<endl; 
    
                                cout<<maxx<<endl;
    
               } 
    
    return 0;
    
    }

四．调试，测试及运行结果

运行截图：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 1]

调试截图：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 2]

测试截图：

测试最小公倍数：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 3]

测试最大公约数：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 4]

五．经验归纳

在做这个程序之前，我们还做过两个数字之间寻找最大公约数和最小公倍数。这个基于那个程序之上多了一个循环的使用，算法思路是将要比较的数字放进一个数组中，从第一个数字开始一次向后寻找，即：第一个数和第二个数找到它们的最大公约数和最小公倍数，将求得的和后面一个数又求最大公约数和最小公倍数。  
其余的用之前的函数就可以实现。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70]: /images/20220228/1dfc5fdad8b84faeaf29435189b2f891.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 1]: /images/20220228/30496d9ce0a942929504891a80169859.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 2]: /images/20220228/b03aa0a602f34d969751db2138d60f79.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 3]: /images/20220228/b6b4ddd9b2e84b168fd80e617bbf22a8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 4]: /images/20220228/988535cbc5f44b89b83c85ef49f40ab4.png