- Python语言: 计算n*n网格生成树的数目
- from math import cos
- """
- [1] <a href="http://en.wikipedia.org/wiki/Kirchhoff">http://en.wikipedia.org/wiki/Kirchhoff's_theorem
- [2] <a href="http://www.research.att.com/">http://www.research.att.com/~njas/sequences/A007341
- [3] Direct Methods for Computing Eigenvalues of the Finite-Difference Laplacian
- J. R. Kuttler
- SIAM Journal on Numerical Analysis, Vol. 11, No. 4 (Sep., 1974),
- pp. 732-740
- """
- def eigenvalues_of_laplacian(n):
- ew = [2*(2-cos(i*pi/n)-cos(j*pi/n)) for i in range(n) for j in range(n)]
- return ew
- def num_of_spanning_trees(n):
- ew = eigenvalues_of_laplacian(n)
- return reduce(lambda x,y:x*y, ew[1:])/n**2
- #该片段来自于http://www.codesnippet.cn/detail/290120131982.html
来源: http://www.codesnippet.cn/detail/290120131982.html