一锅棕、最大公約數(shù)(Greatest Common Divisor)
幾個自然數(shù)，公有的因數(shù)淌山，叫做這幾個數(shù)的公約數(shù)裸燎；其中最大的一個，叫做這幾個數(shù)的最大公約數(shù)泼疑。例如：18德绿、12的公約數(shù)有1、2退渗、3移稳、6，其中最大的一個是6会油，6是18與12的最大公約數(shù)个粱，一般記為（18、12）=6钞啸。
二几蜻、編程求最大公約數(shù)
用c++編程實現(xiàn)喇潘，輸入任意兩個自然數(shù)a和b，求他們的最大公約數(shù)梭稚。
這個題目主要是考察小朋友們對循環(huán)的使用颖低。
三、算法求解
1.窮舉法
解析
窮舉法是大部分人最先想到的方法弧烤。讓一個數(shù)循環(huán)的去被a和b除忱屑，如果余數(shù)都為0那么就是他們的公約數(shù)，然后最大的那個就是最大公約數(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;
}
運行結(jié)果：
18 12
循環(huán)次數(shù)(窮舉法)：6
18和12的最大公約數(shù)：6
分析
窮舉法雖然簡單莺戒，但是有一個很大的缺點，就是效率低急波。比如咱們輸入1200和1800从铲，那么程序是從1200開始自減，一直減到600澄暮，才得出了結(jié)果名段。這個過程for共執(zhí)行了600次。含有很多小朋友會從1開始寫自增泣懊，那么循環(huán)的次數(shù)就更多了伸辟。
所以求最大公約數(shù)，通常不用窮舉法馍刮。
窮舉法的效率極其的低下信夫，和后面其他幾個不在一個數(shù)量級上。
2.輾轉(zhuǎn)相除法
解析
輾轉(zhuǎn)相除法卡啰，又稱歐幾里得算法静稻。用于計算兩個正整數(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;
}
運行結(jié)果：
18 12
循環(huán)次數(shù)(迭代相除)：1
18和12的最大公約數(shù)：6
分析
可以看到迭代相除只用了一次循環(huán)就得到了結(jié)果，大大提高了效率梅誓。
此方法當數(shù)據(jù)較小的時候性能最好恰梢，代碼可讀性極好，但是它需要用到取余運算.
擴展
小朋友們只學(xué)到了循環(huán)梗掰，如果學(xué)到函數(shù)以及遞歸則可以把函數(shù)寫成如下這樣嵌言，大大簡化代碼提高可讀性。
int gcd(int a, int b)
{
return 0 == b ? a : gcd(b, a % b);
}
3.更相減損法
解析
更相減損術(shù)是出自《九章算術(shù)》的一種求最大公約數(shù)的算法及穗，它原本是為約分而設(shè)計的摧茴，但它適用于任何需要求最大公約數(shù)的場合。
《九章算術(shù)》是中國古代的數(shù)學(xué)專著埂陆，其中的“更相減損術(shù)”可以用來求兩個數(shù)的最大公約數(shù)苛白，原文是：
可半者半之娃豹，不可半者，副置分母购裙、子之數(shù)懂版，以少減多，更相減損躏率，求其等也躯畴。以等數(shù)約之蜡励。
白話文譯文：
（如果需要對分數(shù)進行約分痘拆，那么）可以折半的話得封，就折半（也就是用2來約分）最冰。如果不可以折半的話，那么就比較分母和分子的大小饱岸，用大數(shù)減去小數(shù)屡久，互相減來減去纤怒，一直到減數(shù)與差相等為止黄娘，用這個相等的數(shù)字來約分峭状。
算法的圖示如下：
代碼
#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;
}
運行結(jié)果：
18 12
循環(huán)次數(shù)(更相減損法)：2
18和12的最大公約數(shù)：6
分析
可以看到更相減損法用了兩次循環(huán)得到結(jié)果克滴，效率也挺高逼争，還有它不需要取余。
這種方法在計算大數(shù)的情況下依舊可以保持較快的速度劝赔，代碼的可讀性也非常高誓焦，但是因為要不斷互減,在兩個數(shù)較為接近的時候需要的系統(tǒng)資源較大。
4.短除法
解析
短除法應(yīng)該是小朋友最熟悉的數(shù)學(xué)方法着帽，和計算數(shù)學(xué)題時常采用的方法一致杂伟。
左邊部分的因子相乘，即為最大公約數(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++)
{
// 四個條件只要有一個不滿足，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é)方法一致越平，算法上比較容易理解，但是代碼的可讀性就比較差一些灵迫。
