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 を実行させると恐ろしく時間がかかります。ご注意を(汗)

 以上、如何でしょうか?

広告