首页 > 代码库 > poj1338

poj1338

2024-07-06 05:11:27   221人阅读

                                                                             Ugly Numbers
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 19952   Accepted: 8856

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

Source

New Zealand 1990 Division I,UVA 136
这题题意好理解，给一个定义，某个数只能被2,3,5整除，这样的数叫做丑数，然后有这样一个丑数序列，给出n，让我们求出丑数序列中的第n个丑数。
这个题目直观上面有一个简单解法，我们只需要用这个数分别不停的除以2,3,5，直到number%2 or 3 or 5不为零为止，当除到最后，如果number = 1，则说明这个数是丑数，于是我们加入序列，或者数一个计数器累加，到最后输出，当然也可以先筛选出某个范围内的丑数，然后根据n直接对应输出。但是这样会超时，因为很多非丑数我们也进行了循环除法，效率太低。于是有更好的方法：
　　我们想像筛选法挑选素数那样，以乘积进行扩展，所有的丑数都等于小于它的某个丑数*2 or *3 or *5得来，我们给一个数组，初始有一个丑数1，然后分别*2 *3 *5，这样确实可以得到所有丑数，但是第一不能保证有序，第二不能保证不重复，如果解决了这两个中任何一个问题就OK了，解决了有序，当然就不重复，解决了重复，利用STL sort排序就OK了。下面是保证有序产生丑数，基本思路：
　　

这种思路的关键在于怎样确保数组里面的丑数是排好序的。我们假设数组中已经有若干个丑数，排好序后存在数组中。我们把现有的最大丑数记做M。现在我们来生成下一个丑数，该丑数肯定是前面某一个丑数乘以2、3或者5的结果。我们首先考虑把已有的每个丑数乘以2。在乘以2的时候，能得到若干个结果小于或等于M的。由于我们是按照顺序生成的，小于或者等于M肯定已经在数组中了，我们不需再次考虑；我们还会得到若干个大于M的结果，但我们只需要第一个大于M的结果，因为我们希望丑数是按从小到大顺序生成的，其他更大的结果我们以后再说。我们把得到的第一个乘以2后大于M的结果，记为M2。同样我们把已有的每一个丑数乘以3和5，能得到第一个大于M的结果M3和M5。那么下一个丑数应该是M2、M3和M5三个数的最小者。

前面我们分析的时候，提到把已有的每个丑数分别都乘以2、3和5，事实上是不需要的，因为已有的丑数是按顺序存在数组中的。对乘以2而言，肯定存在某一个丑数T2，排在它之前的每一个丑数乘以2得到的结果都会小于已有最大的丑数，在它之后的每一个丑数乘以2得到的结果都会太大。我们只需要记下这个丑数的位置，同时每次生成新的丑数的时候，去更新这个T2。对乘以3和5而言，存在着同样的T3和T5。

以上是借用：http://zhedahht.blog.163.com/blog/static/2541117420094245366965/   感觉自己讲不出来。。

除了这种思路外，看到还有大牛用STL中的set自动删除重复元素，这样就更加简单了。

还有一种，纯粹为了A题目，利用第一种方法先得出题目给的1500范围内的所有丑数，然后打表，有点无赖的感觉

http://blog.csdn.net/coder_xia/article/details/6707600  这个大牛总结了很多方法，值得借鉴。

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 
 5 int Min(int a,int b,int c)
 6 {
 7     int temp = a>b?b:a;
 8     return (temp>c?c:temp);
 9 }
10 
11 int main()
12 {
13     int n;
14     int Uglynumber[1502]={0,1};
15     int num_1=1,num_2=1,num_3=1;
16     for(int i = 2;i<=1501;i++)
17     {
18         Uglynumber[i]= Min(Uglynumber[num_1]*2,Uglynumber[num_2]*3,Uglynumber[num_3]*5);
19         if(Uglynumber[num_1]*2==Uglynumber[i])
20         {
21             num_1++;
22         }
23         if(Uglynumber[num_2]*3==Uglynumber[i])
24         {
25             num_2++;
26         }
27         if(Uglynumber[num_3]*5==Uglynumber[i])
28         {
29             num_3++;
30         }
31     }
32     while(scanf("%d",&n)!=EOF&&n!=0)
33     {
34         printf("%d\n",Uglynumber[n]);
35     }
36     return 0;
37 }

 


联系
我们