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

第十五問

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

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

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)

Arantium Maestum