uglynumbers.java

来自「PKU中一些数据结构基本算法题的java实现」· Java 代码 · 共 68 行

package PKU.DP;
import java.util.*;


/**
 * ID:1338
 * DP
 * @author yhm
 *
 */
public class UglyNumbers {

	static int[] array = new int[1500];
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		
		getArray();
		
		while(cin.hasNext()){
			int n = cin.nextInt();
			if(n==0){
				break;
			}
			System.out.println(array[n-1]);
			
		}

	}

	static void  getArray(){
		int num=0;
		int m2=0;
		int m3=0;
		int m5=0;
		array[num] = 1;
		num++;
		while(num<1500){
			int r2=array[m2]*2;
			int r3=array[m3]*3;
			int r5=array[m5]*5;
			
			int min = Math.min(r2, r3);
			min = Math.min(min, r5);
			
			if(min==r2){
				m2++;
			}
			else if(min==r3){
				m3++;
			}
			else{
				m5++;
			}
			if(min!=array[num-1]){
				array[num] = min;
				num++;
			}
			

			
		}
	}
	
}