笔趣阁 > 科幻小说 > 编程之战 > 章节目录 第四十五章 统计找零组合

 推荐阅读: 重生弃少归来 黎明之剑 说好的末世呢 七根凶简 民调局异闻录之勉传 学霸的黑科技系统 无限英灵神座 快穿攻略,病娇男主,宠翻天! 终极透视眼 纵横诸天的武者

编程之战 第四十五章 统计找零组合


“微风拂面,开着私家车在宽广的城市环线上驰骋,渴了来一瓶冰镇可乐,这种感觉真的很难用言语形容”。
    一辆进口车上走下来一位车主,他戴着一副酷酷的墨镜,正走向路边的一家便利店。
    便利店很普普通通,门口就挂了块“24小时营业”的牌子,杨成推门而入。
    “老板,来瓶可乐”,杨成站在柜台前,打量着四周。
    店长是一位中年大叔,他很热情地拿了瓶冰镇可乐,塞给杨成,然后笑眯眯地看着他。
    杨成接过可乐,拧开瓶盖,然后瓶口对准嘴巴,咕噜噜地喝了起来。
    大约过了几十秒,喝完最后一滴可乐,杨成抹抹嘴。
    “嗝~”,他舒服地打了个嗝,还有些意犹未尽。
    “老板,多少钱?”,杨成摸了摸口袋。
    “六块”,中年大叔报出价格。
    杨成递过去一张10块的,大叔接过钱,却没有急着找零。
    “小伙子,考考你”,大叔脸上流露出笑意。
    “我现在有1块和2块的两种硬币,如果要找零,有几种方式”。
    杨成略加思考,便给出了答案。
    “找零四块有三种方式”。
    “第一种,找四个1块的硬币”。
    “第二种,找两个1块和一个2块的硬币”。
    “第三种,找两个2块的硬币”。
    大叔接着问道。
    “那小伙子,假如要找零10块,而我现在有2块,3块和5块的硬币,有多少种方式呢?”
    “这。。。”,杨成一时语塞。
    “稍等一下”,杨成感觉大脑不够用了,于是调出代码编辑器面板。
    这是一个经典的找零组合问题,这种问题如果不用递归是很难求解的。
    现有硬币种类2,3,5,找零10块。
    将这个问题,可以分解为2个子问题:
    1.包含2块硬币有多少种解法。
    2.不包含2块硬币有多少种解法。
    对于每个子问题,又有子问题:
    1.包含当前最小面值硬币有多少种解法。
    2.不包含当前最小面值硬币有多少种解法。
    。。。。
    这两个子问题的解法种类之和就是最后的答案。
    编译,运行,得到结果,杨成给出了答案。
    “是4种!”
    “很好!”
    “结账!”,中年大叔递过来4块钱。
    “叮!恭喜您完成了统计找零组合的相关任务!”
    “当前积分103分,击败了全球37%的玩家,请您再接再厉!”

温馨提示:方向键左右(← →)前后翻页,上下(↑ ↓)上下滚用, 回车键:返回列表

上一章章节目录下一章