串并联网络

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file series_parallel.in Output file series_parallel.out

【题目描述】

在这个问题中,你要计算有两个端点的串并联网络的数量。串并联网络是指电路网络的拓扑或几何属性,也就是说,没有电学功能的电路网络。两个端点中的一个叫源,另一个叫汇。

串并联网络递归定义如下:

(1)一条边是串并联网络。

(2)若G1和G2都是串并联网络,把它们的源和汇分别接在一起也能得到串并联网络。

(3)若G1和G2都是串并联网络,将1的汇和2的源并在一起也能得到串并联网络。

注意在串并联网络中两点之间可以有多条边,而且串联在一起的各个部分可以任意调换顺序,比如下图中的三种网络被看做相同的:

类似地,并联在一起的各个部分也可以任意调换顺序。比如下图中的三种网络也被看做相同的。

输入正整数N,你的任务是统计有多少个n条边的串并联网络。例如,n=4时有10个,如下图:

【输入格式】

输入包含多组数据。

输入文件的每一行都有一个正整数N(1<=N<=30),为给定的边数。

输入文件以一个0结束。

【输出格式】

对于每组数据,输出一行,即包含N条边的串并联网络数目。

【样例输入】

1
4
15
0

【样例输出】

1
10
1399068

【提示】

对于30%的数据,1<=N<=10

对于100%的数据,1<=N<=30

【来源】

UVa10253 Series-Parallel Networks

刘汝佳,《算法竞赛入门经典训练指南》表2.2