[ACM_ZJUT_1089]Ugly Numbers

杰拉斯 | 时间：2012-03-28, Wed | 9,000 views
编程算法　

Ugly Numbers

Time Limit:1000MS Memory Limit:32768K

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, 15, ... shows the first 11 ugly numbers. By convention, 1 is included. Write a program to find and print the n’th ugly number.

Input

Every integer number (≤1500)describing position of ugly number from 1.If integer number is 0,the process should ended. Maybe there are 10000 integer numbers on input data.

Output

Every integer given should output a line as shown below, The <n>th ugly number is <number>. with <n> replaced by the integer number and <number> replaced by the number computed.

Sample Input

5 16

Sample Output

The 5th ugly number is 5.The 16th ugly number is 25.

Source

ZJUT1089

本题最开始的想法是使用set容器，将1插入容器后，利用循环，将容器中的每一位从小到大分别乘以2,3,5，利用set容器的特性去重并自动排序，

#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
int main()
{
	set<int> s;
	s.insert(1);
	set<int>::iterator it = s.begin();
	//此处使用1600而非1500，是为了防止类似*it*5 > *(++it)*2的情况出现而导致循环结束时较小的丑数仍未插入容器
	while(s.size()<=1600)
	{
		s.insert(*it*2);
		s.insert(*it*3);
		s.insert(*it*5);
		it++;
	}
	int n;
	while(cin>>n&&n)
	{
		it = s.begin();
		int i = n;
		while(--i){
			++it;
		}
		cout<<"The "<<n<<"th ugly number is "<<*it<<"."<<endl;
	}
	return 0;
}

虽然代码Accept，但很容易看出，这种算法有大量的数据重复，且需要比题目给出的数目1500循环更多次数，极大地增加了算法的时间复杂度，因此应寻找一种更简便的算法，思路如下：

定义一个集合，该集合中有元素1，如果x在集合中，并且y是x的下一个丑数，那么x*2，x*3，x*5也在集合中，其它数不再集合中，这三个数中必定是2x最小，因此首先放入数组中，而此时*2最小的应该是x的下一个丑数y*2，此时应该找出y*2，x*3，x*5中最小的数放入数组，以此类推，具体操作如下：

1
*2
*3
*5

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

1     2
*3   *2
*5

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

1     2     3
*5   *2
*3

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

1     2     3     4
*5   *3    *2

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

1     2     3     4
*3   *2
*5

以此类推，直到获得1500的结果集，实现代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int ugly[1501];
	ugly[1] = 1;
	int x2 = 1, x3 = 1, x5 = 1, num, n;
	for(int i = 2; i < 1501; ++i){
		num = min(min(ugly[x2] * 2, ugly[x3] * 3), ugly[x5] * 5);
		if(num == ugly[x2] * 2)
			++x2;
		if(num == ugly[x3] * 3)
			++x3;
		if(num == ugly[x5] * 5)
			++x5;
		ugly[i] = num;
	}
	while(cin >> n){
		cout << "The " << n << "th ugly number is " << ugly[n] << "." << endl;
	}
	return 0;
}

如需转载请注明出处：杰拉斯的博客

杰拉斯的博客