Project Euler Problem 15

問題15: 20x20のマトリクスにおいて左上端から右下端へ格子を通って到達する経路は何通りあるか。ただし、左から右、上から下へしか移動できないものとする。[=>問題文]

図を描いてみる

　簡単な図を書くだけですぐに仕組みが分かります。

　右から左、下から上へは戻れないため上辺に位置する格子点は常に左からの１通りしか到達手段がありません。同様に左辺の点もみんな１。内部の点に関しては到達経路が上からと左から２通りになります。したがってある点への到達経路の数は、その上の点への経路数と左の点への経路数の和で求められます。いくつかの格子点に経路の数を記入していくと、これは「パスカルの三角形」と同じことをやってることに気づきます。図は左に45度傾いたパスカルの三角形そのものです。
　ゴールは対角線上にあるので割り当てられる値は、三角形の行の要素数が奇数となる段の中央の値となります。つまりこの問題は次のように読みかえることが出来ます。
　パスカルの三角形の 2n 段目の中央の値を答えよ（ただし三角形の頂点は 0段目とする）

問題15の解答

(defun problem015 (N)
  (let ((prev '(1.0))
        (next nil)
        (i 0))
    (dotimes (i (* 2 N))
      (setq next '(1.0))
      (while (< 1 (length prev))
        (push (+ (pop prev) (car prev)) next))
      (setq prev (cons 1.0 next)))
    (nth (/ (length prev) 2) prev)))

(problem015 20)

　これまた 28bitでは収まらないので float を使っています。