丑数

只包含因子2,3,5的数称作丑数。要求按从小到大的顺序输出指定数量的丑数。

有2中方法：

第一种：用穷举法，从最小的1开始判断穷举，是丑数就输出，否则继续循环判断。判断的方法是：如果一个数能被2整除，我们把他连续除以2；如果能被3整除，我们把他连续除以3；如果能被5整除，我们把他连续除以5。如果最后得到的值为1，那么这个数就是丑数。具体代码如下：

 1 ////////////丑数///////////////////////
 2 
 3 bool isUgly(int number)
 4 {
 5     assert(number > 0);
 6     while (number % 2 == 0)
 7     {
 8         number /= 2 ;
 9     }
10     while (number % 3 == 0)
11     {
12         number /= 3 ;
13     }
14     while (number % 5 == 0)
15     {
16         number /= 5 ;
17     }
18 
19     return (number == 1) ? true : false ;
20 }
21 void GetUgly1(int index)
22 {
23     if (index <= 0)
24     {
25         return;
26     }
27     int number = 0 ;
28     int count = 0 ;
29     while (count < index)
30     {
31         ++number;
32         if (isUgly(number))
33         {
34             count++ ;
35             cout<<number<<endl;
36         }
37     }
38 }

1 int main()
2 {
3     unsigned long  start_time = GetTickCount(); 
4     GetUgly1(1000);
5     unsigned long  end_time = GetTickCount(); 
6     cout<<"The run time is: "<<(end_time-start_time)<<"ms!"<<endl;//输出运行时间
7     getchar();
8     return 0;
9 }

输出1000个丑数的结果如下图：

第二种：

用空间换时间，创建一个数组，里面的数字是排好序的丑数，下一个丑数是前面丑数乘以2、3、5得到的大于当前最大丑数的最小一个数。和第一种思路相比，第二种思路不需要在非丑数上做任何计算，因此时间效率会明显提升，但增加了空间消耗。具体代码如下：

 1 int Min(int num1 , int num2 , int num3)
 2 {
 3     int min = (num1 < num2) ? num1 : num2 ;
 4     return (min < num3) ? min : num3 ;
 5 }
 6 
 7 
 8 void GetUgly2(int index)
 9 {
10     if (index <= 0)
11     {
12         return ;
13     }
14     int* pUglyNumbers = new int[index];
15     pUglyNumbers[0] = 1 ;
16     int* pUglyNumbers2 = pUglyNumbers ;//指向丑数乘以因数2后得到的最大丑数的位置，起始位置为pUglyNumbers[0]
17     int* pUglyNumbers3 = pUglyNumbers ;//指向丑数乘以因数3后得到的最大丑数的位置，起始位置为pUglyNumbers[0]
18     int* pUglyNumbers5 = pUglyNumbers ;//指向丑数乘以因数5后得到的最大丑数的位置，起始位置为pUglyNumbers[0]
19     int NextUgly = 1 ; //下一个丑数存储的位置
20     while ( NextUgly < index )
21     {
22         int min = Min((*pUglyNumbers2) * 2 , (*pUglyNumbers3) * 3 , (*pUglyNumbers5) * 5) ;//取最小的值作为下一个丑数
23         pUglyNumbers[NextUgly] = min ;
24 
25         while ((*pUglyNumbers2) * 2 <= min) //改变pUglyNumbers2的位置，使其指向后续所有丑数乘以因数2后得到的最大丑数
26         {
27             pUglyNumbers2++ ;
28         }
29         while ((*pUglyNumbers3) * 3 <= min) //改变pUglyNumbers3的位置，使其指向后续所有丑数乘以因数3后得到的最大丑数
30         {
31             pUglyNumbers3++ ;
32         }
33         while ((*pUglyNumbers5) * 5 <= min) //改变pUglyNumbers5的位置，使其指向后续所有丑数乘以因数5后得到的最大丑数
34         {
35             pUglyNumbers5++ ;
36         }
37 
38         NextUgly++ ;
39 
40     }
41 
42     for (int i = 0 ; i < index ; i++)
43     {
44         cout<<pUglyNumbers[i]<<endl;
45     }
46 
47     delete[] pUglyNumbers ;
48 
49 }
50 
51 int main()
52 {
53     unsigned long  start_time = GetTickCount(); 
54     GetUgly2(1000);
55     unsigned long  end_time = GetTickCount(); 
56     cout<<"The run time is: "<<(end_time-start_time)<<"ms!"<<endl;//输出运行时间
57     getchar();
58     return 0;
59 }

输出1000个丑数的结果如下图：

可以看见第二种方法时间效率提高了10多倍！！