PKU 3445考查遞歸程序設(shè)計(jì)。大意是給出兩個(gè)用集合表示的整數(shù)，求出該整數(shù)和并用集合表示出來。
0--{}
1--{{}}
2--{{},{{}}}
...
整數(shù)n的集合表示為小于n-1所有整數(shù)的集合表示的集合。如2的集合表示為以0跟1的集合表示為元素的集合。
首先要識(shí)別一個(gè)串表示的整數(shù)，可以用棧來計(jì)算括號(hào)的嵌套層次，可以用數(shù)學(xué)歸納法證明整數(shù)n的嵌套數(shù)目為n+1。
接著要輸出整數(shù)n的集合表示。用遞歸程序?qū)崿F(xià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}