楊輝三角
楊輝三角心俗，是二項(xiàng)式系數(shù)在三角形中的一種幾何排列流酬。
（1）每個(gè)數(shù)等于它上方兩數(shù)之和。
（2）每行數(shù)字左右對(duì)稱甘畅，由1開始逐漸變大埂蕊。
（3）最外層的數(shù)字總是1
（4）第二層是自然數(shù)，
（5）下一層數(shù)字之和是上一層的2倍
（6）(a+b)^n的展開式中的各項(xiàng)系數(shù)依次對(duì)應(yīng)楊輝三角的第(n+1)行中的每一項(xiàng)疏唾，這正是定義中二項(xiàng)式系數(shù)蓄氧。如最熟悉的 二項(xiàng)式分解，(a+b)2=a2+2ab+b^2槐脏，它的系數(shù)對(duì)應(yīng)就是楊輝三角的第二層【1,2,1】喉童。
利用第一個(gè)和第二個(gè)特性，我們就很方便地推導(dǎo)出楊輝三角每一行的數(shù)值准给。只要給出初始值泄朴，第一行只有一個(gè)【1】，每一行總是【1】開始露氮，然后根據(jù)每個(gè)數(shù)等于它上方兩數(shù)之和祖灰，便能求解出任何位置的數(shù)值，代碼如下畔规。
def pascal(depth):
"""楊輝三角"""
res = [[1]] # 第一層
for i in range(0, depth):
layer = [1] # 特性3:每一層都是１開始
for j in range(0, len(res[i]) - 1):
# 特性1:每個(gè)數(shù)等于它上方兩數(shù)之和
layer.append(res[i][j] + res[i][j + 1])
layer.append(1) # 特性3:每一層都是1結(jié)尾
res.append(layer) # 把每一層的數(shù)列加到結(jié)果中
return res
def print_pascal(data):
"""輸出楊輝三角"""
for squence in data:
total = 0 #一層數(shù)值求和結(jié)果
for i in squence:
total += i
print(i, end=' ')
print("=%d" % total, end=' ') # end表示輸出結(jié)尾
print()# 默認(rèn)的輸出結(jié)尾是\n,回車另起一行局扶。
用pascal()函數(shù)返回的結(jié)果作為輸入，我們?cè)倏纯磒rint_pascal()函數(shù)處理后的樣子。
print_pascal(pascal(9))
# -----------結(jié)果-------------
1 =1
1 1 =2
1 2 1 =4
1 3 3 1 =8
1 4 6 4 1 =16
1 5 10 10 5 1 =32
1 6 15 20 15 6 1 =64
1 7 21 35 35 21 7 1 =128
1 8 28 56 70 56 28 8 1 =256
1 9 36 84 126 126 84 36 9 1 =512
這樣顯示就一目了然三妈，順帶驗(yàn)證了了它的第五個(gè)特性畜埋，真的是一個(gè)很神奇的規(guī)律，其實(shí)它還有更多有趣的規(guī)律畴蒲，比如我們按照一個(gè)斜度去求和數(shù)列悠鞍，而不是按一層，你會(huì)發(fā)現(xiàn)模燥，竟然會(huì)出現(xiàn)斐波那契數(shù)列的項(xiàng)
楊輝三角和斐波拉契數(shù)列的關(guān)系如下：
F(0) = C(0,0)=1
F(1) = C(1,0)=1
F(2) = C(2,0) + C(1,1)=1+1=2
F(3) = C(3,0) + C(2,1)=1+2=3
F(4) = C(4,0) + C(3,1) + C(2,2)=1+3+1=5
由此推到出F(n)=C(n-m, m)(m<=n-m)
def pascal_to_fibonacci(data):
result = []
for n in range(len(data)):
fib = [] # 初始化每一層的數(shù)列咖祭，為空
m = 0
while n - m >= m:
# 根據(jù)定義，楊輝三角和斐波拉契數(shù)列的轉(zhuǎn)化下標(biāo)關(guān)系
fib.append(data[n-m][m])
m += 1
result.append(fib)
print_pascal(result) # 借用楊輝三角輸出函數(shù)輸出每一層的和
測(cè)試一下當(dāng)n=6的時(shí)候蔫骂，結(jié)果如何么翰。
pascal_to_fibonacci(pascal(6))
# -----------結(jié)果-------------
1 =1
1 =1
1 1 =2
1 2 =3
1 3 1 =5
1 4 3 =8
1 5 6 1 =13
想更多了解Python，可以購(gòu)買我寫的書 《數(shù)據(jù)結(jié)構(gòu)和算法基礎(chǔ)Python語(yǔ)言實(shí)現(xiàn)》
