集合的前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 }