经典算法详解（9）寻找丑数

 1 #include<iostream> 2  3 using namespace std; 4  5 //判断一个数是否是丑数，uglynum=2*2……*2*3*3*……*3*5*5……*5组成 6 int isUglyNumber(int n) { 7     while (n%2==0) 8     { 9         n /= 2;10     }11     while (n%3==0)12     {13         n /= 3;14     }15     while (n%5==0)16     {17         n /= 5;18     }19     return n == 1;20 }21 //方法1：逐个判断是否是丑叔，思路简单，但是计算冗余，因为越到后面很多都不是丑数也在计算。22 int get_Ugly_fir(int number) {23     int i = 1;24     int count = 0;25     while (i<=number)26     {27         if (isUglyNumber(i)) {28             cout << i << "	";29             count++;30             if (count % 10 == 0)31                 cout << endl;32         }33         i++;34     }35     return count;36 }37 38 //方法二：算法效率高。39 //思路：(1)后面的丑数肯定是已存在的丑数乘以2、3或者5，找到比现有丑数大的且是最小的丑数作为下一个丑数（如何找是关键）。40 //2分别从现有丑数中从前往后乘以丑数，找到第一个大于当前所有丑数的值以及位置，3、5同样如此，再把他们相乘之后的结果做对比，取最小的。41 //下次将从上一次的位置开始往下找，这样将不会出现冗余，详细见如下函数。42 43 int Next_Ugly(int ugly_arr[], int *loc2, int *loc3, int *loc5, int *index) {44     while (ugly_arr[*loc2] * 2 <= ugly_arr[*index]) {    //千万注意这里是小于等于，不要写成小于了45         (*loc2)++;46     }47     while (ugly_arr[*loc3] * 3 <= ugly_arr[*index]) {48         (*loc3)++;49     }50     while (ugly_arr[*loc5] * 5 <= ugly_arr[*index]) {51         (*loc5)++;52     }53     if (ugly_arr[*loc2] *2< ugly_arr[*loc3]*3) {54         return (ugly_arr[*loc2] * 2 < ugly_arr[*loc5] * 5) ? ugly_arr[*loc2] * 2 : ugly_arr[*loc5] * 5;55     }56     else {57         return (ugly_arr[*loc3] * 3) < ugly_arr[*loc5] * 5 ? ugly_arr[*loc3] * 3 : ugly_arr[*loc5] * 5;58     }59 }60 61 int get_Ugly_sec(int num) {62     int ugly_arr[1000];63     int index = 0, value = 1;64     int loc2=0, loc3=0, loc5=0;65     while (value<=num) {66         ugly_arr[index] = value;67         cout << ugly_arr[index] << "	";68         if ((index + 1) % 10 == 0)69             cout << endl;70         71         value = Next_Ugly(ugly_arr, &loc2, &loc3, &loc5, &index);72         index++;73     }74     return index;75 }76 77 int main(int argc, char *argv[]) {78     get_Ugly_fir(1500);79     cout << endl;80     get_Ugly_sec(1500);81     getchar();82     return 0;83 }