一、最大公约数(Greatest Common Divisor)
几个自然数，公有的因数，叫做这几个数的公约数；其中最大的一个，叫做这几个数的最大公约数。例如：18、12的公约数有1、2、3、6，其中最大的一个是6，6是18与12的最大公约数，一般记为（18、12）=6。
二、编程求最大公约数
用c++编程实现，输入任意两个自然数a和b，求他们的最大公约数。
这个题目主要是考察小朋友们对循环的使用。
三、算法求解
1.穷举法
解析
穷举法是大部分人最先想到的方法。让一个数循环的去被a和b除，如果余数都为0那么就是他们的公约数，然后最大的那个就是最大公约数。
代码
#include <iostream>
using namespace std;
//穷举法
int gcd1(int a, int b)
{
int x=(a<b?a:b);
int z = 0 ,count=0;
for(;x>0;x--)
{
if( a%x == 0 && b%x == 0 ){
z=x;
break;
}
count++;
}
cout<<"循环次数(穷举法)："<<count<<endl;
return z;
}
int main(){
int a,b,result;
cin>>a>>b;
result = gcd1(a,b);
cout<<a<<"和"<<b<<"的最大公约数："<<result<<endl;
return 0;
}
运行结果：
18 12
循环次数(穷举法)：6
18和12的最大公约数：6
分析
穷举法虽然简单，但是有一个很大的缺点，就是效率低。比如咱们输入1200和1800，那么程序是从1200开始自减，一直减到600，才得出了结果。这个过程for共执行了600次。含有很多小朋友会从1开始写自增，那么循环的次数就更多了。
所以求最大公约数，通常不用穷举法。
穷举法的效率极其的低下，和后面其他几个不在一个数量级上。
2.辗转相除法
解析
辗转相除法，又称欧几里得算法。用于计算两个正整数a，b的最大公约数和最小公倍数，其依赖于gcd(a,b) = a (b=0)和gcd(b,a mod b) (b!=0)。算法的具体描述如下图：
辗转相除法图示
代码
#include <iostream>
using namespace std;
//迭代相除法
int gcd2(int a, int b)
{
int z = b;
int count = 0;
while (a % b != 0) {
z = a % b;
a = b;
b = z;
count++;
}
cout<<"循环次数(迭代相除)："<<count<<endl;
return z;
}
int main(){
int a,b,result;
cin>>a>>b;
result = gcd2(a,b);
cout<<a<<"和"<<b<<"的最大公约数："<<result<<endl;
return 0;
}
运行结果：
18 12
循环次数(迭代相除)：1
18和12的最大公约数：6
分析
可以看到迭代相除只用了一次循环就得到了结果，大大提高了效率。
此方法当数据较小的时候性能最好，代码可读性极好，但是它需要用到取余运算.
扩展
小朋友们只学到了循环，如果学到函数以及递归则可以把函数写成如下这样，大大简化代码提高可读性。
int gcd(int a, int b)
{
return 0 == b ? a : gcd(b, a % b);
}
3.更相减损法
解析
更相减损术是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。
《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，原文是：
可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。
白话文译文：
（如果需要对分数进行约分，那么）可以折半的话，就折半（也就是用2来约分）。如果不可以折半的话，那么就比较分母和分子的大小，用大数减去小数，互相减来减去，一直到减数与差相等为止，用这个相等的数字来约分。
算法的图示如下：
更相减损法
代码
#include <iostream>
using namespace std;
//更相减损法
int gcd3(int a,int b)
{
int count = 0;
while(a != b)
{
if(a>b)
{
a = a - b;
}
else
{
b = b - a;
}
count++;
}
cout<<"循环次数(更相减损法)："<<count<<endl;
return a;
}
int main(){
int a,b,result;
cin>>a>>b;
result = gcd3(a,b);
cout<<a<<"和"<<b<<"的最大公约数："<<result<<endl;
return 0;
}
运行结果：
18 12
循环次数(更相减损法)：2
18和12的最大公约数：6
分析
可以看到更相减损法用了两次循环得到结果，效率也挺高，还有它不需要取余。
这种方法在计算大数的情况下依旧可以保持较快的速度，代码的可读性也非常高，但是因为要不断互减,在两个数较为接近的时候需要的系统资源较大。
4.短除法
解析
短除法应该是小朋友最熟悉的数学方法，和计算数学题时常采用的方法一致。
短除法
左边部分的因子相乘，即为最大公约数。
所以，18与12的最大公约数为2 * 3 = 6
// 短除法
int gcd4(int a, int b)
{
int min = a < b ? a : b;
int s = 1;
int i;
for(i = 2; i <= min ; i++)
{
// 四个条件只要有一个不满足，while循环结束
while(a > 0 && b > 0 && 0 == a % i && 0 == b % i)
{
a /= i;
b /= i;
s *= i;
}
}
return s;
}
int main(){
int a,b,result;
cin>>a>>b;
result = gcd4(a,b);
cout<<a<<"和"<<b<<"的最大公约数："<<result<<endl;
return 0;
}
分析
短除法的效率也还算可以，它更多是和我们常用的数学方法一致，算法上比较容易理解，但是代码的可读性就比较差一些。
网友评论