1

私が解決しようとしている問題は次のとおりです。

n ドルが与えられた場合、無制限のペニー、ニッケル、ダイム、クォーターがあり、n を表す方法の総数を計算します。

私は再帰的な解決策を思いつきました（nが0.25ドルであると仮定して、出力はばかげた数値ではありません）：

def changes(w, x, y, z)
  if 0.01 * w + 0.05 * x + 0.1 * y + 0.25 * z > 0.25
    return
  elsif 0.01 * w + 0.05 * x + 0.1 * y + 0.25 * z == 0.25
    @@counter += 1
    puts "w: #{w} x: #{x} y: #{y} z: #{z}"
  else
    changes(w + 1, x, y, z)
    changes(w, x + 1, y, z)
    changes(w, x, y + 1, z)
    changes(w, x, y, z + 1)
  end
end

@@counter = 0
changes(0, 0, 0, 0)
puts @@counter

基本的に、ここでの考え方は、一致した場合にカウンターをインクリメントし、そうでない場合は次の可能な金種を試すことです。

しかし、出力には次のような繰り返しがたくさんあります。

w: 15 x: 0 y: 1 z: 0
w: 15 x: 0 y: 1 z: 0
w: 15 x: 0 y: 1 z: 0
w: 15 x: 0 y: 1 z: 0
w: 15 x: 0 y: 1 z: 0
w: 10 x: 1 y: 1 z: 0
w: 15 x: 0 y: 1 z: 0
w: 10 x: 1 y: 1 z: 0

誰かが理由を教えてもらえますか? 私の再帰では、常に異なる値のパラメーターを渡しませんか? 同じ値が複数回出力されるのはなぜですか?

ありがとうございました。

4

2 に答える 2

1

重複を取得する方法の例

との最初の通話でchanges(0, 0, 0, 0)。
失敗して次のように呼び出されます。

changes(1, 0, 0, 0) # a
changes(0, 1, 0, 0) # b
changes(0, 0, 1, 0) # c
changes(0, 0, 0, 1) # d

aその後、失敗して呼び出します

changes(2, 0, 0, 0) # aa
changes(1, 1, 0, 0) # ab
changes(1, 0, 1, 0) # ac
changes(1, 0, 0, 1) # ad

同時に、b失敗して呼び出します

changes(1, 1, 0, 0) # ba
changes(0, 2, 0, 0) # bb
changes(0, 1, 1, 0) # bc
changes(0, 1, 0, 1) # bd

ご覧のとおり、同じパラメーターabを使用します。baac/ca など...

于 2013-03-05T05:05:19.467 に答える
0

いくつかの説明を付けてコードを書き直しましょう。

@variants = []
def changes(w, x, y, z)
  case 0.01 * w + 0.05 * x + 0.1 * y + 0.25 * z 
  when 0...0.25
    changes(w + 1, x, y, z)
    changes(w, x + 1, y, z)
    changes(w, x, y + 1, z)
    changes(w, x, y, z + 1)
  when 0.25
    @variants << [w,x,y,z] unless @variants.include?([w,x,y,z])
  end 
end

changes(0, 0, 0, 0)
puts @variants.size
@variants.each { |v| puts "w: #{v[0]} x: #{v[1]} y: #{v[2]} z: #{v[3]}" }

まだカウントされていない場合にのみ、カウントにバリアントを追加するという主なアイデア。重複は、状態に到達するためのさまざまな方法があるという事実から生じました[w=1,x=1]：[0,0]⇒[0,1]⇒[1,1]そして[0,0]⇒[1,0]⇒[1,1]（中央のチェーンリンクに注意してください。）caseここでは、のスパゲッティよりも明白ですif-elsif-end。

于 2013-03-05T05:39:16.553 に答える