Ugly Numbers

Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 17500 Accepted: 7757

Description

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, …
shows the first 10 ugly numbers. By convention, 1 is included.
Given the integer n,write a program to find and print the n’th ugly number.

Input

Each line of the input contains a postisive integer n (n <= 1500).Input is terminated by a line with n=0.

Output

For each line, output the n’th ugly number .:Don’t deal with the line with n=0.

Sample Input

1
2
9
0

Sample Output

1
2
10

Source

解:
丑陋数是仅有素因子2、3、5的整数,1 * 2, 1 * 3, 1 * 5, 2 * 2, 2 * 3, 2 * 5……这样算下去,得到的是2, 3, 5, 4, 6, 10,而4应该排在5的前面,也就是说这样计算出来的值还要进行排序,感觉非常耗时间,怎么办呢?我们可以创建一个数组,把丑陋数的列表计算出来,然后通过输入值在数组中快速寻找出对应的值。我们得想办法进行动态排序,我们可以先设置3个变量来记录2的倍数、3的倍数、5的倍数的个数,将这些个数作为索引,找出丑陋数列表数组中对应的值,再乘以对应的2、3、5就可以得到现在需要插入列表的2的倍数、3的倍数、5的倍数的值,找到这三个值的最小的数,将这个数添加到数组的最后面,一直循环这个操作就可以实现动态排序了。可能我上面表达得不是很好,看代码应该就清楚了,代码如下:
#include <stdio.h>
int twoNum = 0, threeNum = 0, fiveNum = 0;
int ugly[1500];

void create()
{
	ugly[0] = 1;
	for (int i = 1; i < 1500; i++) {
		int min = ugly[twoNum] * 2, b = ugly[threeNum] * 3, c = ugly[fiveNum] * 5;
		if (b < min) {
			min = b;
		}
		if (c < min) {
			min = c;
		}
		ugly[i] = min;
		if (ugly[i] == ugly[twoNum] * 2) {
			twoNum++;
		}
		if (ugly[i] == ugly[threeNum] * 3) {
			threeNum++;
		}
		if (ugly[i] == ugly[fiveNum] * 5) {
			fiveNum++;
		}
	}
}

int main()
{
	create();
	int n;
	while (scanf("%d", &n) != EOF) {
		if (n == 0) {
			return 0;
		}
		printf("%d\n", ugly[n - 1]);
	}
	return 0;
}
Result Memory Time Language Code Length
Accepted 172K 0MS C++ 661B

 

Tonitech版权所有 | 转载请注明出处: http://www.tonitech.com/1785.html

《Ugly Numbers》有1个想法

发表评论