一、最大公約數(shù)(Greatest Common Divisor)
幾個(gè)自然數(shù)，公有的因數(shù)，叫做這幾個(gè)數(shù)的公約數(shù)；其中最大的一個(gè)，叫做這幾個(gè)數(shù)的最大公約數(shù)。例如：18、12的公約數(shù)有1、2、3、6，其中最大的一個(gè)是6，6是18與12的最大公約數(shù)，一般記為（18、12）=6。
二、編程求最大公約數(shù)
用c++編程實(shí)現(xiàn)，輸入任意兩個(gè)自然數(shù)a和b，求他們的最大公約數(shù)。
這個(gè)題目主要是考察小朋友們對(duì)循環(huán)的使用。
三、算法求解
1.窮舉法
解析
窮舉法是大部分人最先想到的方法。讓一個(gè)數(shù)循環(huán)的去被a和b除，如果余數(shù)都為0那么就是他們的公約數(shù)，然后最大的那個(gè)就是最大公約數(shù)。
代碼
#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<<"循環(huán)次數(shù)(窮舉法)："<<count<<endl;
return z;
}
int main(){
int a,b,result;
cin>>a>>b;
result = gcd1(a,b);
cout<<a<<"和"<<b<<"的最大公約數(shù)："<<result<<endl;
return 0;
}
運(yùn)行結(jié)果：
18 12
循環(huán)次數(shù)(窮舉法)：6
18和12的最大公約數(shù)：6
分析
窮舉法雖然簡(jiǎn)單，但是有一個(gè)很大的缺點(diǎn)，就是效率低。比如咱們輸入1200和1800，那么程序是從1200開(kāi)始自減，一直減到600，才得出了結(jié)果。這個(gè)過(guò)程for共執(zhí)行了600次。含有很多小朋友會(huì)從1開(kāi)始寫(xiě)自增，那么循環(huán)的次數(shù)就更多了。
所以求最大公約數(shù)，通常不用窮舉法。
窮舉法的效率極其的低下，和后面其他幾個(gè)不在一個(gè)數(shù)量級(jí)上。
2.輾轉(zhuǎn)相除法
解析
輾轉(zhuǎn)相除法，又稱(chēng)歐幾里得算法。用于計(jì)算兩個(gè)正整數(shù)a，b的最大公約數(shù)和最小公倍數(shù)，其依賴于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<<"循環(huán)次數(shù)(迭代相除)："<<count<<endl;
return z;
}
int main(){
int a,b,result;
cin>>a>>b;
result = gcd2(a,b);
cout<<a<<"和"<<b<<"的最大公約數(shù)："<<result<<endl;
return 0;
}
運(yùn)行結(jié)果：
18 12
循環(huán)次數(shù)(迭代相除)：1
18和12的最大公約數(shù)：6
分析
可以看到迭代相除只用了一次循環(huán)就得到了結(jié)果，大大提高了效率。
此方法當(dāng)數(shù)據(jù)較小的時(shí)候性能最好，代碼可讀性極好，但是它需要用到取余運(yùn)算.
擴(kuò)展
小朋友們只學(xué)到了循環(huán)，如果學(xué)到函數(shù)以及遞歸則可以把函數(shù)寫(xiě)成如下這樣，大大簡(jiǎn)化代碼提高可讀性。
int gcd(int a, int b)
{
return 0 == b ? a : gcd(b, a % b);
}
3.更相減損法
解析
更相減損術(shù)是出自《九章算術(shù)》的一種求最大公約數(shù)的算法，它原本是為約分而設(shè)計(jì)的，但它適用于任何需要求最大公約數(shù)的場(chǎng)合。
《九章算術(shù)》是中國(guó)古代的數(shù)學(xué)專(zhuān)著，其中的“更相減損術(shù)”可以用來(lái)求兩個(gè)數(shù)的最大公約數(shù)，原文是：
可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也。以等數(shù)約之。
白話文譯文：
（如果需要對(duì)分?jǐn)?shù)進(jìn)行約分，那么）可以折半的話，就折半（也就是用2來(lái)約分）。如果不可以折半的話，那么就比較分母和分子的大小，用大數(shù)減去小數(shù)，互相減來(lái)減去，一直到減數(shù)與差相等為止，用這個(gè)相等的數(shù)字來(lái)約分。
算法的圖示如下：
代碼
#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<<"循環(huán)次數(shù)(更相減損法)："<<count<<endl;
return a;
}
int main(){
int a,b,result;
cin>>a>>b;
result = gcd3(a,b);
cout<<a<<"和"<<b<<"的最大公約數(shù)："<<result<<endl;
return 0;
}
運(yùn)行結(jié)果：
18 12
循環(huán)次數(shù)(更相減損法)：2
18和12的最大公約數(shù)：6
分析
可以看到更相減損法用了兩次循環(huán)得到結(jié)果，效率也挺高，還有它不需要取余。
這種方法在計(jì)算大數(shù)的情況下依舊可以保持較快的速度，代碼的可讀性也非常高，但是因?yàn)橐粩嗷p,在兩個(gè)數(shù)較為接近的時(shí)候需要的系統(tǒng)資源較大。
4.短除法
解析
短除法應(yīng)該是小朋友最熟悉的數(shù)學(xué)方法，和計(jì)算數(shù)學(xué)題時(shí)常采用的方法一致。
左邊部分的因子相乘，即為最大公約數(shù)。
所以，18與12的最大公約數(shù)為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++)
{
// 四個(gè)條件只要有一個(gè)不滿足，while循環(huán)結(jié)束
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<<"的最大公約數(shù)："<<result<<endl;
return 0;
}
分析
短除法的效率也還算可以，它更多是和我們常用的數(shù)學(xué)方法一致，算法上比較容易理解，但是代碼的可讀性就比較差一些。
