題目
求兩個(gè)數(shù)的最大公約數(shù)莹弊。
怎么看都是一個(gè)數(shù)學(xué)的問(wèn)題风宁，所以還是需要數(shù)學(xué)的定理公理球恤，來(lái)求。
輾轉(zhuǎn)相除法
假設(shè)兩個(gè)整數(shù)x,y（x>y）
那么：
兩個(gè)數(shù)相除商：k=x/y
兩個(gè)數(shù)相除余數(shù)：d=x%y
那么使用y表x：x=ky+b
所以如果一個(gè)數(shù)能夠正除y剿配、x搅幅，那么這個(gè)數(shù)一定能夠正除b。
假設(shè)兩個(gè)數(shù)的最大公約數(shù)為c,那么x=mc=ky+b,y=nc呼胚。
所以b=x-ky=mc-knc=c(m-kn)所以茄唐，c也是b的一個(gè)因數(shù)。
參考文章
所以得出
int gcd(int x,inty)
{
return(!y)?x:gcd(y,x/y);
}
也就是
f(42,30)=f(30,12)=f(12,6)=f(6,0)=6
方法二
改進(jìn)方法一
對(duì)于取模運(yùn)算開(kāi)銷(xiāo)大蝇更，所以將上面的取模運(yùn)算改為減法
int gcd(int x, int y)
{
if(x<y)
{
return gcd(y,x)
}
if(y == 0)
{
return x;
}else{
return gcd(x-y,y);
}
}
當(dāng)時(shí)對(duì)于(100000,1)這種計(jì)算緩慢
方法三
利用2來(lái)簡(jiǎn)化計(jì)算沪编。如果兩個(gè)數(shù)都是偶數(shù)，那么同除2年扩。
如果其中一個(gè)數(shù)是偶數(shù)蚁廓，那么該數(shù)除2，另一個(gè)不變厨幻。
如果都不是偶數(shù)相嵌，那么直接相減，然后遞歸况脆。
看不太懂饭宾，不過(guò)方法卻是對(duì)。
