首页 > 代码库 > poj1338 Ugly Numbers（丑数模拟）

poj1338 Ugly Numbers（丑数模拟）

2024-07-11 21:56:11   223人阅读

转载请注明出处：http://blog.csdn.net/u012860063?viewmode=contents

题目链接：http://poj.org/problem?id=1338


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. 

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

思路：用一个长度为1500的数组存储这些数，另有三个游标x,y,z；

a[1]=1，x=y=z=1，代表第一个数为1，此后的数都是通过已有的数乘以2,3,5得到的，
那么x，y，z分别代表a[x],a[y],a[z]可以通过乘以2,3,5来得到新的数，i递增，每次取2*a[x], 3*a[y], 5*a[z]
中的最小值，得到a[i]后，可以将对应的x(或y,z)右移，当然如果原本通过3*2得到6，那么2*3也能得到6，
因此可能x和y都需要递增。

详见代码：

#include <iostream>
using namespace std;
int min(int a, int b, int c)
{
	return min(a,min(b,c));
}
int main()
{
	int a[1517];
	int x, y, z, i;
	x = y = z = 1, a[1] = 1;
	for(i = 2; i <= 1500; i++)
	{
		a[i] = min(2*a[x],3*a[y],5*a[z]);
		if(a[i] == 2*a[x])
		x++;
		if(a[i] == 3*a[y])
		y++;
		if(a[i] == 5*a[z])
		z++;
	}
	int n;
	while(cin >> n && n)
	{
		cout<<a[n]<<endl;
	}
	return 0;
}


联系
我们