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