首页 > > 程序设计 > C/C++ >

集合的前N个元素

2018-06-17 22:57:58来源：未知阅读 ()

集合的前N个元素：编一个程序，按递增次序生成集合M的最小的N个数，M的定义如下：

(1)数1属于M；

(2)如果X属于M，则Y=2*x+1和Z=3*x+1也属于M；

(3)此外再没有别的数属于M。

【分析】

可以用两个队列a和b来存放新产生的数，然后通过比较大小决定是否输出，具体方法如下：

(1)令fa和fb分别为队列a和队列b的头指针，它们的尾指针分别为ra和rb。初始时，X=1，fa=fb=ra=rb＝1；

(2)将2*x+1和3*x+1分别放入队列a和队列b的队尾，尾指针加1。即:a[r]←2*x+1，b[r]←3*x+1，r←r+1；

(3)将队列a和队列b的头结点进行比较，可能有三种情况：

(A)a[ha]>b[hb] (B)a[ha]=b[hb] (C)a[ha]<b[hb]

将比较的小者取出送入X，取出数的队列的头指针相应加1。

(4)重复(2)，(3)直至取出第N项为止。

非stl

 1 #include<iostream>
 2 using namespace std;
 3 int a[10001];
 4 int b[10001];
 5 int ha=1,ta;
 6 int hb=1,tb;
 7 int n;
 8 int tot=1;
 9 int x=1;
10 int main()
11 {
12     int n;
13     cin>>n;
14     while(tot<=n)
15     {
16         cout<<x<<" ";
17         ta++;
18         tb++;
19         a[ta]=2*x+1;
20         b[tb]=3*x+1;
21         if(a[ha]>b[hb])
22         {
23             x=b[hb];
24             hb++;
25         }
26         else if(a[ha]<b[hb])
27         {
28             x=a[ha];
29             ha++;
30         }
31         else
32         {
33             x=a[ha];
34             ha++;
35             hb++;
36         }
37         tot++; 
38     }
39     //cout<<tot;
40     return 0;
41 }

stl:

 1 #include<iostream>
 2 #include<queue>
 3 using namespace std;
 4 int tot=1;
 5 int x=1;
 6 int main()
 7 {
 8     queue<int>a;
 9     queue<int>b;
10     int n;
11     cin>>n;
12     while(tot<=n)
13     {
14         cout<<x<<" ";
15         a.push(2*x+1);
16         b.push(3*x+1);
17         if(a.front()>b.front())
18         {
19             x=b.front();
20             b.pop();
21         }
22         else if(a.front()<b.front())
23         {
24             x=a.front();
25             a.pop();
26         }
27         else 
28         {
29             x=a.front();
30             a.pop();
31             b.pop();
32         }
33         tot++;
34     }
35     return 0;
36 }