首页 > 代码库 > poj1338

poj1338

                                                                             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。现在我们来生成下一个丑数,该丑数肯定是前面某一个丑数乘以23或者5的结果。我们首先考虑把已有的每个丑数乘以2。在乘以2的时候,能得到若干个结果小于或等于M的。由于我们是按照顺序生成的,小于或者等于M肯定已经在数组中了,我们不需再次考虑;我们还会得到若干个大于M的结果,但我们只需要第一个大于M的结果,因为我们希望丑数是按从小到大顺序生成的,其他更大的结果我们以后再说。我们把得到的第一个乘以2后大于M的结果,记为M2。同样我们把已有的每一个丑数乘以35,能得到第一个大于M的结果M3M5。那么下一个丑数应该是M2M3M5三个数的最小者。

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

以上是借用: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 }