RubyでProject Euler - Problem 31 : PamGau

Problem 31 (Project Euler) [原文]

イギリスでは硬貨はポンドとペンスがあり，一般的な流通ではこれらの8つの硬貨がある．

1p, 2p, 5p, 10p, 20p, 50p, 1ポンド (100p) and 2ポンド (200p).

以下の方法で2ポンドを作ることが可能である．

1×1ポンド + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

いくらかの硬貨を使って2ポンドを作る方法はいくつあるでしょうか?

頻出問題と云えるのですが、ちからまかせにコーディングすると苦労します。さらに効率が低くて答えが出るまでに実行時間がえらくかかってしまいます。

私などはうろ覚えだった記憶を掘り起こそうともせず、最初、再帰呼び出しを使ったかなり遅いプログラムでなんとか正解にたどり着きました。さすがにこれではあまりにもまずいので、エレガントなPerlによる解答が書かれた下記のブログ記事を参考にさせていただきました。動作を確認しつつ、Rubyに書き写してみました。Thanks !

Project Euler Problem 31 Solution (Dreamshire)

  LIMIT = 200
  coins = [1,2,5,10,20,50,100,200]
  ways = Array.new(LIMIT+1, 0)
  ways[0] = 1

  coins.each do |c|
    (c..LIMIT).each do |s|
      ways[s] += ways[s-c]
    end
  end

  p ways[LIMIT]

上のコード中、"ways"という配列には、各要素のインデクッスに対応する支払い方法の数が格納されることになります。LIMITを小さくしたり、コインの種類を減らしたりしながら、"ways"の変遷を確認すると興味深いです。

結局、私が関数の再帰呼び出しに相当することを、配列(メモリセグメント)でやっているのだと理解しました。