生活随笔
收集整理的這篇文章主要介紹了
面试题之丑数的C++实现求解（孤陋寡闻了，才知道丑数这么high的东东）
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
問題描述：
?? ? 我們把只包含因子2、3和5的數稱作丑數（Ugly Number）。例如6、8都是丑數，但14不是，因為它包含因子7。習慣上我們把1當做是第一個丑數。求按從小到大的順序的第1500個丑數。（昨天突然發現個不錯的博客：http://blog.csdn.net/v_JULY_v，突然知道丑數這個題，于是搜之）
?? ? 當然，最簡單的肯定是遍歷啊，想當年初學的時候，什么水仙花數，完數，質數，都遍歷搞定。遍歷存在的問題就是效率太低，如同暴力破密碼似的，以前用bt4破一個wep的有時候都要10多分鐘，破個WAP加密的半個小時，這不蛋疼嗎，破了就為蹭個網。像這個吧，到第1500個丑數的時候，用時就要42s多(win7+vc6)，效率上肯定是有折扣的了，下面是代碼：
#include <iostream>#include <climits>using namespace std;int IsUgly(int num){ while (num %2 == 0){num /= 2;} while (num %3 == 0){num /= 3;} while (num %5 == 0){num /= 5;} if (num == 1) return 1; else return 0;}void GetUglyNumber(int index){ int i , time =0 ; if (index < 1){ cout << "error input " << endl; exit(EXIT_FAILURE);} for (i=1 ; i< INT_MAX && time < index ; i++){ if ( IsUgly(i) ){time ++ ; }} cout << i-1 << endl;}int main(){ int Number; cout << "Input a number : " ; cin >> Number ;GetUglyNumber(Number); return 0;}
?? ? ? ?遍歷法很大的問題在于對每個數都進行判斷，進行取余和除的運算了，如果換種思路的話，只對丑數進行計算呢？根據
http://www.cnblogs.com/mingzi/archive/2009/08/04/1538491.html
的思路，雖然從代碼上來看
http://www.cppblog.com/zenliang/articles/131094.html
的更簡潔易懂，不過第一個鏈接的變量命名會好很多，而且思路交代更清晰。
?? ? ? ?根據丑數的定義，丑數應該是另一個丑數乘以2、3或者5的結果（1除外）。因此我們可以創建一個數組，里面的數字是排好序的丑數。里面的每一個丑數是前面的丑數乘以2、3或者5得到的。那關鍵就是確保數組里的丑數是有序的了。我們假設數組中已經有若干個丑數，排好序后存在數組中。我們把現有的最大丑數記做M。
現在我們來生成下一個丑數，該丑數肯定是前面某一個丑數乘以2、3或者5的結果。
我們首先考慮把已有的每個丑數乘以2。在乘以2的時候，能得到若干個結果小于或等于M的。
由于我們是按照順序生成的，小于或者等于M肯定已經在數組中了，我們不需再次考慮；
我們還會得到若干個大于M的結果，但我們只需要第一個大于M的結果，因為我們希望丑數是按從小到大順序生成的，其他更大的結果我們以后再說。
我們把得到的第一個乘以2后大于M的結果，記為M2。
同樣我們把已有的每一個丑數乘以3和5，能得到第一個大于M的結果M3和M5。那么下一個丑數應該是M2、M3和M5三個數的最小者。(來自http://www.cnblogs.com/mingzi/archive/2009/08/04/1538491.html)，則可以得到以下代碼：
#include <iostream> using namespace std; int Min(int a, int b, int c) { int temp = (a < b ? a : b); return (temp < c ? temp : c); } int FindUgly(int n) { int* ugly = new int[n]; ugly[0] = 1; int index2 = 0; int index3 = 0; int index5 = 0; int index = 1; while (index < n) { int val = Min(ugly[index2]*2, ugly[index3]*3, ugly[index5]*5); if (val == ugly[index2]*2) ++index2; if (val == ugly[index3]*3) ++index3; if (val == ugly[index5]*5) ++index5; ugly[index++] = val; } int result = ugly[n-1]; delete[] ugly; return result; } int main() { int num; cout << "input the number : " ; cin >> num; cout << FindUgly(num) << endl; return 0; }
?? ? 代碼來自：
http://www.cppblog.com/zenliang/articles/131094.html
?？吹剿膎ew，才想起，以前寫排序的時候，由于數組大小可變，直接用了vector，讓它直接去vector的size()就知道大小了，而沒有想到還有更初級的new，對于不定大小，new就好了啊，雖說new出來的是是在堆上，直接定義的是在棧上，不過用起來也是毫無影響的，果然自己還是太菜了點。
?? ? ?另外還可以采用的方法很多，參考
http://www.iteye.com/topic/832545
。本帖子列出了5種方法：
?????
?? ? ?代碼直接參考，實際上，搜到的C++的代碼就是method1和method4，其實吧，method2和method3的精髓在于i?<?Integer.MAX_VALUE / 5 ，也是利用了所有丑數肯定是由丑數產生這一思想，雖然不同之處在于遍歷和求下標，不過總體是產生足夠大的丑數集合，再直接取需要的位置。C++實現如下：
???
#include <set>#include <iostream>#include <climits>using namespace std;const int MAX = INT_MAX/5; void GetUgly(int Index){ int i; set<int,less<int> > s; set<int, less<int> >::iterator It;s.insert(1); for (i=1 ; i<MAX ; i++){ if (s.find(i) != s.end() ){s.insert(2*i) ;s.insert(3*i) ;s.insert(5*i) ;}} for (It = s.begin() ,i=1 ; It != s.end() && i < Index; It++)i++; cout << *It << endl;}int main(int argc,char *argv[]){ int Number; cout << "Input a number : " ; cin >> Number ;GetUgly(Number); return 0;}
?? ?說到這個，本打算用vector的，還用到了algorithm頭文件的find和sort。不過問題在于vector怎么刪除重復元素呢？哪怕加入是否在vector中的判斷，仍然難以阻止，效率不高。不過一不小心找到了STL的
set
，高級貨啊，
set自動刪除重復元素
這一特性，還是很給力的。和Java的set一樣，不過這個算法的問題在于，直接將所有的丑數都找出來了，再取下標，在vc6和gcc測試下，速度著實很慢，莫非是C++STL的set不如Java的set高效么？這個方法讓我想到對于1000個數，找出其中最小的5個，但是將這1000個數都進行排序了再直接取前5個，雖然可行，但未免開銷太大，不經濟。運行的時候，等的時間太長，以至于直接關掉，將MAX換為2w，隨便測試了下對于100等數是否正確來判斷程序是否大致準確。
?? ?下面來改寫Java的method5為C++版本，代碼如下：
#include <iostream>using namespace std; int nums5(int val){ int n=0 ; while (val >= 5){n++ ;val /= 5;} return n;}int nums35(int val){ int n=0 ; while (val >= 3){n += 1+nums5(val);val /= 3;} return n;}int nums235(int val){ int n=0 ; while (val >= 2){n += 1+nums35(val);val /= 2 ;} return n;}int numOfIndex(int n) { if(n == 1) return 1; n--; int val1 = 1; int nums1 = 0; int val2 = 2; int nums2 = nums235(val2); while( nums2 < n ) { val1 = val2; nums1 = nums2; val2 = val1*2; nums2 = nums235(val2); } if( nums1 == n ) return val1; if( nums2 == n ) return val2; while(true) { long mid = (val1 + val2)/2; int nums = nums235(mid); if(val2 == mid+1 && nums == n-1 && nums2==n) return val2; if(mid == val1+1 && nums1 == n-1 && nums==n) return mid; if(nums >= n) { val2 = mid; nums2 = nums; } else { val1 = mid; nums1 = nums; } } }int check(int val) { long v = val; while( v%2==0 ) v/=2; while( v%3==0 ) v/=3; while( v%5==0 ) v/=5; if( v != 1 ) cout << " v is not an ugly number! " << endl; return val; } void calc(int n) { long val = numOfIndex(n); cout << n << " : " << val << endl;; check(val); } int main(int argc ,char *argv[]){ int Number; cout << "Please input a number : " ; cin >> Number ;calc(Number); return 0;}
?? ? ? ? 想不到這算法很是高級貨啊，直接因數分解，其實也是充分利用丑數是由丑數產生這一原理，用nums235統計出val內丑數個數。雖然也是都大量計算，不過比第一種的好很多，加上引入二分查找，效率還是不錯的。經過測試，與method4在1500的時候都能在5ms內完成，各有所長。不過有個不足的地方，
http://www.iteye.com/topic/832545
雖然說這方法是最優解（如果在calc中去掉check調用，1500-1545都是1ms或2ms完成，震驚啊），不過在輸入1546開始，會很慢，更不用說在1692這樣會溢出的點，會很慢（沒等，不知道具體時間）不過在1545以內，的確是最優，作者
taolei0628
果然牛。
?? ? ? ? ?總結起來，就是最簡陋的遍歷，從小到大的只算丑數，統計全部丑數，計算丑數個數，方法不同，算起來，搞程序還是很有意思的嘛，可惜沒早點發現，就這樣了吧。
?? ? ? ? ?菜鳥goes on ~~
總結
以上是生活随笔為你收集整理的面试题之丑数的C++实现求解（孤陋寡闻了，才知道丑数这么high的东东）的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
