一步一步寫(xiě)算法

1、步一步寫(xiě)算法（之 最大公約數(shù)、最小公倍數(shù)）一步一步寫(xiě)算法（之 最大公約數(shù)、最小公倍數(shù)）分類： 數(shù)據(jù)結(jié)構(gòu)和算法 2011-11-19 21:04 265 人閱讀 評(píng) 論 （5） 收藏 舉報(bào) 【 聲明：版權(quán)所有，歡迎轉(zhuǎn)載，請(qǐng)勿用于商業(yè)用途。 聯(lián) 系信箱： feixiaoxing 】 求解最小公倍數(shù)和最 大公約數(shù)是我們開(kāi)始編程的時(shí)候經(jīng)常需要練習(xí)的題目。從題 面上看，好像我們需要求解的是兩個(gè)題目，但其實(shí)就是一個(gè) 題目。那就是求最大公約數(shù)？為什么呢？我們可以假想這兩個(gè)數(shù)m和n ,假設(shè)m和n的最大公約數(shù)是 a。那么我們可以 這樣寫(xiě)：m = b *a ；n = c * a;所以 m 和 n 的最小公倍數(shù)就應(yīng)

2、該是 a*b*c 啊，那不就是 m * n / a，其中m和n是已知的，而a就是那個(gè)需要求解的 最大公約數(shù)。所以就有了下面的代碼， view plaincopy to clipboardprint?int GetMinCommonMultiple(int m, int n) assert(m && n);return m * n / GetMaxCommonDivide(m, n); int GetMinCommonMultiple(int m, int n)assert(m && n); return m * n /GetMaxCommonDivide(m,

3、n); 下面就可以開(kāi)始最大公約數(shù)的求解。 其實(shí)， 關(guān)于最大公 約數(shù)的求解，大家看到的更多是各種捷徑，比如說(shuō)歐幾里得 法。歐幾里得法構(gòu)思十分巧妙，它利用了m 、n 和 n、m%n之間的最大公約數(shù)是相等的這一重要條件，充分利用替換的 方法，在 m%n 等于 0 的那一剎那，獲得我們的最大公約數(shù)。 然而，我們平時(shí)自己所能想到的方法卻不多，下面的方法就 是具有典型意義的一種：a) 首先對(duì)數(shù)據(jù) m 和 n 判斷大小，小的賦值給 smaller ， 大的賦值給 largerb) index 索引從 2 開(kāi)始到 smaller 遍歷，發(fā)現(xiàn)有沒(méi)有數(shù) 據(jù)可以同時(shí)被兩者整除，有則更新數(shù)據(jù)c )循環(huán)結(jié)束后，獲取最大

4、的公約數(shù) view plaincopy to clipboardprint?int GetMaxCommonDivide(int n, int m) int index;int smaller;int larger;int value;assert(n && m);if(n > m)larger = n; smaller = m;elselarger = m; smaller = n;value = 1;for(index = 2; index <= smaller; index+) if(0 = (smaller % index) && 0 = (

5、larger % index)value = index; return value; int GetMaxCommonDivide(int n, int m)int index;int smaller;int larger;int value;assert(n && m); if(n > m)larger = n; smaller = m;elselarger = m; smaller = n; value = 1;for(index = 2; index <= smaller; index+)if(0 = (smaller % index) && 0 = (larger % index)value = index; return value; 上面的代碼看似沒(méi)有問(wèn)題，但是還是留下了一個(gè)遺憾， 如果 m 和 n 的數(shù)據(jù)都大于 32 位，那怎么辦？也許有的朋友 會(huì)說(shuō)，現(xiàn)在有 64 位的 cpu 。但是如果我們此刻沒(méi)有 64 位的 cpu ，那該怎么辦呢？總結(jié)：（1）看似最大公約數(shù)、最小公倍數(shù)是個(gè)小問(wèn)題，但是 要寫(xiě)好不容易，算法、參數(shù)判斷、邏輯都要注意，（ 2）如果 m 和 n 的數(shù)據(jù)都比較大，有沒(méi)有可能利用多 核降低計(jì)算的復(fù)雜度，（ 3）如果 m 和 n 中有數(shù)據(jù)大于 32 位，那該怎么辦？ （4）小問(wèn)題看