[ACM_ZJUT_1089]Ugly Numbers

蓝飞 蓝飞 | 时间:2012-03-28, Wed | 7,176 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;
}

 

如需转载请注明出处:蓝飞技术部落格

当前暂无评论 »