Pascal's Triangle
パスカルの三角形では、最初の行は [1] です。それ以降の各行は要素が1つ多く、1で始まり1で終わります。その間の各要素は、真上にある2つの要素の和です。整数 numRows が与えられます。三角形の最初の numRows 行を、最上段から順に、各行を整数の配列として返してください。
関数
- numRowsinteger
- 三角形を作る行数
- 戻り値integer-2d-array
- 最初のnumRows行（最上段から）
制約
1 ≤ numRows ≤ 30- 最初の30行の各項目は、32ビット符号付き整数に収まります。最大値は77558760で、30行目の中央にあります。
例
- 入力
- numRows = 5
- 出力
- [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
- 説明
- 各内側の要素は、その上にある2つの要素を足したものです。4行目: 3 = 1 + 2 and 3 = 2 + 1。5行目: 4 = 1 + 3, 6 = 3 + 3, 4 = 3 + 1。
- 入力
- numRows = 1
- 出力
- [[1]]
- 説明
- 1 行の場合、三角形は頂点だけで、
[1]です。
発展問題
配列を1つだけ使い、行ごとにその場で更新できますか？内側のループはどちら向きに実行する必要がありますか？その理由は何ですか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
行 0 は
[1]、行 1 は[1, 1]です。行rの長さはいくつで、最初と最後の要素は何ですか？各内側の要素には、真上の行からの値が2つあれば十分です。行を順番に作成すれば、その行は必要になる前に必ず完成しています。
新しい行はすべて 1 として始めます。次に、各内側の位置
cについて、前の行の位置c-1とcを足します。その行を追加して次に進みます。
解説
各要素は、その1つ上の行にある2つの要素の和です。各要素について毎回最初からこの規則を評価すると、同じ値を再計算することになり、行が1つ増えるごとに作業量は2倍になります。返す各行は、より小さな問題に対する答えを保存したものなので、三角形は上から下へ、直前の行をもとに各行を作っていきます。
すべての要素を再帰的に計算する
正しいが、最大のテストでは終わらない
考え方
行番号と位置は0から数えます。定義は関数になります。entry(row, col)は端では1で、colが0またはrowの場合がこれに当たり、それ以外ではentry(row-1, col-1) + entry(row-1, col)です。これは定義そのものなので正しいです。
再帰は端でのみ停止し、そこでは1を返すため、値がvの要素を計算するには約2v回の呼び出しが必要です。行rの値の合計は最大で2^rになるため、30行では約2^31回の呼び出しが必要となり、20億回を超えます。
アルゴリズム
entry(row, col)を書きます。colが 0、またはcolがrowと等しい場合は 1 を返します。- それ以外の場合は、
entry(row-1, col-1) + entry(row-1, col)を返します。 - 0 から
numRows-1までの各rowについて、0 からrowまでの各colに対するentry(row, col)を集めます。 - 行のリストを返します。
def pascalEntry(row, col):
if col == 0 or col == row:
return 1 # the edges of the triangle
return pascalEntry(row - 1, col - 1) + pascalEntry(row - 1, col)
def generate(numRows):
triangle = []
for row in range(numRows):
triangle.append([pascalEntry(row, col) for col in range(row + 1)])
return triangle各行をその上の行から作成します
考え方
再帰では前の行の要素を求めようとしますが、その行は結局作ることになります。そこで、行を上から下へ計算し、行 r を埋めるときには、すでに計算済みの行 r-1 を読み取ります。各要素の計算に必要なのは加算1回だけです。小さい問題の答えを並べた表そのものが、出力になります。
各行を r + 1 個の1で初期化すれば、両端も設定されます。そのため、内側の位置がない行0と行1も、特別扱いする必要はありません。三角形の要素数は 1 + 2 + ... + n、つまり約 n²/2 個なので、出力以外のメモリを使わずに処理できます。計算量は O(n²) です。30行なら、20億回の呼び出しではなく465個の要素を計算します。
アルゴリズム
- 空の行リストから始めます。
rowを 0 からnumRows-1まで順に処理し、row + 1個の 1 を作成します。colを 1 からrow-1まで順に処理し、前の行のcol-1とcolの位置の値の合計を設定します。- その行を追加して続けます。リストを返します。
def generate(numRows):
triangle = [[1]]
for row in range(1, numRows):
above = triangle[-1]
values = [1] * (row + 1) # both edges are 1
for col in range(1, row):
values[col] = above[col - 1] + above[col]
triangle.append(values)
return triangle
落とし穴と境界ケース
numRows + 1行を返す。番号は 0 から始まるため、必要な最後の行はnumRows-1。- 内側のループを辺まで実行する。位置 0 には左の親がなく、位置
rowには右の親がないため、それらを読み取ると範囲外アクセスになる。 - 小さい行で問題が起きる範囲。Swift の
1..<rowはrowが 0 のときクラッシュし、R の2:(row-1)はrowが 2 のとき 1 までカウントダウンする。 - 階乗を使って要素を計算する。
C(29, 14)は int に収まるが、29!は 64 ビット整数でもオーバーフローする。 - 各行に同じ配列を追加してから変更する。結果のすべての行が最後の行になる。
よくある質問3
パスカルの三角形を生成する時間計算量はどれくらいですか？
n 行の場合は O(n²) です。三角形には約 n²/2 個の要素があり、それぞれに加算が 1 回必要です。出力のすべての要素を書き出す必要があるため、これは最適です。出力以外に必要な追加領域は O(1) です。
パスカルの三角形は二項係数とどのように関係していますか？
0から数えて、行 r の k 番目の項は C(r, k) であり、これは r 個の項目から k 個を選ぶ方法の数です。和の規則は恒等式 C(r, k) = C(r-1, k-1) + C(r-1, k) で表され、行 r の合計は 2^r になります。これは r 個の項目の部分集合の数です。
その上の行を作らずに、1 行を計算できますか？
はい。1から始め、前の項から次の各項を求めます: C(r, k) = C(r, k-1) × (r-k+1) / k。割り算が正確になるよう、割る前に掛け算を行い、積には64ビット整数を使います。すると行 r の計算には O(r) 時間かかります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def generate(numRows):
# ここにコードを書いてくださいテスト #1
テスト #2
引数
numRows = 5
期待される出力
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]