Archive for 2014年5月|Monthly archive page
projecteuler15...または、再帰による組み合わせ
projecteuler の 問題15 は、格子の道筋を数える問題。
とは言え、N×Nの正方格子で下と右の二つを半分ずつ選ぶことになるから、その組合せ数を求めるだけなら、以下の計算で十分。
> [cmd] (int (/ (apply * (map bigint (sequence 40 21))) (apply * (map bigint (sequence 20 1))))) [/cmd] 137846528820 >
bigint で大整数にしておくのがみそ(笑)
さて、具体的に道筋を求めるには、下と右をそれぞれ '1' と '0' とすれば、
(define (test n m (bit '()) res)
(let (c (count '(0 1) bit))
(if (= (length bit) (+ n m)) (push bit res -1)
(begin
(when (< (c 0) n) (setq res (test n m (cons 0 bit) res)))
(when (< (c 1) m) (setq res (test n m (cons 1 bit) res)))
))
res))
として、
> (test 2 2) ((1 1 0 0) (1 0 1 0) (0 1 1 0) (1 0 0 1) (0 1 0 1) (0 0 1 1)) > (length (test 2 2)) 6 >
再帰を使っているので 20×20 を実行させると恐ろしく時間がかかります。ご注意を(汗)
以上、如何でしょうか?