[ACM_ZJUT_1089]Ugly Numbers
杰拉斯 | 时间:2012-03-28, Wed | 9,351 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
本题最开始的想法是使用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; }
如需转载请注明出处:杰拉斯的博客
当前暂无评论 »