在我多年的编程中,我已经使用递归来解决简单的问题,但我完全清楚,有时你需要迭代,因为内存/速度问题.
所以,在很久以前的某个时候,我去尝试找出是否存在任何"模式"或文本书的方式将常见的递归方法转换为迭代而没有发现任何东西.或者至少我记不住任何事都会有所帮助.
我制作的游戏包括10美元,5美元,3美元和1美元的硬币面额.玩家可以在其库存中具有0种或更多种类型的货币,总共最多15个硬币.我试图弄清楚如何正确选择硬币,以便给予最少量的改变作为回报.起初我觉得这很容易解决,但现在我无法绕过它.
以下两个例子可以进一步解释这种情况:
例1:
用户携带这些硬币:5美元,3美元,3美元,3美元,1美元,1美元,1美元,1美元,并想购买12美元的商品.解决方案是支付5美元,3美元,3美元,1美元并且不做任何改变.
例2:
用户没有任何1美元的硬币,并且携带5美元,3美元,3美元,3美元,3美元.一件物品以12美元的价格购买,因此他们以5美元,3美元,3美元和3美元的价格购买,并且返还2美元的更改.
由于我们首先选择较大的硬币,我无法弄清楚的是如何知道玩家的库存中是否有足够的低价值硬币(在这种情况下为1美元)以适应示例1,如果没有足够的硬币使用更多高价值的硬币,如例2所示.
在下面的示例中可以看到另一个问题,但我很高兴只是让上面的两个示例正常工作:
示例3: 用户携带这些硬币:5美元,3美元,3美元,3美元.玩家以6美元的价格购买东西.最好使用3美元和3美元并且不返回任何变化,而不是使用5美元和3美元,并给出2美元的变化.
我相信前两个例子可以使用递归和贪婪算法的变体来解决.
赏金奖励:
我现在已经在下面添加了我自己的答案作为临时解决方案.但是,我喜欢Llama先生的方法(参见他引用的链接),并希望找到一个PHP示例来满足这一要求.我相信这种方法不需要递归并使用memoization.
如果有多个选项可以进行最少量的更改,那么我希望能够以最少的硬币付款.
以下示例在Node.js书中给出:
var open = false;
setTimeout(function() {
open = true
}, 1000)
while (!open) {
console.log('wait');
}
console.log('open sesame');
作者解释说明while循环阻止执行的原因:
Node永远不会执行超时回调,因为事件循环停留在第7行的while循环中,永远不会让它有机会处理超时事件!
但是,作者没有解释为什么会在事件循环的上下文中发生这种情况或者真正发生在幕后的事情.
有人可以详细说明吗？节点为什么会卡住？如何更改上面的代码,同时保留while控制结构,以便不阻止事件循环,并且代码将按照人们可能合理预期的方式运行; 等待将在setTimeout火灾前记录仅1秒,然后在记录"打开芝麻"后退出该过程.
关于IO和事件循环和回调这个问题的答案等通用解释并没有真正帮助我理解这一点.我希望直接引用上述代码的答案会有所帮助.