|
最大公約數(shù)，Greatest Common Divisor(GCD)，當(dāng)然你要是叫它Highest Common Factor(HCF)也沒(méi)人會(huì)說(shuō)不行。 相信提到最大公約數(shù)大家都不會(huì)陌生，因?yàn)閺男W(xué)開始我們就接觸到了， 短除法對(duì)吧！大概是這樣的：如果我們拿到的數(shù)是103287和417145，我們還可以通過(guò)短除法輕松的解決嗎？ 所以要給大家介紹兩種新的求法，第一種的思維過(guò)程很簡(jiǎn)單，窮舉法，思路就是枚舉每一個(gè)數(shù)，如果兩個(gè)數(shù)字都可以整除就說(shuō)明這個(gè)是公因數(shù)，最大公因數(shù)當(dāng)然要從大往小舉了！從兩個(gè)數(shù)的較小值到1。有一個(gè)符合就可以聽停止了。 我們看到就算要求的a和b很大也可以輕松求解。 很明顯，這個(gè)算法的事件復(fù)雜度是O(min(a,b))，線性的時(shí)間復(fù)雜度。接下來(lái)要介紹的輾轉(zhuǎn)相除法效率就更高了。  轉(zhuǎn)轉(zhuǎn)相除法 用較小數(shù)除較大數(shù)，再用出現(xiàn)的余數(shù)（第一余數(shù)）去除除數(shù)，再用出現(xiàn)的余數(shù)（第二余數(shù)）去除第一余數(shù)，如此反復(fù)，直到最后余數(shù)是0為止。 關(guān)于它的證明......感興趣的人看一下吧 設(shè)兩數(shù)為a、b(a>b)，用gcd(a,b)表示a，b的最大公因數(shù)，r=a (mod b) 為a除以b的余數(shù)，k為a除以b的商，即a/b = k······r。輾轉(zhuǎn)相除法即是要證明 gcd(a,b)=gcd(b,r)。 第一步：令 第二步：根據(jù)前提可知 第三步：根據(jù)第二步結(jié)果可知， 第四步：可以斷定 不知道你有沒(méi)有看懂。不過(guò)不重要我們來(lái)看代碼吧。 
. |
|
|
來(lái)自： 長(zhǎng)沙7喜 > 《信息課》
，則設(shè)
也是
的因數(shù)
與
