E:/GitHub/suanfaquti/Q22不缠绕的纸杯电话.py

---

'''
问题描述(有修改)
正n边形(n是偶数)，把所有点用n/2条线连接，每个点都被连接，要求这些线不相交。
求当n=16时有多少连接方式
分析
设f(n)表示n个点的连法的总数。给16个点编号0到15，那么0只能连接奇数序号，
共8种连法，每一种连法的种数，就等于f(a)*f(b)，a,b分别两侧的点数(都是偶数)。
'''

n=16
res=[0]*(n+1)
res[0]=1
res[2]=1
#res[4]=2
for m in range(4,n+1,2):
    count=0
    for i in range(int(m/2)):
        count+=res[i*2]*res[m-2-i*2]
    res[m]=count

print(res)              #1430