奇怪的数列（2X+1 3X+2）

admin

有一个数列是递增序列，第一个元素是1，后面的每个数都是前面某个数的2倍+1或者3倍+2，求第100个数。

admin

1. #include<iostream>
   
2. using namespace std;
   
3. const int mm=10000;
   
4. int a[mm];
   
5. int head,tail;
   
6. bool b;
   
7. int x,x1,x2,i,j;
   
8. int main()
   
9. {
   
10.     a[0]=1;
    
11.     head=tail=0;
    
12.     b=true;
    
13.     while (b && (head<=tail) && (tail<=mm-100))
    
14.     {
    
15.         x=a[head];
    
16.         x1=2*x+1;
    
17.         ///找head和tail之间那个数字>=x1
    
18.         ///=就不管了 >就将此数字以及后面的数字挪一位，腾个空间给ｘ１
    
19.         i=tail;
    
20.         while (a[i]>x1) i--;  ///隐含一个条件a[head]<x
    
21.         if (a[i]<x1)
    
22.         {
    
23.             for (j=tail; j>=i+1; j--) a[j+1]=a[j];  ///挪出空间
    
24.             a[i+1]=x1;tail++; ///进队列
    
25.         }
    
26.         x2=3*x+2;
    
27.         i=tail;
    
28.         while (a[i]>x2) i--;
    
29.         if (a[i]<x2)
    
30.         {
    
31.             for (j=tail; j>=i+1; j--) a[j+1]=a[j];
    
32.             a[i+1]=x2;tail++;
    
33.         }
    
34.         head++;
    
35.         if (head>=100) b=false;    ///只要找到前100项
    
36.     }
    
37.     if (!b) for (i=0; i<=99; i++ ) cout<<a[i]<<' ';
    
38. }
    

复制代码

admin

1. #include<iostream>
   
2. using namespace std;
   
3. const int mm=10000;
   
4. int a[mm];
   
5. int head,tail;
   
6. bool b;
   
7. int x,x1,x2,i,j;
   
8. int main()
   
9. {
   
10.     a[0]=1;
    
11.     head=tail=0;
    
12.     b=true;
    
13.     while (b && (head<=tail) && (tail<=mm-100))
    
14.     {
    
15.         x=a[head];
    
16.         x1=2*x+1;
    
17.         ///找head和tail之间那个数字>=x1
    
18.         ///=就不管了 >就将此数字以及后面的数字挪一位，腾个空间给ｘ１
    
19.         i=tail;
    
20.         while (a[i]>x1) i--;  ///隐含一个条件a[head]<x
    
21.         if (a[i]<x1)
    
22.         {
    
23.             for (j=tail; j>=i+1; j--) a[j+1]=a[j];  ///挪出空间
    
24.             a[i+1]=x1;tail++; ///进队列
    
25.         }
    
26.         x2=3*x+2;
    
27.         i=tail;
    
28.         while (a[i]>x2) i--;
    
29.         if (a[i]<x2)
    
30.         {
    
31.             for (j=tail; j>=i+1; j--) a[j+1]=a[j];
    
32.             a[i+1]=x2;tail++;
    
33.         }
    
34.         head++;
    
35.         if (head>=100) b=false;    ///只要找到前100项
    
36.     }
    
37.     if (!b) for (i=0; i<=99; i++ ) cout<<a[i]<<' ';
    
38. }
    

复制代码

黄煦喆

1. #include<iostream>
   
2. #include<queue>
   
3. using namespace std;
   
4. int n,x;
   
5. priority_queue<int,vector<int>,greater<int> >pq;
   
6. bool b[10000000];
   
7. int main()
   
8. {
   
9.     pq.push(1);
   
10.     b[1]=1;
    
11.     while(!pq.empty()&&n<100)
    
12.     {
    
13.         x=pq.top();
    
14.         pq.pop();
    
15.         n++;
    
16.         if(!b[2*x+1])pq.push(2*x+1);
    
17.         b[2*x+1]=1;
    
18.         if(!b[3*x+2])pq.push(3*x+2);
    
19.         b[3*x+2]=1;
    
20.     }
    
21.     cout<<x;
    
22.     return 0;
    
23. }
    

复制代码

admin

楼上同学会用 优先队列了！ 好牛呀 ！为什么不顺便y弄个set判重呢

黄煦喆

admin 发表于 2018-8-19 10:09
楼上同学会用 优先队列了！ 好牛呀 ！为什么不顺便y弄个set判重呢

之前没想到，谢谢老师提醒

黄煦喆

1. #include<iostream>
   
2. #include<queue>
   
3. #include<set>
   
4. using namespace std;
   
5. int n,x;
   
6. priority_queue<int,vector<int>,greater<int> >pq;
   
7. set<int>s;
   
8. int main()
   
9. {
   
10.     pq.push(1);
    
11.     s.insert(1);
    
12.     while(!pq.empty()&&n<100)
    
13.     {
    
14.         x=pq.top();
    
15.         pq.pop();
    
16.         n++;
    
17.         if(!s.count(2*x+1))pq.push(2*x+1);
    
18.         s.insert(2*x+1);
    
19.         if(!s.count(3*x+2))pq.push(3*x+2);
    
20.         s.insert(3*x+2);
    
21.     }
    
22.     cout<<x;
    
23.     return 0;
    
24. }
    

复制代码