????求最大公約數(shù)是一常見的數(shù)學(xué)問題，數(shù)學(xué)思維中的常用求法有指數(shù)分解、短除法、輾轉(zhuǎn)相除和更相減損法，其中前兩個算法通過代碼實現(xiàn)的效率是非常低的，我能想到的方法只有首先就需要一個求質(zhì)數(shù)算法的表達(dá)式來表示無窮大的質(zhì)數(shù)集合，然后再試模判斷，成功后進(jìn)行分解。在這里我們主要研究后兩個算法的設(shè)計與C語言的實現(xiàn)。

????1、輾轉(zhuǎn)相除法

????????其方法顧名思義，就是大數(shù)模小數(shù)取余，再用余數(shù)與小數(shù)進(jìn)行比較，繼續(xù)重復(fù)大數(shù)模小數(shù)取余的操作，直到大數(shù)模小數(shù)為0時，小數(shù)就是這兩個數(shù)的最大公約數(shù)，又稱歐幾里得算法。因為此過程中我們要進(jìn)行多次的判斷大數(shù)和小數(shù)，若小數(shù)的值比大數(shù)的要大，則需要交換著兩個數(shù)，所以在此我們可以先封裝一個交換兩個×××的方法，把判斷放在實現(xiàn)求取最大公約數(shù)的函數(shù)中，并不需要把判斷野封裝進(jìn)去，這樣可以盡量減小函數(shù)調(diào)用的次數(shù)，提高效率。

????????封裝交換×××的代碼如下：

void?swap(int?*a,?int?*b) { int?tmp?=?*a; *a?=?*b; *b?=?tmp; }

????????接下來需要考慮的就是實現(xiàn)輾轉(zhuǎn)相除算法的代碼了，通過解釋，我們很容易就能寫出來，代碼如下：

int?DetGreatestCommonDivisor(int?max,int?min)//輾轉(zhuǎn)相除法 { while?(max) { if?(min?>?max) swap(&min,?&max); max?=?max%min; } return?min; }

????2、更相減損法，又叫更相減損術(shù)，出自九章算法，其算法核心是首先兩個數(shù)若存在偶數(shù)，則把偶數(shù)除2然后判斷大小，用大數(shù)減小數(shù)，然后再重復(fù)以上操作，直到大數(shù)減小數(shù)為0時，這個小數(shù)或者大數(shù)就是它們的最大公約數(shù)。則“可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也。以等數(shù)約之。

????????????其代碼實現(xiàn)如下：

int?GetGreatestCommonDivisor(int?max,?int?min)//更相減損法 { while?(max) { while?(min?%?2?==?0) {min?/=?2; } while?(max?%?2?==?0) {max?/=?2; } if?(min?>?max) swap(&min,?&max); max?=?max?-?min; } return?min; }

????如有不足還請指正

轉(zhuǎn)載于:https://blog.51cto.com/10743407/1744578

總結(jié)

以上是生活随笔為你收集整理的求最大公约数的设计与C语言实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。