Posts pythonTip 106 LTC-男人八题之一:连通图
Post
Cancel

pythonTip 106 LTC-男人八题之一:连通图

题目描述: LTC不知道是谁?百度去!楼天成是也,楼教主当年提出来的男人八题系列,可谓经典中的经典。 言归正传,本题的任务是,请你计算,具有n个节点的无向连通图有多少种不同的形态。n是一个正整数,1 <= n <= 50,请输出结果。 如: n=3时,输出:4 note:n=3,有如下四种不同的无向连通图 A——-B A——-B A B A——-B . . . . . . . . . . . . C C C C 其中,’.’和’-‘画出的线表示无向图的边,A,B,C表示三个顶点。

示例: 输入: n = 1 输出: 1

分析: 首先要搞清楚,这题必然要用高精度,因为随着n的增长无向连通图的数目的增长将比卡特兰数列更加猛烈.我用的方法是先统计出总共能组成多少无向图,再减去其中不联通的个数.设i个点能组成的无向连通图个数为a[i].n个点之间共有C(n,2)条边可连,总图个数为2^C(n,2).假设图不连通,那么节点1必定在某个连通分量中,由于图不连通,所以节点1所在连通分量节点个数可能为i=1~n-1,则剩下的k=n-i个点可以任意连接,所以a[n]=Σ(i=1->n-1){a[i]*2^C(k,2)}.想清楚之后关键问题就在于高精度。但是在python里面对高精度封装的很好,所以这个题对于Python程序员来说,在语法上面不存在什么难题。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
a = [1 for _ in range(51)]
a[3] = 4

def pai(n, m):
    ta = 1
    for i in range(1, m+1):
        ta *= (n-i+1)
        ta /= i
    return int(ta)

for i in range(4, n+1):
    temp = 2 ** (i*(i-1) // 2)
    for j in range(1, i):
        temp -= (a[j] * 2**((i-j) * (i-j-1) // 2)) * pai(i-1, j-1)
    a[i] = temp

print(a[n])
This post is licensed under CC BY 4.0 by the author.
Trending Tags
Contents

pythonTip 105 勇气的挑战

pythonTip 107 LTC-男人八题之二:古老的取石子游戏

Trending Tags