由于任意一个ugly number（设为第n个）都只有因数2、3、5，即它是由较小的ugly number×2或×3或×5得来（假设已得到<n的所有ugly number）。用一个一维数组u[]来保存前n个ugly number。分别用p2,p3,p5来指向由×2，×3，×5得来的最大数。
p2,p3,p5均初始化为1。设已求得<n的任意ugly number，则
the nth ugly number = min{2×u[p2]，3×u[p3]，5×u[p5]}。
并更新p2,p3,p5，使得它们始终指向由×2，×3，×5得来的最大数
（注意它们可以指向同一个数，这时要同时更新）。


// 1338 ugly number
# include <iostream>
using namespace std;

const int N = 1500;
unsigned int ugly_numbers[N];

int min(int a, int b, int c, int &x1, int &x2, int &x3)
{
    if (a > b) {
        if (b > c) {
            x3 = 1;    
            return c;                // a > b > c
        } else if (b < c) {
            x2 = 1;    
            return b;                // a > b, c > b
        } else {
            // b = c
            x2 = 1;
            x3 = 1;
            return b;                // a > b = c
        }
    } else if (a < b) {
        if (b > c) {
            if (a > c) {
                x3 = 1;
                return c;            // b > a > c
            } else if (a < c) {
                x1 = 1;
                return a;            // b > a, c > a
            } else {
                // a = c
                x1 = 1;
                x3 = 1;
                return a;            // b > a = c
            }
        } else if (b < c) {
            x1 = 1;
            return a;                // c > b > a
        } else {
            // b = c
            x1 = 1;
            return a;                // b = c > a
        }
    } else {
        // a == b
        if (b > c) {
            x3 = 1;
            return c;                // a = b > c
        } else if (b < c) {
            x1 = 1;
            x2 = 1;
            return b;                // c > a = b
        } else {
            // b = c
            x1 = 1;
            x2 = 1;
            x3 = 1;
            return a;                // a = b = c
        }
    }
}
int nth(int n)
{
    ugly_numbers[1] = 1;
    int p2 = 1, p3 = 1, p5 = 1;
    for (int i = 2; i <= n; ++i) {
        int x1 = 0, x2 = 0, x3 = 0;
        ugly_numbers[i] = min(2 * ugly_numbers[p2], 3 * ugly_numbers[p3], 5 * ugly_numbers[p5],
            x1, x2, x3);
        p2 += x1;
        p3 += x2;
        p5 += x3;
    }
    return ugly_numbers[n];
}
int main()
{
    nth(N);
    int n;
    while (cin >> n) {
        if (n == 0) {
            break;
        }
        cout << ugly_numbers[n] << endl;
    }
    return 0;
}


[url=http://blog.csdn.net/Sedgewick]感兴趣的来我的窝看看。[/url]