Subscribed unsubscribe Subscribe Subscribe

SE Can't Code

A Tokyo based Software Engineer. Not System Engineer :(

両替の話.

本当にこれ動くのかと思いつつ動かしてみたら動いた。SICP再帰手続きを使った両替の話。
50セント、25セント、10セント、5セント、1セントがあるとして、1ドルの両替にはどのくらいの場合があるか、という問い。再帰的手続きを用いて、下記のようなベースモデルを組み込む。

  • aがちょうど0なら、両替の場合の数は1
  • aが0より少なければ、両替の場合の数は0
  • nが0なら、両替の場合の数は0

これにより、ある金額の両替の問題を、少ない種類の効果を使う少ない金額の問題へ再帰的に縮小させることが可能になる。

(define  (count-charge amount)
  (cc amount 5))

(define (cc amount kind-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kind-of-coins 0)) 0)
        (else (+ (cc amount (- kind-of-coins 1))
                 (cc (- amount (first-denomination kind-of-coins))
                     kind-of-coins)
                 ))))

(define (first-denomination kind-of-coins)
  (cond ((= kind-of-coins 1) 1)
        ((= kind-of-coins 2) 5)
        ((= kind-of-coins 3) 10)
        ((= kind-of-coins 4) 25)
        ((= kind-of-coins 5) 50)))


1ドルの両替という問いにきちんと答えている。

(count-change 100)
292

count-chargeは冗長な木構造再帰的プロセスを生成しているのがわかる。一般に木構造再帰的プロセスで必要なステップ数は木構造の節の数に比例し、必要なスペースは木構造の最大深さに比例する。木構造再帰的プロセスは計算上非常に非効率だが、規定し理解するのにを手助けする。要は非常にわかりやすい。たとえば代表例としてよく使われるFibonacci数列だとわかりやすいのだが、与えられた数のnの-1と-2を再帰的に木構造で計算すると、自分自身の手続きを二回呼び出してしまうなんてことがある。

コンピュータサイエンスの基礎からやり直しているが、たとえば再帰的プロセスと反復的プロセスで、保持する情報量が線形に伸びるか否かといったところを改めて学ぶこととハッとすることが多い。再帰って理屈はわかるんだけど、実際に演算上で何が起こっているかがイマイチ掴めなかったりしたので、反復と比較することで基本的なイメージを再確認している感じ。ここ1年くらい応用せずにひたすら書籍で勉強しながら基礎練ばかりしている気がしないでもないが、きっと将来で役に立つだろうと信じてる。

Remove all ads