Python怎樣實現楊輝三角

# Python怎樣實現楊輝三角

楊輝三角（帕斯卡三角）是二項式系數在三角形中的幾何排列，具有豐富的數學性質和編程實踐價值。本文將介紹三種Python實現方法，并分析其優劣。

## 一、楊輝三角的數學特性

楊輝三角的第n行（從0開始）對應二項式$(a+b)^n$展開的系數，具有以下性質：
1. 每行首位和末位為1
2. 其余每個數等于它上方兩數之和
3. 第n行有n+1個元素

## 二、基礎實現方法

### 方法1：嵌套列表法

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

# 打印前6行
for row in pascal_triangle(6):
    print(row)

優點：直觀易理解，直接體現數學定義
缺點：空間復雜度O(n2)

方法2：生成器實現

def pascal_triangle_gen(n):
    row = [1]
    for _ in range(n):
        yield row
        row = [1] + [row[i] + row[i+1] for i in range(len(row)-1)] + [1]

# 使用示例
for row in pascal_triangle_gen(5):
    print(row)

優點：內存高效，適合大三角計算
缺點：無法隨機訪問特定行

三、進階優化方案

方法3：組合數公式法

利用組合數公式\(C(n,k) = \frac{n!}{k!(n-k)!}\)實現：

from math import comb

def pascal_comb(n):
    return [[comb(i, j) for j in range(i+1)] for i in range(n)]

# 示例輸出
print(pascal_comb(5))

優點：數學表達簡潔
缺點：重復計算階乘，效率較低

優化版本（記憶化）：

from functools import lru_cache

@lru_cache(maxsize=None)
def fact(n):
    return 1 if n < 2 else n * fact(n-1)

def pascal_memo(n):
    return [[fact(i)//(fact(j)*fact(i-j)) for j in range(i+1)] 
            for i in range(n)]

四、格式化輸出技巧

實現美觀的等腰三角形輸出：

def print_pretty(triangle):
    max_width = len(' '.join(map(str, triangle[-1])))
    for row in triangle:
        print(' '.join(map(str, row)).center(max_width))

# 使用示例
print_pretty(pascal_triangle(6))

輸出效果：

       1       
      1 1      
     1 2 1     
    1 3 3 1    
   1 4 6 4 1   
 1 5 10 10 5 1

五、性能對比

六、實際應用場景

1. 概率計算（二項分布）
2. 多項式展開
3. 動態規劃問題
4. 算法教學案例

結語

不同實現方式各有優劣，建議根據實際需求選擇。生成器版本在大多數場景下表現最優，兼顧了內存效率和代碼可讀性。理解楊輝三角的實現有助于培養遞歸思維和動態規劃思想。 “`