我正在尝试从 coursera 的 scala 类(class)中构建我的最后一份作业，但是我的算法似乎失败了。但是我不明白为什么它失败以及为什么它返回 0。
注意 我不是要解决这个问题。我想要一个关于代码发生了什么以及它为什么失败的解释。
def countChange(money: Int, coins: List[Int]): Int = {
def cc(amount: Int, list: List[Int]): Int = {
println(amount, list);
if (amount == 0) 1
if (amount < 0 || list.isEmpty) 0
else cc(amount - list.head, list) + cc(amount, list.tail)
}
cc(money, coins)
}
逻辑是，您可以对给定金额进行找零的方式数量等于您可以使用第一种类型的硬币找零的方式数量
+ 您可以为下一种类型的硬币找零的方式数量.这导致了一个递归函数，它计算了所有的方式。这是我的逻辑，这就是我试图构建的内容，但这就是它返回的内容: (10,List(2, 3, 5))
(8,List(2, 3, 5))
(6,List(2, 3, 5))
(4,List(2, 3, 5))
(2,List(2, 3, 5))
(0,List(2, 3, 5))
(-2,List(2, 3, 5))
(0,List(3, 5))
(-3,List(3, 5))
(0,List(5))
(-5,List(5))
(0,List())
(2,List(3, 5))
(-1,List(3, 5))
(2,List(5))
(-3,List(5))
(2,List())
(4,List(3, 5))
(1,List(3, 5))
(-2,List(3, 5))
(1,List(5))
(-4,List(5))
(1,List())
(4,List(5))
(-1,List(5))
(4,List())
(6,List(3, 5))
(3,List(3, 5))
(0,List(3, 5))
(-3,List(3, 5))
(0,List(5))
(-5,List(5))
(0,List())
(3,List(5))
(-2,List(5))
(3,List())
(6,List(5))
(1,List(5))
(-4,List(5))
(1,List())
(6,List())
(8,List(3, 5))
(5,List(3, 5))
(2,List(3, 5))
(-1,List(3, 5))
(2,List(5))
(-3,List(5))
(2,List())
(5,List(5))
(0,List(5))
(-5,List(5))
(0,List())
(5,List())
(8,List(5))
(3,List(5))
(-2,List(5))
(3,List())
(8,List())
(10,List(3, 5))
(7,List(3, 5))
(4,List(3, 5))
(1,List(3, 5))
(-2,List(3, 5))
(1,List(5))
(-4,List(5))
(1,List())
(4,List(5))
(-1,List(5))
(4,List())
(7,List(5))
(2,List(5))
(-3,List(5))
(2,List())
(7,List())
(10,List(5))
(5,List(5))
(0,List(5))
(-5,List(5))
(0,List())
(5,List())
(10,List())
0
正如您所看到的，它返回 0，即使从打印的调用中可以看出它所采取的步骤似乎正是我的逻辑试图实现的。
这是主函数中函数的调用:
println ("" + countChange(10,List(2,3,5)))
请 不要给我可以复制和粘贴的烘焙代码。我想知道我的逻辑有什么问题。
最佳答案
您缺少 else :
if (amount == 0) 1 // This value is thrown away
if (amount < 0 || list.isEmpty) 0
else cc(amount - list.head, list) + cc(amount, list.tail)
只需在第二个
if 之前添加它就可以了。(如果不清楚，只返回最后一个 if/else 的结果，所以在
if (a) 1
if (b) 2
if (c) 3
else 4
只有最后两行很重要。如果您想选择这些选项之一，
if (a) 1
else if (b) 2
else if (c) 3
else 4
是你需要的。)
关于硬币找零算法失败，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23545113/