Poj 1338 Ugly Numbers(数学推导)

一、题目大意

本题要求写出前1500个仅能被2，3，5整除的数。

二、题解

最初的想法是从1开始检验该数是否只能被2，3，5整除，方法是这样的，对于一个数，如果它能被2整除，就除以2，如果它能被3整除，就除以3，如果它能被5整除，就除以5，直到不能被2，3，5整除，看结果是不是1，如果是1就满足条件，否则不满足条件。但是第1500个数大约近10亿，显然是1s内不可以完成的。

然后仔细分析发现：满足条件的数是2^x*3^y*5^z,可以转换为这样的定义，定义一个集合，该集合中有元素1，如果x在集合中，那么2x，3x，5x也在集合中，其它数不再集合中。我们可以定义一个bool数组，初始化为false，从1开始设置为true，如果x为true，则2x，3x，5x设置为true，直到获得1500个true即可，典型的空间换时间的做法，但是这个空间也太大了！这个数组要开到近10亿才可以，显然是不可行的，内存用完了，可能都不够用。

顺着这个思路继续想下去，定义一个集合，该集合中有元素1，如果x在集合中，那么2x，3x，5x也在集合中，其它数不再集合中。按照这个思路走下去：只需要定义一个结果数组，和3个指针，分别代表待乘2的数，待乘3的数，待乘5的数，

选出乘积最小的，加入到结果集中，相应指针右移

1 2

*3 *2

选出乘积最小的，加入到结果集中，相应指针右移

1 2 3

*5 *2

选出乘积最小的，加入到结果集中，相应指针右移

1 2 3 4

*5 *3 *2

选出乘积最小的，加入到结果集中，相应指针右移

1 2 3 4

*3 *2

以此类推，直到获得1500的结果集。

参考：

Pku acm 1338 Ugly Numbers 动态规划解题报告(二十一)

三、java代码

import java.util.Scanner;

public class Main { 

    public static void main(String[] args) {

    	Scanner sc=new Scanner(System.in);

    	int n;

		int i2_mul;

		int i3_mul;

		int i5_mul;

		long[] ugly=new long[1501];

		i2_mul = 1;

		i3_mul = 1;

		i5_mul = 1;

		ugly[1]=1;

		for(  int i = 2; i <= 1500; i++ ){

			ugly[i] = Math.min(ugly[i2_mul]*2,Math.min(ugly[i3_mul]*3,ugly[i5_mul]*5));

			if(ugly[i] == ugly[i2_mul]*2 )

				i2_mul++;

			if(ugly[i] == ugly[i3_mul]*3 )

				i3_mul++;

			if(ugly[i] == ugly[i5_mul]*5)

				i5_mul++;

		}

		while((n=sc.nextInt())!=0){

    		System.out.println(ugly[n]);

    	}

    }

}

巴特西

Poj 1338 Ugly Numbers(数学推导)

最新文章

热门文章