[ACM_ZJUT_1089]Ugly Numbers

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;
}

原文地址（本人博客）：http://lanfei.sinaapp.com/2012/03/242.html

欢迎访问交流。