多个数求最大公约数和最小公倍数
多个数求最大公约数和最小公倍数
-
问题描述
求N个数的最大公约数和最小公倍数，提供友好的输入输出，并进行输入数据的正确性验证
-
解题思路
N个数的最大公约数最小公倍数求解首先在输入数据时应该是无限的，用一个for循环实现。其次用一种算法写出求解两个数的最大公约数和最小公倍数，我选择辗转相除法。最后是求N个数的结果，可以想到用for循环和递归调用，将两个数的结果赋值给第一个数，后面的数赋值给第二个数，循环下去，两两求解，到最后一个数即可得到最终结果。
-
算法构造
long q=a[0]; for(j=1;j<n;++j) { q=divisor(q,a[j]); } cout<<q<<endl;这是for循环求N个数的最大公约数的代码，divisor函数用辗转相除法计算两个数的最大公约数，q的赋值很重要，q在下标指向数组第一个数时是第一个数的值，在数组中1 2个数计算一次后是两个数的最大公约数，即实现了将结果赋值给divisor函数第一个参数的过程。
long k=a[0]; for(i=1;i<n;++i) { k=multiple(k,a[i]); } cout<<k<<endl;
最小共倍数的求解相同，也用这种方法得到最终结果。
4. 算法实现
#include<iostream>
using namespace std;
int divisor(int a,int b)
{
int c;
while(b)
{
c=a;
a=b;
b=c%b;
}
return a;
}
int multiple(int a,int b)
{
int divisor(int a,int b);
int temp;
temp=divisor(a,b);
return (a*b/temp);
}
int main()
{
int n,i,j;
int a[100];
cout<<"输入多少个数:";
cin>>n;
cout<<endl;
cout<<"请输入这些数:";
for(i=0;i<n;i++)
{
cin>>a[i];
}
cout<<endl;
//检查输入数据是否有重复，有负数和0
for(i=0;i<n;i++)
{
if(a[i]<=0)
cout<<"输入数据错误，请重新输入!!!";
}
j=a[0];
for(int w=1;w<n;w++)
{
if(j==a[w])
cout<<"数据有重复，请重新输入!!!"<<endl;
}
cout<<endl；
long q=a[0];
cout<<"这些数的最大公约数是:";
for(j=1;j<n;++j)
{
q=divisor(q,a[j]);
}
cout<<q<<endl;
cout<<endl;
cout<<"这些数的最小公倍数是:";
long k=a[0];
for(i=1;i<n;++i)
{
k=multiple(k,a[i]);
}
cout<<k<<endl;
cout<<endl；
return 0;
}
-
调试
输入4个数:
给求最大公约数的第一个参数赋值为数组第一个值,让q等于a[0],即12，准备循环:
进入循环求最大公约数，j=1、2、3时：
得到最大公约数：
i=1、2、3时循环求最小公倍数：
求解最小公倍数k的结果：
验证数组数据是否小于0，是否重复：
6. 测试及运行结果
随意输入4个数据：12 3 6 24的值后程序运行求得的最大公约数和最小公倍数结果
-
经验归纳
这次程序编程过程中，我转换了一次思路，刚开始参照别人的代码，思路是：输入任意个数进入数组，然后根据冒泡排序从小到大排列后，如果除了最小值之外的其他数都可以被第一个数（即最小数）整除，则这个最小的数就是最大公约数。否则最小数减1，继续与其他数比较，重复上述过程，直到找到最大公约数。这个思路在编程过程中遇到了很多问题，其中最主要的问题是不知道怎样写一个循环使得最小数本身不是最大公约数的情况下总是减一，每次减一后数组中的数下标从1开始到结束来被最小值整除，判断是否每一个数都可以满足。这个问题放在后面需要继续研究。后来改变了思路：先写出求解两个数最大公约数divisor和最小公倍数multiple的算法，然后，用for循环和递归的思想从数组开始到结尾循环调用两个函数。
在这个编程过程中，最重要的就是 q=divisor(q,a[j]);这个语句。用到了递归的思想。先将q赋值为数组第一个数，j就从下标为1处开始循环，则q是divisor函数的第一个参数。后面的q就是前两个数求得的最大公约数。这一点是求解N个数的最大公约数和最小公倍数的关键。需要好好利用和理解。