Ugly Numbers
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 21307 | Accepted: 9513 |
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.
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
解题思路：
刚开始打表做，直接WA了2次，第1500个丑数，我以为会是7000000-9000000中的某个数，但是确实错的，还是用三个变量分别标记目前的位置，从1开始算，
开始分别乘上2,3,5，然后得到了新的数字，再在这些数字中找到最小的一个，如果最小的数字已经在前面的计算中得到了，那么就让x,y,z分别进行移动。。。。
直到打完这个1500长度的表结束。
代码：
# include<cstdio>
# include<iostream>
# include<algorithm>
# include<cstring>
# include<string>
# include<cmath>
# include<queue>
# include<stack>
# include<set>
# include<map>
using namespace std;
# define inf 999999999
# define MAX 1500+4
# define eps 1e-7
int a[MAX];
void init()
{
int x = 1;
int y = 1;
int z = 1;
a[1] = 1;
for ( int i = 2;i <= 1500;i++ )
{
int t = min(a[x]*2,a[y]*3);
a[i] = min(t,a[z]*5);
if ( a[i]==2*a[x] )
x++;
if ( a[i]==3*a[y] )
y++;
if ( a[i]==5*a[z] )
z++;
}
}
int main(void)
{
int n;
init();
while ( cin>>n )
{
if ( n==0 )
break;
cout<<a[n]<<endl;
}
return 0;
}