返回第二十六章 自动售货机(第1/1页)  编程之战首页

关灯 护眼     字体:

上一章 目录 下一章

    “我的要求很简单,就是能喝上一罐82年份的雪碧”。

    杨成坏坏地笑了。

    “好,满足你!”

    系统声音刚落,杨成就出现在了一个自动售货机前面。

    漆黑的夜晚,明亮的路灯下面,自动售货机散发出微蓝色的光芒,里面一排排的货架盛放着一瓶瓶饮料。

    杨成掏出几个硬币,先选中了雪碧下面的按钮,然后把硬币塞进投币口。

    估摸着过了好几秒钟,从出货口并没有滚出来饮料。

    相反一个便笺飘落了下来。

    借着微弱的灯光,杨成拿起便笺一看,上面写着几行小字。

    “为自动售货机编写业务逻辑,已知规则如下:”

    “1.售货机接收n种纸币或硬币,其中包括1元,5元,10元....”

    “2.售货机最开始拥有各种类型钱币的数量都是一定的”。

    “3.如果投入的钱币低于商品的价值,那么将钱币原封不动地退回”。

    “4.如果投入的钱币等于商品的价值,那么无须找零”。

    “5.如果投入了售货机不支持的钱币类型,原路返回无效的钱币”。

    “6.如果要找零,尽可能从大额的纸币开始,比方说,要找25块钱,退回的结果是1张20块和1张5块,而不是2张10块的和1张5块”。

    “7.如果售货机已有的钱币无法全额找零,那么尽可能接近地找零,但售货机是不能吃亏的!”

    “这是个背包问题啊”,杨成挠了挠头。

    最后一条描述说明了问题的性质。

    背包问题可以描述为:

    给定一组物品,每种物品都有自己的价格,在限定的总价值内,我们如何选择,才能使得物品的总价格最高。

    对于这一类问题,最好最高效的方法是动态规划求解,但使用递归蛮力求解,在小数据范围内也是可以的。

    假如售货机内已有1元钱币3个,5元钱币5个,20元钱币1个。

    我要购买3元的雪碧一瓶,并投进去了一张20元纸币,那么我得找零17元。

    先看能用于找零的有什么样的钱币,20元的肯定排除,因为它大于17,售货机可不干亏本买卖!

    然后,我们看3个1元钱币和5个5元钱币能不能产生找零17元的结果?

    答案是肯定的,3个5元钱币和2个1元钱币就能够组成17。

    这就是递归匹配的过程,不过具体实现上面,很多地方可以优化,用来提高效率。

    “真的是好麻烦啊”,杨成擦了一把汗,在路灯的照耀下挥汗如雨。

    早知道喝瓶雪碧解解渴这样的简单要求居然要先写个多小时的代码,还不如把自己送到海南喝点纯正的椰子汁呢!

    “哟西,终于搞定了”。

    杨成不愧是有毅力的程序员。

    “叮!恭喜您完成了自动售货机的相关任务!”

    “当前积分55分,击败了全球27%的玩家,请您再接再厉!”

    “咕噜噜...”

    从自动售货机的出货口滚落下来一瓶冰镇的雪碧,还有一张小小的便笺。

    便笺上面写着一行娟秀的字迹。

    “请慢用^_^”飘天文学_www.piaotiange.com

『加入书签,方便阅读』

上一章 目录 下一章