Python でパスカルの三角形を印刷する方法

このチュートリアルでは、Python で指定された行数 のパスカルの三角形 を出力する 方法を説明します。

まずはパスカルの三角形の作り方を学びます。次に、Python 関数の作成に進み、それをさらに最適化する方法を学習します。

▶️始めましょう！

パスカルの三角形とは何ですか?その構築方法は?

指定された行数のパスカルの三角形を出力することは、面接でよくある質問です。

n 行のパスカルの三角形では、行番号 i には i 個の要素があります。

したがって、最初の行には 1 つの要素があり、それは 1 です。後続の行の各要素は、その すぐ上の 2 つの数値の合計です。

次の図は、5 行のパスカルの三角形を作成する方法を説明しています。

特定の数値より 大きい数値が 1 つしか ない場合に、どのようにゼロを埋め込むことができるかに注目してください。

📝簡単な練習として、上記の手順に従って、n = 6 と n = 7 のパスカルの三角形を作成します。

次に、コードを書いてみましょう。チュートリアルを進めながら、 の Python IDE でコード スニペットをブラウザから直接実行することもできます。

パスカルの三角形を出力する Python 関数

このセクションでは、任意の行数のパスカルの三角形を出力する Python 関数を作成してみましょう。

考慮すべき重要な質問が 2 つあります。

• パスカルの三角形の要素をどのように表現するか?
• パスカルの三角形を適切な間隔と書式で印刷するにはどうすればよいですか?

今すぐ答えてみましょう。

#1. パスカルの三角形の各要素の式は何ですか?

たまたま、パスカルの三角形の要素は、 nCr の公式を使用して取得できます。学校の数学を思い出してください。nCr nCr 、 n 個の項目のセットから r 個の項目を選択できる方法の数を示します。

nCr の式は次のとおりです。

ここで、 nCr 公式を使用してパスカルの三角形の要素を表現してみましょう。

これで、行列内のエントリを表現する方法が見つかりました。

#2. パターンを印刷するときに間隔を調整するにはどうすればよいですか?

numRows を含むパスカルの三角形では、行 #1 には 1 つのエントリがあり、行 #2 には 2 つのエントリがあります。パターンを三角形として印刷するには、行 #i に numRows - i 個のスペースが必要です。これを行うには、Python の range 関数を for ループと組み合わせて使用​​できます。

range 関数はデフォルトでエンドポイントを除外するため、必ず + 1 を追加して必要な数の先頭スペースを取得してください。

エントリを表現する方法と、パスカルの三角形を印刷するときにスペースを調整する方法を学習したので、関数 pascal_tri を定義してみましょう。

関数定義の解析

それで、関数 pascal_tri に何をさせたいのでしょうか?

• 関数 pascal_tri は行数 ( numRows ) を引数として受け入れる必要があります。
• パスカルの三角形を numRows で出力する必要があります。

階乗を計算するには、Python の組み込み math モジュールの factorial 関数を使用しましょう。

▶️ 次のコード セルを実行して factorial をインポートし、現在のモジュールで使用します。

 from math import factorial

以下のコード スニペットには関数定義が含まれています。

 def pascal_tri(numRows):
  '''Print Pascal's triangle with numRows.'''
  for i in range(numRows):
    # loop to get leading spaces
	  for j in range(numRows-i+1):
		  print(end=" ")
    
    # loop to get elements of row i
	  for j in range(i+1):
		  # nCr = n!/((n-r)!*r!)
		  print(factorial(i)//(factorial(j)*factorial(i-j)), end=" ")

	 # print each row in a new line
	  print("\n")

この関数は次のように動作します。

• 関数 pascal_tri は、行数を表す必須パラメータ numRows 1 つあります。
• 全部で numRows 行あります。すべての行 i について、行の最初のエントリの前に numRows - i 先頭スペースを追加します。
• 次に、 nCr 式を使用して個々のエントリを計算します。行 i の場合、エントリは iCj ( j = {0,1,2,..,i} です。
• エントリを整数にしたいので、整数の除算を実行する // 使用していることに注目してください。
• 行内のすべてのエントリを計算した後、次の行を新しい行に出力します。

🔗 docstring を追加したため、Python の組み込み help 関数または __doc__ 属性を使用して関数の docstring にアクセスできます。以下のコード スニペットは、その方法を示しています。

 help(pascal_tri)

# Output
Help on function pascal_tri in module __main__:

pascal_tri(numRows)
    Print Pascal's triangle with numRows.

pascal_tri.__doc__

# Output
Print Pascal's triangle with numRows.

それでは、行数を引数として関数を呼び出してみましょう。

 pascal_tri(3)

# Output
     1
    1 1
   1 2 1

予想どおり、パスカルの三角形の最初の 3 行が印刷されます。

再帰を使用してパスカルの三角形を出力する

前のセクションでは、パスカル トライアングルの各エントリの数式を特定しました。ただし、連続する 2 行のエントリ間の関係は利用しませんでした。

実際、前の行を使用して後続の行のエントリを計算しました。これを使用して関数 pascal_tri の 再帰 実装を考え出すことはできないでしょうか?

はい、そうしましょう！

再帰的 実装では、関数は 基本ケースが 満たされるまでそれ自体を繰り返し呼び出します。パスカルの三角形の構築では、1 つのエントリ 1 を持つ最初の行から始めて、後続の行を構築します。

したがって、 pascal_tri(numRows) への関数呼び出しは、基本ケースの pascal_tri(1 pascal_tri(numRows-1) pascal_tri(1) 呼び出します。

パスカルの三角形の最初の 3 行を印刷する必要がある例を考えてみましょう。次の図は、再帰呼び出しがどのようにスタックにプッシュされるかを説明しています。そして、再帰関数呼び出しがどのようにしてパスカルの三角形の行を返すのかを説明します。

▶️ 以下のコード スニペットを実行して、パスカルの三角形の行を再帰的に生成します。

 def pascal_tri(numRows):
    '''Print Pascal's triangle with numRows.'''
    if numRows == 1:
        return [[1]] # base case is reached!
    else:
        res_arr = pascal_tri(numRows-1) # recursive call to pascal_tri
        # use previous row to calculate current row 
        cur_row = [1] # every row starts with 1
        prev_row = res_arr[-1] 
        for i in range(len(prev_row)-1):
            # sum of 2 entries directly above
            cur_row.append(prev_row[i] + prev_row[i+1]) 
        cur_row += [1] # every row ends with 1
        res_arr.append(cur_row)
        return res_arr

注意すべき点がいくつかあります。

• データ構造としてネストされたリストを使用しました。パスカルの三角形の各行 は、 [[row 1], [row 2],…,[row n]] のように、それ自体がリストです。
• 関数呼び出し pascal_tri(numRows) numRows - 1 、 numRows - 2 から 1 までを引数として一連の再帰呼び出しをトリガーします。これらの呼び出しはスタックにプッシュされます。
• numRows == 1 の場合、基本ケースに達し、関数は [[1]] を返します。
• 返されたリストは、コール スタック内の後続の関数によって次の行を計算するために使用されます。
• cur_row が現在の行の場合、 cur_row[i] = prev_row[i] + prev_row[i+1] – 現在のインデックスのすぐ上にある 2 つの要素の合計。

返される配列は入れ子になったリスト (リストのリスト) であるため、以下のコード セルに示すように、間隔を調整してエントリを出力する必要があります。

 tri_array = pascal_tri(5)

for i,row in enumerate(tri_array):
  for j in range(len(tri_array) - i + 1):
    print(end=" ") # leading spaces
  for j in row:
    print(j, end=" ") # print entries
  print("\n")  # print new line

以下に示すように、出力は正しいです。

 # Output

       1

      1 1

     1 2 1

    1 3 3 1

   1 4 6 4 1

numRows ≤ 5 のパスカルの三角形を出力する Python 関数

学習した両方のメソッドは、任意の行数 numRows のパスカルの三角形を出力するために機能します。

ただし、より少ない行数でパスカルの三角形を印刷する必要がある場合があります。印刷する必要がある行数が最大 5 行の場合は、簡単な手法を使用できます。

以下の図を見てください。そして、11 の累乗がパスカルの三角形の要素とどのように一致するかを観察してください。また、これは 11 の 4 乗までしか機能しないことに注意してください。つまり、11 の {0, 1, 2, 3, 4} 乗は、パスカルの三角形の行 1 ～ 5 のエントリを与えます。

以下に示すように、関数定義を書き直してみましょう。

 def pascal_tri(numRows):
  '''Print Pascal's triangle with numRows.'''
  for i in range(numRows):
    print(' '*(numRows-i), end='')
    # compute power of 11
    print(' '.join(str(11**i)))

関数 pascal_tri 仕組みは次のとおりです。

• 前の例と同様に、間隔を調整します。
• 次に、Python のべき乗演算子 (**) を使用して 11 の累乗を計算します。
• 11 の累乗はデフォルトでは整数なので、str() を使用して文字列に変換します。これで、11 の累乗が文字列として得られます。
• Python の文字列は反復可能であるため、文字列をループして一度に 1 文字ずつアクセスできます。
• 次に、構文 <sep>.join(<iterable>) で join() メソッドを使用し、 <sep> 区切り文字として使用して <iterable> 内の要素を結合します。
• ここでは、文字の間に 1 つの スペースが必要なので、 <sep> は ' ' 、 <iterable> は文字列: 11 の累乗になります。

関数が意図したとおりに動作するかどうかを確認してみましょう。

 pascal_tri(5)

# Output
     1
    1 1
   1 2 1
  1 3 3 1
 1 4 6 4 1

別の例として、引数として 4 を指定して関数 pascal_tri を呼び出します。

 pascal_tri(4)

# Output
     1
    1 1
   1 2 1
  1 3 3 1

1 から 5 の範囲の numRows のパスカル トライアングルを簡単に出力する方法を理解できたと思います。

結論

私たちが学んだことは次のとおりです。

• 指定された行数でパスカルの三角形を構築する方法。各行のすべての数値は、そのすぐ上の 2 つの数値の合計です。
• 式 nCr = n!/(nr)!.r! を使用して Python 関数を作成します。パスカルの三角形の要素を計算します。
• 次に、関数の 再帰的実装 について学習しました。
• 最後に、 11 のべき乗 を使用して、最大 5 の numRows に対してパスカルの三角形を構築する最適な方法を学びました。

Python のスキルをレベルアップしたい場合は、行列の乗算、数値が素数かどうかの確認、文字列操作の問題の解決を学びましょう。コーディングを楽しんでください!