劍指OFFER之丑數（九度OJ1214）

題目描述：

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

輸入：

輸入包括一個整數N(1<=N<=1500)。

輸出：

可能有多組測試數據，對於每組數據，
輸出第N個丑數。

樣例輸入：

3 

樣例輸出：

3 

解題思路：

　　最簡單的思路是，從1到大數，每個數都檢測一遍是否是丑數，檢測方法可以考慮

int ugly(int number){
    if(number%2 == 0){
        return ugly(number/2);
    }else if(number%3 == 0){
        return ugly(number/3);
    }else if(number%5 == 0){
        return ugly(number/5);
    }else
        return number==1?true:false;
}

　　可是這種思路，會浪費大量的時間，最後就會超時。

　　我們考慮一個數組，數組存儲的是當前的丑數，以後的每個丑數，都是用之前的數組的元素相乘的來的。接下來就是如何得到後面的丑數並保證它是有序的。

　　可以想到，數組的第一個元素是1,1與2 3 5分別相乘，可以得到三個值，這三個值裡面最小的，肯定就是下一個丑數的最大值，接著max2的下標後移，繼續比較。

void mkUglyNumber(){
    gArr[top++] = 1;
    int *max2 = gArr;
    int *max3 = gArr;
    int *max5 = gArr;
    while(top < 1500){
        int min = getMin(*max2*2,*max3*3,*max5*5);
        gArr[top] = min;
        while(*max2*2 <= gArr[top])
            ++max2;
        while(*max3*3 <= gArr[top])
            ++max3;
        while(*max5*5 <= gArr[top])
            ++max5;
        ++top;
    }
}

　　比如，當前的數組元素只是1，那麼與2 3 5 相乘得到2 3 5，顯然得到的最小值是2。數組元素變為1 2。

　　下標這回變為2 1 1，繼續與2 3 5相乘，得到4 3 5，找出其中最小的，再放進數組，元素變為1 2 3。

　　繼續，直到找到1500個丑數之後，每次進行讀取丑數即可。

全部代碼：

#include <stdio.h>
#define MAXSIZE 1500
void mkUglyNumber();
int getMin(int max2,int max3,int max5);
int gArr[MAXSIZE];
int top;
int main(){
    int n;
    top = 0;
    mkUglyNumber();
    while(scanf("%d",&n)!=EOF && n>=1 && n<=1500){
        printf("%d\n",gArr[n-1]);
    }
    return 0;
}
void mkUglyNumber(){
    gArr[top++] = 1;
    int *max2 = gArr;
    int *max3 = gArr;
    int *max5 = gArr;
    while(top < 1500){
        int min = getMin(*max2*2,*max3*3,*max5*5);
        gArr[top] = min;
        while(*max2*2 <= gArr[top])
            ++max2;
        while(*max3*3 <= gArr[top])
            ++max3;
        while(*max5*5 <= gArr[top])
            ++max5;
        ++top;
    }
}
int getMin(int max2,int max3,int max5){
    int min = max2<max3?max2:max3;
    return min<max5?min:max5;
}
/**************************************************************
    Problem: 1214
    User: xhalo
    Language: C
    Result: Accepted
    Time:10 ms
    Memory:920 kb
****************************************************************/