丑數，什麼是丑數

丑數，什麼是丑數

題目:我們把只包含因子2、3和5的數稱作丑數（Ugly Number）。例如6、8都是丑數，但14不是，因為它包含因子7。習慣上我們把1當做是第一個丑數。求按從小到大的順序的第1500個丑數。

思路1:遍歷

思路2: 根據丑數的定義，丑數應該是另一個丑數乘以2、3或者5的結果（1除外）。因此我們可以創建一個數組，裡面的數字是排好序的丑數。裡面的每一個丑數是前面的丑數乘以2、3或者5得到的。那關鍵就是確保數組裡的丑數是有序的了。我們假設數組中已經有若干個丑數，排好序後存在數組中。我們把現有的最大丑數記做M。現在我們來生成下一個丑數，該丑數肯定是前面某一個丑數乘以2、3或者5的結果。我們首先考慮把已有的每個丑數乘以2。在乘以2的時候，能得到若干個結果小於或等於M的。由於我們是按照順序生成的，小於或者等於M肯定已經在數組中了，我們不需再次考慮；我們還會得到若干個大於M的結果，但我們只需要第一個大於M的結果，因為我們希望丑數是按從小到大順序生成的，其他更大的結果我們以後再說。我們把得到的第一個乘以2後大於M的結果，記為M₂。同樣我們把已有的每一個丑數乘以3和5，能得到第一個大於M的結果M₃和M₅。那麼下一個丑數應該是M₂、M₃和M₅三個數的最小者。

 1 #include <stdio.h>
 2 #include "stdafx.h"
 3 
 4 int IsUgly(int number)
 5 {
 6     while(number % 2 == 0)
 7         number /= 2;
 8     while(number % 3 ==0)
 9         number /= 3;
10     while(number % 5 ==0)
11         number /= 5;
12 
13 
14     return (number == 1) ? true : false;
15 }
16 
17 int GetUglyNumber_Solution1(int index)
18 {
19     if(index <= 0)
20         return 0;
21 
22     int number = 0;
23     int uglyFound = 0;
24     while(uglyFound < index)
25     {
26         ++ number;
27 
28         if(IsUgly(number))
29         {
30             ++ uglyFound;
31         }
32     }
33 
34     return number;
35 }
36 
37 
38 int Min(int number1, int number2, int number3);
39  
40  int GetUglyNumber_Solution2(int index)
41 {
42     if(index <= 0)
43         return 0;
44  
45     int *pUglyNumbers = new int[index];
46     pUglyNumbers[0] = 1;
47     int nextUglyIndex = 1;
48  
49     int *pMultiply2 = pUglyNumbers;
50     int *pMultiply3 = pUglyNumbers;
51     int *pMultiply5 = pUglyNumbers;
52  
53     while(nextUglyIndex < index)
54     {
55         int min = Min(*pMultiply2 * 2, *pMultiply3 * 3, *pMultiply5 * 5);
56         pUglyNumbers[nextUglyIndex] = min;
57  
58         while(*pMultiply2 * 2 <= pUglyNumbers[nextUglyIndex])
59             ++pMultiply2;
60         while(*pMultiply3 * 3 <= pUglyNumbers[nextUglyIndex])
61             ++pMultiply3;
62         while(*pMultiply5 * 5 <= pUglyNumbers[nextUglyIndex])
63             ++pMultiply5;
64  
65         ++nextUglyIndex;
66     }
67  
68     int ugly = pUglyNumbers[nextUglyIndex - 1];
69     delete[] pUglyNumbers;
70     return ugly;
71 }
72  
73  int Min(int number1, int number2, int number3)
74  {
75      int min = (number1 < number2) ? number1 : number2;
76      min = (min < number3)? min : number3;
77      
78      return min;
79  }
80  
81 int main()
82 {
83     int index = 10;
84     printf("solution1 %d\n", GetUglyNumber_Solution1(index));
85     printf("solution2 %d\n", GetUglyNumber_Solution2(index));
86     printf("\n");
87     
88     index = 30;
89     printf("solution1 %d\n", GetUglyNumber_Solution1(index));
90     printf("solution2 %d\n", GetUglyNumber_Solution2(index));
91     printf("\n");
92     
93     index = 1500;
94     printf("solution1 %d\n", GetUglyNumber_Solution1(index));
95     printf("solution2 %d\n", GetUglyNumber_Solution2(index));
96     printf("\n");
97     
98     return 0;
99 }