PKU 3445考查递归程序设计。大意是给出两个用集合表示的整数,求出该整数和并用集合表示出来。
0--{}
1--{{}}
2--{{},{{}}}
...
整数n的集合表示为小于n-1所有整数的集合表示的集合。如2的集合表示为以0跟1的集合表示为元素的集合。
首先要识别一个串表示的整数,可以用栈来计算括号的嵌套层次,可以用数学归纳法证明整数n的嵌套数目为n+1。
接着要输出整数n的集合表示。用递归程序实现:先输出{,再依次输出0,1,...,n-1的集合表示,中间用“,”隔开,最后输出}。
1#include <iostream>
2
3using namespace std;
4
5char stack[20];
6
7void printSet(int x)
8{
9 if(x==0) printf("{}");
10 else
11 {
12 printf("{");
13 for(int i=0;i<x-1;i++) {printSet(i);printf(",");}
14 printSet(x-1);
15 printf("}");
16 }
17 return;
18}
19
20int calSet()
21{
22 int top=0,maxi=0;
23 char ch;
24 while(scanf("%c",&ch) && ch!=10)
25 {
26 if(ch=='{') {stack[top++]=ch; maxi=top>maxi?top:maxi;}
27 else if(ch=='}') {top--;}
28 }
29 return maxi;
30}
31
32int main()
33{
34 int t;
35 scanf("%d",&t);
36 getchar();
37 while(t--)
38 {
39 int a=calSet();
40 //getchar();
41 int b=calSet();
42 printSet(a+b-2);
43 //printf("%d %d\n",a,b);
44 printf("\n");
45 }
46 //printSet(4);
47 return 1;
48}