黄昏より暗きもの、血の流れより赤きもの

読者です 読者をやめる 読者になる 読者になる

黄昏より暗きもの、血の流れより赤きもの

自分の好きな事を好きなように書いて行きます。

【アルゴリズム】Project Euler Problem 15 解答:動的計画法を用いて40C20の値を求めてみた

数学の問題をプログラムを使って解くサイト「Project Euler」。今回はその問題15とその解説をしたい。数学やProject Eulerアルゴリズムに興味のある方は是非読んで欲しい。

Problem 15

Lattice paths Problem 15

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down,there are exactly 6 routes to the bottom right corner.


f:id:program_study:20150508234322g:plain

How many such routes are there through a 20×20 grid?

さて、本問題を日本語化すると「20*20の格子状の道を最短で通る方法は何通りか?」となる。話し好きの自分なので、様々な雑談を交えつつ本問題を解説したい。

大学時代の回想

本問題は中学入試を受験するような小学生でも理解できる問題だ。回想するに筆者がまだ大学生でSAPIXの模擬試験監督をしていた頃、小学生が図に以下のように書き込んで答えを出していた。


f:id:program_study:20150508234352p:plain

ここで生徒が途中からかけ算するのを間違う様子を見るに、「これ、(和の法則)で足し合わせれば良いと覚え込んでない?」と疑問に思った事がある。文章題でもある問題では○と×をxとyに見立てて二元一次連立方程式を組むと思いきや、違う問題だと算数。

いやいっその事全部二元一次連立方程式で解いてしまえばと思ってしまった。どうも問題の答えとパターンを覚えさせる方針な訳ね。パターンを覚えきれない生徒さんには辛い教育方針だと思いながら見ていた。

解答1:ExcelのCOMBIN関数を使う

さてどんな秀才でも、仮に入試の現場でこのProject Eulerの問題を見たら絶句するだろう。流石に足し算はし続けられなくなり、捨て問と察して他の問題に行く事を考えるはずだ。この波紋は小学生だけにと どまらない。高校入試ないしは数学好きな中学生以上の方なら、以下のように解くだろう。

解答

格子状の道を縦20回横20回計40回動く。この内何回目に右に移動するかの組み合わせを考える。この計算をExcelにやらせて、

\binom{40}{20} = COMBIN(40,20) = 137,846,528,820(通り)

さて、これを手計算でやろうとすると、


\frac{40*39*38*37*36*35*34*33*32*31*30*29*28*27*26*25*24*23*22*21*20}{20*19*18*17*16*15*14*13*12*11*10*9*8*7*6*5*4*3*2*1}

と約分の大変な有様を垣間みれる。しかも23や29は素数なので、約分して数を丸める事ができやしない。しかしnCrは整数であるため、最終的に分母が全て消え失せるはずだ!こんなわけで消えろ分母消えろ分母と計算が進めてみたが、途中でやる気が失せたのは言うまでもない。

解答2:動的計画法よりnCkを求める

解答2は「二項係数を求める関数の作り方 (Ruby編):tsujimotterのノートブック」のやり方を真似た物だ。

やり方は\binom{n}{k} = \frac{n}{k} *\binom{n-1}{k-1}再帰的に呼び出し、最終的にnCkの値を求めようと言うもの。この際途中まで計算した二項係数を一旦配列に格納し、計算量の削減を行っている。こうした手法を一般的に動的計画法(Dynamic Programming)*1と呼ぶ。この動的計画法を用いて書いたC言語は以下のようになり、無事に数値計算されている。

余談として、実装の最中に(n/k)と括弧で括ったら小数となるため、0と言う結果が返ってきた。nCkは整数であるため、前から計算させれば良かったと後悔している。計算結果は小数なのか整数なのかは意識しておかねばと思った限りだ。

ソースコード

実行結果

time ./a.out
137846528820
real 0m0.022s
user 0m0.001s
sys 0m0.002s

おまけ

最後に本問題の類題を紹介したい。それは、日本数学オリンピック予選で出題された、

\binom{40}{20} を41で割った余りをもとめよ

という問題。1から計算するか?何か違う方法を考えるか?を現場で考えないと行けないのが難しかった。試験会場では30分位かかる問題でも、C言語だと一瞬で余り1と計算してくれる。

この問題はパスカルの三角形に関連があり、「40C20を41で割った余り:ゆとり日記」が詳しく解説しているので紹介したい。