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