小练习-杨辉三角Python实现

杨辉三角

杨辉三角，是二项式系数在三角形中的一种几何排列。

（1）每个数等于它上方两数之和。
（2）每行数字左右对称，由1开始逐渐变大。
（3）最外层的数字总是1
（4）第二层是自然数，
（5）下一层数字之和是上一层的2倍
（6）(a+b)^n的展开式中的各项系数依次对应杨辉三角的第(n+1)行中的每一项，这正是定义中二项式系数。如最熟悉的 二项式分解，(a+b)^2=a2+2ab+b^2，它的系数对应就是杨辉三角的第二层【1,2,1】。

利用第一个和第二个特性，我们就很方便地推导出杨辉三角每一行的数值。只要给出初始值，第一行只有一个【1】，每一行总是【1】开始，然后根据每个数等于它上方两数之和，便能求解出任何位置的数值，代码如下。

def pascal(depth):
    """杨辉三角"""
    res = [[1]] # 第一层
    for i in range(0, depth):
        layer = [1] # 特性3:每一层都是１开始
        for j in range(0, len(res[i]) - 1):
            # 特性1:每个数等于它上方两数之和
            layer.append(res[i][j] + res[i][j + 1]) 
        layer.append(1) # 特性3:每一层都是1结尾
        res.append(layer) # 把每一层的数列加到结果中
    return res

def print_pascal(data):
    """输出杨辉三角"""
    for squence in data:
        total = 0 #一层数值求和结果
        for i in squence:
            total += i
            print(i, end=' ')
        print("=%d" % total, end=' ') # end表示输出结尾
        print()# 默认的输出结尾是\n,回车另起一行。

用pascal()函数返回的结果作为输入，我们再看看print_pascal()函数处理后的样子。

print_pascal(pascal(9))
# -----------结果-------------
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 

这样显示就一目了然，顺带验证了了它的第五个特性，真的是一个很神奇的规律，其实它还有更多有趣的规律，比如我们按照一个斜度去求和数列，而不是按一层，你会发现，竟然会出现斐波那契数列的项

image.png

杨辉三角和斐波拉契数列的关系如下：
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 = [] # 初始化每一层的数列，为空
        m = 0
        while n - m >= m:
            # 根据定义，杨辉三角和斐波拉契数列的转化下标关系
            fib.append(data[n-m][m])
            m += 1
        result.append(fib)
    print_pascal(result) # 借用杨辉三角输出函数输出每一层的和

测试一下当n=6的时候，结果如何。

pascal_to_fibonacci(pascal(6))
# -----------结果-------------
1 =1 
1 =1 
1 1 =2 
1 2 =3 
1 3 1 =5 
1 4 3 =8 
1 5 6 1 =13