一、最大公約數(shù)(Greatest Common Divisor)
幾個自然數(shù)皱卓，公有的因數(shù)总放，叫做這幾個數(shù)的公約數(shù)；其中最大的一個好爬，叫做這幾個數(shù)的最大公約數(shù)局雄。例如：12、16的公約數(shù)有1存炮、2炬搭、4，其中最大的一個是4穆桂，4是12與16的最大公約數(shù)宫盔，一般記為（12、16）=4享完。12灼芭、15、18的最大公約數(shù)是3般又，記為（12彼绷、15、18）=3茴迁。
二寄悯、編程求兩個數(shù)的最大公約數(shù)
求最大公約數(shù)有多種方法，沒有專門學過方法的人堕义，首先可能會聯(lián)想到窮舉法猜旬。
（一）窮舉法
#include <stdio.h>
// 窮舉法
int gcd(int num1, int num2)
{
// 求最小的那個數(shù)
int divisor = num1 < num2 ? num1 : num2;
for(; divisor >= 1; divisor--)
{
if(0 == num1 % divisor && 0 == num2 % divisor)
{
// 找到最大公約數(shù)脚曾，跳出循環(huán)
break;
}
}
return divisor;
}
int main()
{
printf("%d", gcd(12, 16));
return 0;
}
運行結(jié)果：
4
分析：
窮舉法雖然簡單双肤，但是有一個很大的缺點，就是效率低逾柿。比如咱們輸入10000和15000怕膛，那么程序是從10000開始自減熟嫩，一直減到5000，才得出了結(jié)果嘉竟。這個過程for共執(zhí)行了10000-5000+1 = 5001次邦危。
所以求最大公約數(shù)，通常不用窮舉法舍扰。
那么有沒有其他求最大公約數(shù)的方法呢倦蚪？
有的。
常見的有輾轉(zhuǎn)相除法边苹、相減法陵且、短除法等。
（二）輾轉(zhuǎn)相除法
思路:
有兩整數(shù)a和b
① a%b得余數(shù)c
② 若c=0，則b即為兩數(shù)的最大公約數(shù)
③ 若c≠0慕购，則a=b聊疲，b=c，再回去執(zhí)行①
例子: a = 10000 b = 15000沪悲，則運算過程為
① c = a % b = 10000 % 15000 = 10000, a = b = 15000, b = c = 10000
② c = a % b = 15000 % 10000 = 5000, a = b = 10000, b = c = 5000
③ c = a % b = 10000 % 5000 = 0, 則b = 5000即為最大公約數(shù)
程序：
#include <stdio.h>
// 遞歸實現(xiàn)輾轉(zhuǎn)相除法
int gcd(int a, int b)
{
if(0 == b)
{
return a;
}
return gcd(b, a% b);
}
int main()
{
printf("%d", gcd(10000, 15000));
return 0;
}
運行結(jié)果：
5000
分析：
與窮舉法相比获洲，求10000和15000的最大公約數(shù)，輾轉(zhuǎn)相除法只循環(huán)了三次殿如，就得到了結(jié)果贡珊。效率提高了很多。
可以將輾轉(zhuǎn)相除法的代碼簡化成一行
int gcd(int a, int b)
{
return 0 == b ? a : gcd(b, a % b);
}
（三）相減法
又叫更相減損法涉馁、等值算法门岔，起源于《九章算術(shù)》。
思路：
有兩整數(shù)a和b
① 若a>b烤送，則a = a - b
若a<b寒随，則b = b - a
② 若a=b，則a（或b）即為兩數(shù)的最大公約數(shù)
若a≠b帮坚，則再回去執(zhí)行①
例子：求27和15的最大公約數(shù)過程為：
① a = a - b = 27－15＝12
② b = b - a = 15－12＝3
③ a = a - b = 12－3＝9
④ a = a - b = 9－3＝6
⑤ a = a - b = 6－3＝3妻往，此時a = b = 3，則3即為所求叶沛。
程序：
#include <stdio.h>
// 相減法
int gcd(int num1, int num2)
{
while(num1 != num2)
{
if(num1 > num2)
{
num1 -= num2;
}
else
{
num2 -= num1;
}
}
return num1;
}
int main()
{
printf("%d", gcd(27, 15));
return 0;
}
運行結(jié)果：
3
（四）短除法
思路：
左邊部分的因子相乘蒲讯，即為最大公約數(shù)。
所以灰署，12與16的最大公約數(shù)為2 * 2 = 4
程序：
#include <stdio.h>
// 短除法
int gcd(int m, int n)
{
int min = m < n ? m : n;
int s = 1;
int i;
for(i = 2; i <= min ; i++)
{
// 四個條件只要有一個不滿足，while循環(huán)結(jié)束
while(m > 0 && n > 0 && 0 == m % i && 0 == n % i)
{
m /= i;
n /= i;
s *= i;
}
}
return s;
}
int main()
{
printf("%d", gcd(12, 16));
return 0;
}
運行結(jié)果：
4
三局嘁、作業(yè)
輾轉(zhuǎn)相除法特別重要溉箕，必須掌握。其他三種方法了解思路即可悦昵。
想了解少兒編程肴茄、少兒英語請加微信307591841或QQ307591841
公眾號.jpg
