目次
TypeScriptでパスカルの三角形を実装してみます。
パスカルの三角形とは?
Wikipedia には次のように説明がある。
パスカルの三角形(パスカルのさんかくけい、英: Pascal's triangle)は、二項展開における係数を三角形状に並べたものである。
これだけではよく分からないので、以下に図を示します。
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
パスカルの三角形は、次のルールで構成されています。
- 最上段(0行目)は
1
のみです - 各行の端は常に
1
です - それ以外の数字は、上の行の隣り合う2つの数字の和になります
パスカルの三角形と二項係数
パスカルの三角形の数字は、二項係数 を並べたものとしても解釈できます。
二項係数は や と表記され、以下の式で計算されます。
パスカルの三角形を二項係数の形で表現すると、次のようになります。
0C0
1C0 1C1
2C0 2C1 2C2
3C0 3C1 3C2 3C3
4C0 4C1 4C2 4C3 4C4
5C0 5C1 5C2 5C3 5C4 5C5
6C0 6C1 6C2 6C3 6C4 6C5 6C6
TypeScriptでの実装
それでは、TypeScript
でパスカルの三角形を実装してみましょう。
ts
/**
* 二項係数(nCr)を計算する関数
* @param n 全体の数
* @param r 選ぶ数
* @returns 組み合わせの数
*/
const combination = (n: number, r: number): number => {
if (r === 0 || r === n) return 1;
if (r > n) return 0;
let result = 1;
for (let i = 1; i <= r; i++) {
result *= n - i + 1;
result /= i;
}
return result;
};
/**
* パスカルの三角形の1行を出力する関数
* @param row 出力する行番号(0から始まる)
*/
const logPascalRow = (row: number): void => {
let line = '';
for (let r = 0; r <= row; r++) {
const value = combination(row, r);
line += value + ' ';
}
console.log(line);
};
// パスカルの三角形を出力
const N = 7;
console.log('出力:');
for (let i = 0; i < N; i++) {
logPascalRow(i);
}
/* 出力:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
*/