[cpp]
/*******************************************************************************
google面試題目：我們把只包含因子2、3和5的數稱作丑數（Ugly Number）。
例如6、8都是丑數，但14不是，因為它包含因子7。習慣上我們把1當做是第一個丑數。
求按從小到大的順序的第2012個丑數。
分析：假設數組ugly[N]中存放不斷產生的丑數，
初始只有一個丑數ugly[0]=1，由此出發，
下一個丑數由因子2,3,5競爭產生，得到ugly[0]*2,
ugly[0]*3, ugly[0]*5， 顯然最小的那個數是新的丑數，
所以第2個丑數為ugly[1]=2，開始新一輪的競爭，
由於上一輪競爭中，因子2獲勝，這時因子2應該乘以ugly[1]才顯得公平，
得到ugly[1]*2,ugly[0]*3,ugly[0]*5，
因子3獲勝，ugly[2]=3，同理，下次競爭時因子3應該乘以ugly[1]，
即：ugly[1]*2, ugly[1]*3, ugly[0]*5, 因子5獲勝，得到ugly[3]=5，
重復這個過程，直到第n個丑數產生。總之：
每次競爭中有一個（也可能是兩個）因子勝出，下一次競爭中
勝出的因子就應該加大懲罰！
本質就是2 ，3 ，5 的乘積的組合，不過要按照順序組合，
每次都將2，3，5乘以一個已經是丑數的數，
再比較三者的大小，小的進入數組，然後繼續比較；
例如：1是丑數，那麼下一個斗勁 2 * 1、3 * 1和5*1，
那麼獲得的是2，2進入數組，下面比較的是2*2、3*1 和5*1
（ 重視因為後面的3*1和5*1的大小並不斷定，所以還要持續進行比較）
獲得3進入數組，再比較 2 * 2、3 * 2和5*1.
************************************************************************/
#include<cstdio>
#include<iostream>
#include<cstdlib>
using namespace std;
/*the smallest in the three*/
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);
//競爭產生下一個丑數
if (val == ugly[index2]*2)
//將產生這個丑數的index*向後挪一位；
++index2;
if (val == ugly[index3]*3)
//這裡不能用elseif，因為可能有兩個最小值，這時都要挪動；
++index3;
if (val == ugly[index5]*5)
++index5;
ugly[index++] = val;
}
int result = ugly[n-1]; //ugly[0] = 1 是第一個丑數
delete[] ugly;
return result;
}
int main()
{
int num=1;
cout<<"input the number:"<<endl;
cin>>num;
cout<<"the "<<(num)<<" th agly number is "<<FindUgly(num);
return 0;
}
/*******************************************************************************
google面試題目：我們把只包含因子2、3和5的數稱作丑數（Ugly Number）。
例如6、8都是丑數，但14不是，因為它包含因子7。習慣上我們把1當做是第一個丑數。
求按從小到大的順序的第2012個丑數。
分析：假設數組ugly[N]中存放不斷產生的丑數，
初始只有一個丑數ugly[0]=1，由此出發，
下一個丑數由因子2,3,5競爭產生，得到ugly[0]*2,
ugly[0]*3, ugly[0]*5， 顯然最小的那個數是新的丑數，
所以第2個丑數為ugly[1]=2，開始新一輪的競爭，
由於上一輪競爭中，因子2獲勝，這時因子2應該乘以ugly[1]才顯得公平，
得到ugly[1]*2,ugly[0]*3,ugly[0]*5，
因子3獲勝，ugly[2]=3，同理，下次競爭時因子3應該乘以ugly[1]，
即：ugly[1]*2, ugly[1]*3, ugly[0]*5, 因子5獲勝，得到ugly[3]=5，
重復這個過程，直到第n個丑數產生。總之：
每次競爭中有一個（也可能是兩個）因子勝出，下一次競爭中
勝出的因子就應該加大懲罰！
本質就是2 ，3 ，5 的乘積的組合，不過要按照順序組合，
每次都將2，3，5乘以一個已經是丑數的數，
再比較三者的大小，小的進入數組，然後繼續比較；
例如：1是丑數，那麼下一個斗勁 2 * 1、3 * 1和5*1，
那麼獲得的是2，2進入數組，下面比較的是2*2、3*1 和5*1
（ 重視因為後面的3*1和5*1的大小並不斷定，所以還要持續進行比較）
獲得3進入數組，再比較 2 * 2、3 * 2和5*1.
************************************************************************/
#include<cstdio>
#include<iostream>
#include<cstdlib>
using namespace std;
/*the smallest in the three*/
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);
//競爭產生下一個丑數
if (val == ugly[index2]*2)
//將產生這個丑數的index*向後挪一位；
++index2;
if (val == ugly[index3]*3)
//這裡不能用elseif，因為可能有兩個最小值，這時都要挪動；
++index3;
if (val == ugly[index5]*5)
++index5;
ugly[index++] = val;
}
int result = ugly[n-1]; //ugly[0] = 1 是第一個丑數
delete[] ugly;
return result;
}
int main()
{
int num=1;
cout<<"input the number:"<<endl;
cin>>num;
cout<<"the "<<(num)<<" th agly number is "<<FindUgly(num);
return 0;
}
