Python編寫楊輝三角

楊輝三角是由中國古代數學家楊輝所創造的，它的形式是一個數字三角形，其規律是上一行兩個數字相加等於下一行對應位置的數字。

一、基本思路

Python編寫楊輝三角的基本思路是使用二維數組來存儲數字三角形，然後通過循環依次計算每一層的數字，並將其存儲在數組中。

首先，我們需要定義一個空的二維數組，然後使用for循環依次計算每一層的數字，最後將其存儲在數組中。

def yanghui_triangle(n):
    triangle = [[1]]
    for i in range(1, n):
        row = [1]
        for j in range(1, i):
            row.append(triangle[i-1][j-1] + triangle[i-1][j])
        row.append(1)
        triangle.append(row)
    return triangle

在這個代碼中，我們將二維數組初始化為[[1]]，表示第一層只有一個數字1。

然後，我們使用for循環依次計算從第二層到第n層的數字，其中i表示當前層數。

對於每一層，我們先初始化一個空的列表row，然後使用內部的for循環計算每一個數字，最後將row添加到triangle數組中。

最後，我們將triangle作為函數的返回值，即可得到一個n層的楊輝三角。

二、優化思路

雖然上面的代碼已經能夠正確地生成楊輝三角，但是它的時間複雜度為O(n^2)，當n變大時，程序的執行速度將變得非常慢。

因此，我們需要考慮優化代碼，使其時間複雜度變為O(n)。

一種優化思路是利用楊輝三角的對稱性質，僅需要計算一半的數字，然後將其對稱複製到剩餘的部分。

def yanghui_triangle_optimized(n):
    triangle = [[1]]
    for i in range(1, (n+1)//2):
        row = [1]
        for j in range(1, i):
            row.append(triangle[i-1][j-1] + triangle[i-1][j])
        row.append(1)
        triangle.append(row)
    for i in range(len(triangle)-1, (n-1)//2, -1):
        triangle.append(triangle[i][:i+1][::-1])
    return triangle

在這個代碼中，我們仍然使用二維數組來存儲數字三角形，但是只計算了n的前一半行數（注意，當n為奇數時，需要再多計算一行），然後將其對稱複製到後一半的部分。

具體而言，我們使用兩個for循環，分別計算前一半和後一半的數字，並將其添加到triangle數組中。

最後，我們將triangle作為函數的返回值，即可得到一個n層的楊輝三角。

三、應用場景

楊輝三角在數學中有着廣泛的應用，下面介紹幾個典型的應用場景：

1. 組合數學

楊輝三角在組合數學中有着廣泛的應用，可以通過楊輝三角求得組合數的規律。具體而言，楊輝三角的每一個數字都表示C(n,m)，即從n個元素中取出m個元素的組合數。

2. 等差數列和

楊輝三角可以用來求解等差數列的和。對於一個等差數列a1, a2, a3, …, an，其和可以通過楊輝三角的左下半角和來計算。具體而言，等差數列的和為S = C(n+1,2) * a1 + C(n,2) * (a1 + d) + C(n-1,2) * (a1 + 2d) + … + C(1,2) * (a1 + (n-1)d)，其中d為公差。

3. 概率統計

楊輝三角可以用來計算二項式分佈和正態分佈的概率。對於二項式分佈，可以使用楊輝三角來計算投擲n次硬幣，正好出現k次正面朝上的概率；對於正態分佈，可以使用楊輝三角來計算$x^k * e^(-(x-a)^2/2*b^2)$的積分。