problem 15 - mtsuyuguの日記

project euler 問題 15 です。
20×20 のマス目を左上から右下まで引き返さずに辿る方法は何通りあるかという問題。ありがちな二項定理を使う数学の問題です。

マス目の交点へたどり着く方法を左上から順番に求めていくという方法で解いてみました。

(use gauche.sequence)
(use gauche.collection)

(define (gen-grid)
  (let1 grid (make-vector 21 0)
        (let loop ((i 0))
          (unless (= i 21)
            (set! (ref grid i) (make-vector 21 (if (= i 0) 1 0)))
            (loop (+ i 1))))
        (for-each (lambda (x) (set! (ref x 0) 1)) grid)
        grid))

(define (grid-at grid i j)
  (ref (ref grid i) j))

(define (grid-at! grid i j n)
  (set! (ref (ref grid i) j) n))

(define (p15 grid)
  (let loop ((i 1)
             (j 1))
    (cond ((= i 21) (grid-at grid 20 20))
          (else (grid-at! grid i j (+ (grid-at grid (- i 1) j)
                                      (grid-at grid i (- j 1))))
                (loop (if (= j 20) (+ i 1) i)
                      (if (= j 20) 1 (+ j 1)))))))

(print (p15 (gen-grid))) ; 137846528820

とここにコピペしてて気づいた。二項定理と書いているのにも関わらず二項定理を使って解いていないじゃないか！

ということで

二項定理というか組み合わせを使って解いてみました。

$_{n}C_{m} = \frac{n\cdot(n-1)\cdots(n-m+1)}{m\cdot(m-1)\cdots\1} = \frac{n-m+1}{m}\cdot_{n}C_{m-1}$

の漸化式を利用して

(define (c n m) ; combination
  (if (= m 0) 1
    (* (/ (- (+ n 1) m) m)
       (c n (- m 1)))))

(print (c 40 20)) ; 137846528820

これで良かった。

わかったこと。

(when cond body...) で cond が真の時だけ body... が評価される。いままでは (if cond (begin body...) #t) とかってやってた。
when の反対は unless
begin なしで書けるときれいな感じがする。