Pythonでパスカルの三角形を生成するプログラム

パスカルの三角形とは

ある整数 n が与えられたとき、n 行分のパスカルの三角形を生成することを考えます。パスカルの三角形は次のような形をしています。

パスカルの三角形の性質

パスカルの三角形には、「前の行で隣り合う2つの数の和が、その真下に配置される数の値になる」という重要な性質があります。

例えば、6行目の最初の「10」は5行目の「4」と「6」の和であり、同じく6行目の2つ目の「10」は5行目の「6」と「4」の和になっています。この性質により、各行を順番に計算していくことで三角形全体を構築できます。

入力と出力の例

入力が n = 5 の場合、出力は以下のようになります。

    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1

アルゴリズムの手順

この問題を解くためには、以下の手順に従います。

• i を 0 から n+1 未満の範囲で繰り返す
  • j を 0 から n-i 未満の範囲で繰り返し、空白を1つずつ出力する（三角形を右に揃えるため）
• 変数 C を 1 で初期化する
• j を 1 から i+1 未満の範囲で繰り返す
  • C の値と空白を出力する
  • C を「C × (i − j) ÷ j」の商で更新する（二項係数の計算式）
• 改行して次の行へ進む

ここで使われる更新式 C = C * (i - j) // j は、二項係数（組み合わせの数）を効率的に計算するための公式です。前の値を利用して次の値を求めることで、毎回階乗を計算する必要がなくなり、処理が高速になります。

Pythonでの実装例

それでは、実際の実装を見てみましょう。

def solve(n):
    for i in range(n+1):
        for j in range(n-i):
            print(' ', end='')

        C = 1
        for j in range(1, i+1):
            print(C, ' ', sep='', end='')
            C = C * (i - j) // j
        print()

n = 5
solve(n)

入力

5

出力

    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1

まとめ

このプログラムでは、外側のループで行を制御し、内側のループで空白による整形と数値の出力を行っています。二項係数の漸化式的な計算を用いることで、シンプルかつ効率的にパスカルの三角形を生成できます。計算量は O(n²) となり、n 行分のすべての要素を一度ずつ計算するだけで済みます。