プロジェクトオイラー15.

この記事の所要時間: 145

No.15 Lattice Paths

問題.

2\times 2 の格子の左上の角から始めて, 右か下への移動のみ可能であるとき, 右下の角へ移動する道は 6 通りある.

では, 20\times 20 の格子では何通りあるか求めよ.

考え方とプログラム例(Python3).

N\times Nの格子において左上から右下まで, 右または下への移動のみで行く方法は,

\begin{align*} {}_{2N}C_{N} &= \dfrac{(4N)!}{(2N)!(2N)!}\\ &= \dfrac{4N\cdot(4N-1)\cdots (2N+1)}{2N\cdot (2N-1)\cdots 1} \end{align*}

なので, これを計算すればいいだけなのですが, 分母と分子をそれぞれ計算して割り算しようとすると, N=20 だと分母, 分子がそれぞれ大きくなりすぎてしまい, うまく計算できません.

そこで, 次の式を使います.

\begin{align*} {}_nC_k &= {}_nC_{k-1}\cdot \dfrac{n-k+1}{k} \end{align*}

この式を使って,

\begin{align*} {}_{40}C_0, {}_{40}C_1, \ldots, {}_{40}C_{20} \end{align*}

の順に求めていきます.

この方法を使えば, N が20 よりももっと大きい数でも2項係数を計算できます.

答えはこの下にあります. 反転してください.

A. 137846528820

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加