2005/09/13

SICP-第1章の両替問題の効率化(末尾再帰化)に悩んでいたら昼休みが終わってしまった。どうでもいいけど、こういう徒労を繰り返しているうちに人生が短くなっていくからちゅういしろ。あと、これから書くのは答えじゃないからちゅういしろ。

まず、変数と関数をいくつか用意する。
  • a:総額
  • k:コインの種類
  • d:コインの種類に応じて金額を返す関数
  • f:両替問題を解く関数

SICPでの考え方は、次のとおり。
f ( a , d ( k )) = f ( a - d ( k ), d ( k )) + f ( a , d ( k - 1))

これを式変形していくと、次を得る。
f ( a , d ( k )) = ∑_i=0→k-1 { f ( a - d ( k - i ), d ( k - i ))} + f ( a , d ( 0 ))

最後の項は定義により 0 だから、結局 f についての項和が得られる。この和をダイレクトにSchemeで書くと、次のようになる。

(define (d k)
(cond ((= k 1) 1)
((= k 2) 5)
((= k 3) 10)
((= k 4) 25)
((= k 5) 50)))

(define (sum-cc cc a k)
(cond ((< a 0) 0)
((or (= a 1) (= k 1)) 1)
(else (+ (cc (- a (d k)) k)
(sum-cc cc a (- k 1))))))

(define (cc a k)
(sum-cc cc a k))

(define (count-change a)
(cc a 5))

これは結局SICPの例と等価だよな。sum-ccだけ見れば普通の総和計算のコードなので、頭を捻って継続引き渡しスタイルで書くとかすれば、「見た目」は末尾再帰にできそうな木がする。それに、もうちょっとSICPを真面目に読み進めれば、∑を末尾再帰で書くヒントが書いてありそうな木がする。でも、評価の順番を書き下していけば結局SICPの例と同じ木になるわけで、そんなんじゃちっともうれしくないね。このあたりでいつもつまずく。SICPの第1章で主張しているのは、計算プロセスをrecursiveからiterativeにすれば計算機コストの面ではうれしい、って話だと思うんだけど、それってアルゴリズム(っていうか問題の解法)の話じゃないんだよねきっと。かといってプロシージャの表現の話でもないし。
ところでiterativeの訳語って逐次的?

1 comment :

Anonymous said...

「効率化」になるのかなあ?
(cf.) Scheme:末尾再帰で木をトラバース