Problem 15 - マス目のルート
プロジェクトオイラーにハマってます。ステキな問題が多くてイイ!!
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
一瞬で解けました。階乗より早いと思う。