諾西筆試最后一道題，題意:
把只包含質(zhì)因子2、3和5的數(shù)稱作丑數(shù)（Ugly Number），例如：2,3,4,5,6,8,9,10,12,15,等，習(xí)慣上我們把1當(dāng)做是第一個丑數(shù)。
寫一個高效算法，返回第n個丑數(shù)。
最普通（也最耗時(shí)）的做法是從1開始遍歷，然后判斷這個數(shù)的因式分解中只包含2,3,5，滿足則找到了一個，一直找下去，直到第n個被找出！測試了一下，找第1500個丑數(shù)耗時(shí)40秒！
分析：假設(shè)數(shù)組ugly[N]中存放不斷產(chǎn)生的丑數(shù)，初始只有一個丑數(shù)ugly[0]=1，由此出發(fā)，下一個丑數(shù)由因子2,3,5競爭產(chǎn)生，得到ugly[0]*2, ugly[0]*3, ugly[0]*5， 顯然最小的那個數(shù)是新的丑數(shù)，所以第2個丑數(shù)為ugly[1]=2，開始新一輪的競爭，由于上一輪競爭中，因子2獲勝，這時(shí)因子2應(yīng)該乘以ugly[1]才顯得公平，得到ugly[1]*2,ugly[0]*3,ugly[0]*5， 因子3獲勝，ugly[2]=3，同理，下次競爭時(shí)因子3應(yīng)該乘以ugly[1]，即：ugly[1]*2, ugly[1]*3, ugly[0]*5, 因子5獲勝，得到ugly[3]=5，重復(fù)這個過程，直到第n個丑數(shù)產(chǎn)生。總之：每次競爭中有一個（也可能是兩個）因子勝出，下一次競爭中 勝出的因子就應(yīng)該加大懲罰！
程序如下所示（只要把程序中的因子改一下就可以得到新的題目），耗時(shí)忽略不計(jì)：
運(yùn)行結(jié)果：第1500個丑數(shù)：859963392， 第1691個丑數(shù)2 125 764 000，第1692個丑數(shù)就越界了。
int表示的最大整數(shù)是2,147,483,647，可由std::cout<<(std::numeric_limits<int>::max)()<<"\n";給出！
#include <iostream>
using namespace std;
int mymin(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 = mymin(ugly[index2]*2, ugly[index3]*3, ugly[index5]*5); //競爭產(chǎn)生下一個丑數(shù)
if (val == ugly[index2]*2) //將產(chǎn)生這個丑數(shù)的index*向后挪一位；
++index2;
if (val == ugly[index3]*3) //這里不能用elseif，因?yàn)榭赡苡袃蓚€最小值，這時(shí)都要挪動；
++index3;
if (val == ugly[index5]*5)
++index5;
ugly[index++] = val;
}
/**//*/
for (int i = 0; i < n; ++i)
cout << ugly[i] << endl;
//*/
int result = ugly[n-1];
delete[] ugly;
return result;
}
int main()
{
int num=1;
printf("input the number: \n");
scanf("%d", &num);
printf("%d \n",FindUgly(num));
return 0;
}