丑数

题目:

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 1500’th ugly number. Input There is no input to this program.

Output Output should consist of a single line as shown below, with ‘’ replaced by the number computed. Sample Output The 1500'th ugly number is .

解法1:

以前老师讲的方法,一个个把所有的丑数从小到大的得到

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 int min1 (int  a,int b)
 6 {
 7    return a<b?a:b ;
 8 }
 9 
10 int main()
11 {
12     long long a[1500];
13     a[0] = 1;
14     long long a2=0,a3=0,a5=0,min0;
15 
16     for(int i = 1;i<1500;i++)　　　　　　
17     {
18         while(a[a2]*2 <= a[i-1])
19             a2++;
20         while(a[a3]*3 <= a[i-1])
21             a3++;
22         while(a[a5]*5 <= a[i-1])
23             a5++;
24         min0 = min1(min1(a[a2]*2,a[a3]*3),a[a5]*5);
25         a[i] = min0;
26 
27 
28     }
29 
30     cout<<"The 1500'th ugly number is "<<a[1499]<<'.'<<endl;
31 
32 
33     return 0;
34 }

解法2:

这是书上用STL的方法的代码

 1 #include <iostream>
 2 #include <vector>
 3 #include <queue>
 4 #include <set>
 5 #include <stdio.h>
 6 
 7 using namespace std;
 8 
 9 typedef long long LL;
10 
11 const int coeff[3] = {2,3,5};
12 
13 int main()
14 {
15     priority_queue<LL,vector<LL>,greater<LL> >pq;
16     set<LL>s;
17 
18     pq.push(1);
19     s.insert(1);
20 
21     for(int i = 1;;i++)
22     {
23         LL x = pq.top();pq.pop();
24         cout<<x<<"*"<<endl;
25         getchar();getchar();
26         if(i == 1500)
27         {
28             cout<<x<<"ssssss"<<endl;
29             break;
30         }
31 
32         for(int j = 0;j<3;j++)
33         {
34             LL x2 = x * coeff[j];
35             cout<<x2<<"#"<<endl;
36             getchar();getchar();
37             if(!s.count(x2)){ s.insert(x2);pq.push(x2); }
38         }
39     }
40 
41     return 0;
42 }