project Euler 015

環境

• javascript

問題

2×2 のマス目の左上からスタートした場合, 引き返しなしで右下にいくルートは 6 つある.

では, 20×20 のマス目ではいくつのルートがあるか.

考え方

1. 最短経路の算出の仕方は、例の場合は、4C2 = (4 * 3) / (2 * 1)
2. 20×20の場合は、40C20

コード

const tate = 20;
const yoko = 20;
let bunbo = 1;
let bunshi = 1;
for (let i = tate + yoko; i > tate; i--) {
  bunbo = bunbo * i;
}
for (let i = tate; i > 0; i--) {
  bunshi = bunshi * i;
}
return Math.floor(bunbo / bunshi);

説明

• 組み合わせの計算をコードで書く

  $$nCr = ( (n + r) * (n + r - 1) * (n + r - 2) * ( ... ) * n ) / ( r * (r - 1) * (r - 2) * ( ... ) * 1 )$$

• 最後に小数点を丸めて計算する