我的任务是使用暴力编写一个算法来确定不同方式的数量，以及给定数量的变化的相关组合。找零将使用以下硬币：便士（1 美分）、镍币（5 美分）、一角硬币（10 美分）和 25 美分（25 美分）。
e.g.
输入：16（表示变化16美分）
输出：可以通过 6 种不同的方式产生，它们是：
- 16 便士。
- 11 便士，1 镍币
- 6便士、1毛钱
- 6 便士，2 镍币
- 1 便士，3 镍币
- 1 便士、1 镍币、1 毛钱
我的算法必须针对指定的更改量生成所有可能的更改组合。
我完全不知道如何开始启动这样的算法。任何能让我继续前进的意见或见解都会很棒。
好的。让我解释一下暴力算法的一个想法。我在这里将使用递归。
让你需要改变c美分。然后考虑c as
c = p * PENNY + n * NICKEL + d * DIME + q * QUARTER
或者简单地说，
c = ( p * 1 ) + ( n * 5 ) + ( d * 10 ) + ( q * 25 )
现在您需要检查所有可能的值p, n, d and q等于c。使用递归，对于每个p in [0, maximumPennies]遍历每个n in [0, maximumNickels]。对于每个n遍历每个d in [0, maximumDimes]。对于每个d遍历每个q in [0, maximumQuarters].
p in [0, maximumPennies] AND c >= p
|
+- n in [0, maximumNickels] AND c >= p + 5n
|
+- d in [0, maximumDimes] AND c >= p + 5n + 10d
|
+- q in [0, maximumQuarters] AND c >= p + 5n + 10d + 25q
对于这些步骤中的任何平等，您都会得到一个解决方案。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
