change.rb(両替プログラム)

Sussman(サスマン)の「計算機プログラムの構造と解釈」Structure and Interpretation of Computer Programの最初の方にCounting Changeという1ドルをコインにする場合の場合の数を求める話があります。アメリカのコインは多くてhalf-dollars, quarters, dimes, nickels, and penniesの5種類で、先に答えを書くと292通り。日本の100円は1円、5円、10円、50円でちっと違う。再帰で書かれていて、どれか一枚について使わない場合（残りの4種類で構成する場合の場合の数)と使ってその金額を引いて相変わらず5種類で構成する場合の数の合計という、え、それで解けるの？　というような再帰ですが解けてしまう。

(define (count-change amount)
  (cc amount 5))
(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                     (- kinds-of-coins 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
                     kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))

(count-change 100)
292

これをこのままRubyで書く(翻訳する)と、以下のようになるかと思います。

# change.rb

def count_change(amount)
  cc(amount, 5)
end

def cc(amount, kinds)
  if (amount == 0)
    return 1
  elsif ((amount < 0) || (kinds == 0))
    return 0
  else
    return (cc(amount, (kinds - 1)) +
            cc((amount - first_denom(kinds)), kinds))
  end
end

def first_denom(kinds)
  case kinds
  when 1; return 1
  when 2; return 5
  when 3; return 10
  when 4; return 25
  when 5; return 50
  end
end

p count_change(100) #=> 292

さて、Schemeの方もRubyの方も硬貨(コイン)の種類が固定されていて、番号までふられていてどうも面白くない。その分わかりにくくなっているし。というわけで、Arrayで書き直すと以下のようになると思います。

# change.rb

kinds = [1, 5, 10, 25, 50]

def count_change(amount, kinds)
  temp_kinds = kinds.dup
  if (amount == 0)
    return 1
  elsif ((amount < 0) || (temp_kinds == []))
    return 0
  else
    result = 
      count_change(amount, temp_kinds[0..-2]) + 
      count_change((amount - temp_kinds[-1].to_i), temp_kinds)
    return result
  end
end

p count_change(100, kinds) #=> 292

で、何がうれしいかというと、kindsというコインの種類を入れた配列をいじれば、日本のコインでも紙幣でもいろいろ応用できる。