学步园

import java.util.Scanner;

/**
 * 分析： 假设数组uglyArr[NMAX]中存放不断产生的丑数，开始时只有一个丑数uglyArr[0]=1，由此出发，
 * 下一个丑数由2、3、5竞争产生，得到uglyArr[0]*2、uglyArr[0]*3、uglyArr[0]*5，
 * 显然最小的那个数就是新的丑数，所以第2个丑数uglyArr[1]=2；接着进行新一轮的竞争 ，
 * 由于上一轮竞争中，因子2获胜，这时因子2应该乘以uglyArr[1]才显得公平，
 * 故有uglyArr[1]*2、uglyArr[0]*3、uglyArr[0]*5，此时因子3获胜
 * ，故uglyArr[2]=3；同理，下次竞争时因子3应该乘以uglyArr[1]，故uglyArr[1]*2、
 * uglyArr[1]*3、uglyArr[0]*5，此时因子5获胜，故uglyArr[3]=5；重复这个过程，
 * 直到第n个丑数产生。总之，每次竞争中有一个因子胜出，下一次竞争中此因子就应该加大惩罚。
 * 
 * @author wangzhu
 * 
 */
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = -1;
        while (cin.hasNext()) {
            n = cin.nextInt();
            System.out.println(getUgly(n));
        }
    }

    public static final int NMAX = 1501;

    public static long getUgly(int n) {
        long ugly = -1;
        long[] uglyArr = new long[NMAX];
        uglyArr[0] = 1;
        long val = -1;
        int index = 0, index2 = 0, index3 = 0, index5 = 0;
        while (index < n) {
            val = getMin(uglyArr[index2] * 2, uglyArr[index3] * 3,
                    uglyArr[index5] * 5);
            if (val == uglyArr[index2] * 2) {
                index2++;
            }
            if (val == uglyArr[index3] * 3) {
                index3++;
            }
            if (val == uglyArr[index5] * 5) {
                index5++;
            }
            uglyArr[++index] = val;
        }
        ugly = uglyArr[index - 1];
        return ugly;
    }

    public static long getMin(long a, long b, long c) {
        long ab = a < b ? a : b;
        return (ab < c) ? ab : c;
    }
}

 

丑数：因子中只包含有2、3、5的数称为丑数。习惯上把1当作第一个丑数。

输入一个数n，请输出第n个输出数。（1<n<1500）