Ugly numbers are numbers whose only prime factors are 2, 3 or 5.
The sequence 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...
shows the first 11 ugly numbers. By convention, 1 is included.
Write a program to find and print the 1500 'th ugly number.
算法思路:
一个正整数m可表示如下：
m = (p1)j1 * (p2)j2 * … *(pn)jn
Ugly number = 2j1 * 3j2 * 5j3 (j1,j2,j3> =0)
在已知序列中,找一个最小的数,使得它乘以2比已知序列最后一个元素大;找一个最小的数,使得它乘以3比最后一个元素大;找一个最小的数,使得它乘以5比最后一个元素大. 在这三个乘积中找最小的添加到表尾,反复按此规则构造递增序列,直到表中有1500个元素。
可以用数组预先分配1500个单元,也可以用链表动态分配。
这题感觉很容易，可不知从何下手，请帮帮忙！
------解决方案--------------------
public class Temp {
/**
* @param args
*/
public static void main(String[] args) {
// 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15,
int [] u=new int[1600];
int [][] a=new int[1600][3];
int p[]=new int[3];
int ulen=0;
while(ulen <1500){
if(ulen==0){
u[0]=1;
}
else
{
int min=a[p[0]][0];
for(int i=0;i <3;i++){
if(a[p[i]][i] <min){
min=a[p[i]][i];
}
}
for(int i=0;i <3;i++){
if(a[p[i]][i]==min){
p[i]++;
}
}
u[ulen]=min;
}
a[ulen][0]=u[ulen]*2;
a[ulen][1]=u[ulen]*3;
a[ulen][2]=u[ulen]*5;
ulen++;
}
System.out.println(u[1499]);
}
}
------解决方案--------------------
public static void main(String[] args) {
int N = 1500;
int[] num = new int[N];
num[0] = 1;
int num2 = 0;
int num3 = 0;
int num5 = 0;
for (int i = 1; i < num.length; i++) {
int n2 = num[num2] * 2;
int n3 = num[num3] * 3;
int n5 = num[num5] * 5;
n2 = (n2 <= num[i - 1]) ? num[++num2] * 2 : n2;
n3 = (n3 <= num[i - 1]) ? num[++num3] * 3 : n3;
n5 = (n5 <= num[i - 1]) ? num[++num5] * 5 : n5;
// 找出 n2、n3、n5 中最小的一个
int min = n2;
if(n3 < n2)
min = n3;
if(n5 < min)
min = n5;
num[i] = min;
}
// 输出结果
for(int i=0; i <num.length; i++) {
System.out.printf( "%9d%s ", num[i], (i+1)%10==0? "\n ": " ");
}
}
结果与 galois_godel 一致，速度约快两倍。