1

我试图解决的问题如下：

给定 n 美元，你有无限的便士、五分钱、一角硬币和 25 美分硬币，计算表示 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并ba使用相同的参数。等与ac / 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]}" }

您添加一个变体的主要思想是当且仅它还没有被计算在内。dups 源于这样一个事实，即有不同的方式可以达到一个状态[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 回答