Problem 15 - マス目のルート

プロジェクトオイラーにハマってます。ステキな問題が多くてイイ!!

Problem 15 - PukiWiki

2 × 2 のマス目の左上からスタートした場合、引き返しなしで右下にいくルートは 6 つある。
では、20 × 20 のマス目ではいくつのルートがあるか。

これは見たことがある問題が来た。


パスカルの三角形使えば、簡単じゃないか。と思ってコピッペしてみたら。

(define (problem15 n)
  (define (pascal a b)
    (if (or (= a 0) (= b 0) (= a b))
        1
        (+ (pascal (- a 1) (- b 1))
           (pascal (- a 1) b))))
  (pascal (* n 2) n))

(problem15 20) ; 終わらず。

ガーン。終わらず。


ということで、二項定理の漸化式を。

(define (problem15 n)
  (define (combi n r)
    (if (= r 0)
        1
        (* (/ (+ (- n r) 1) r)
           (combi n (- r 1)))))
  (combi (* n 2) n))

(problem15 20) ; 137846528820

一瞬で解けました。階乗より早いと思う。