久しぶりにSICPとか開いたり

リハビリに某所の基本問題を解く。流石に基本なんでさくさく進むが、整数の分割数を求める問題の反復プロセス化を考えて詰まった。*1
何かSICPで似たような問題を見た気がしたんで引っぱり出して探してみると、P22のcount-changeが近かった。テーブル化とかメモ化とかしろと書いてあるな…。ちょっと考えて思い付かなかったんで、手抜きで適当にぐぐってみたらあった。

• http://www.sampou.org/scheme/sicp/mailingList/msg00327.html

数と同じ長さのリストを用意して、リストの長さと同じ金額の場合の、組み合わせの数がそこの値みたいな。それを硬貨1つずつ計算していくんか。うへ。一応反復プロセス化としてはボトムアップの手法なんかな。

で、上のを元にした分割数を求める関数。

(define (partition n)
  (define (genlist n)
    (if (= n 0)
        (list 1)
        (cons 0 (genlist (- n 1)))))
  (define (cc c l)
    (define (cc-iter l)
      (define (sumup l)
        (if (<= (length l) c)
            (car l)
            (+ (car l) (sumup (list-tail l c)))))
      (if (null? l)
          '()
          (cons (sumup l) (cc-iter (cdr l)))))
    (cc-iter l))
  (let loop ((i 1)
                  (ls (genlist n)))
         (if (> i n)
             (car ls)
             (loop (+ i 1) (cc i ls)) )) )

うーん、速いなぁ。(partition 200)とかでも平気で出てくる。

ちなみに普通に考えたpartition。死ぬ程遅い。

(define (partition n)
  (letrec ((p (lambda (x y)
                (cond ((< x y) 0)
                      ((= x y) 1)
                      (else (+ (p (- x y) y)
                               (p x (+ y 1)))) )) ))
    (p n 1)) )

*1:ちなみに反復プロセス化をやれ、という問題ではない。勝手に考えてるだけ。