andy6804tw
7/23/2016 - 6:20 AM

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=72 下一個數必定是從之前的某個數x2或x3或x5而來的，因此要找第n個數(N[n])，

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=72 下一個數必定是從之前的某個數x2或x3或x5而來的，因此要找第n個數(N[n])，就把前n-1個數x2,x3,x5，找出大於(N[n-1])的最小值。 　　另外找第n個數的時候，乘以2不用每次都從第0個開始乘，每次紀錄2乘到哪個位置，以後就從這個位置往後找即可。例如12是從6這個數字乘以2而來，那麼要找12以後的number的時候，只要從6以後的數字乘以2開始找，因為6以前的數字乘以2不可能大於12，乘以3和乘以5也是同樣道理。

Q136: Ugly Numbers.java
content_copyfile_download
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner scn = new Scanner(System.in);
		 int N[]=new int [1501];
		    N[1]=1;
		    int p2=1,p3=1,p5=1;
		    for (int n=2; n<=1500; n++){
		        while (N[p2]*2 <= N[n-1]) p2++;
		        while (N[p3]*3 <= N[n-1]) p3++;
		        while (N[p5]*5 <= N[n-1]) p5++;
		        N[n] = Math.min (N[p2]*2, Math.min (N[p3]*3, N[p5]*5));
		    }
		    System.out.printf("The 1500'th ugly number is %d.\n",N[1500]);
	}
		/* 
    題目：136: Ugly Numbers
    作者：1010
    時間：西元 2016 年 7 月 */
}