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

Arantium Maestum

プログラミング、囲碁、読書の話題

Clojure入門 - Project Eulerを解いてみる 問15

第十五問

20x20の格子の左上から右下まで、右か下に進み続けて到達する道筋の総数を求める。

これはプログラミングというより数学の問題。必ず右に20、下に20動くので、40ある「移動」の中から20を「右」として選ぶ、ということになる。単なる二項係数。

nCr = n! / ((n-r)! * r!)

ただ、これを正直にコードに落とし込むと40!でoverflowに引っかかる。40!/20!が(reduce * (range 21 41))であることを利用する。

(defn ncr [n r]
  (/ (reduce *' (map inc (range r n))) 
     (reduce *' (map inc (range r)))))

それを踏まえてnCr関数。答えは単に:

(ncr 40 20)