作者allen65535 (来来回回的人)
看板Inference
标题Re: [问题]找钱问题 不知道能不能在这边问～
时间Wed Apr 18 01:59:19 2007
※ 引述《weiluner (游戏人间^^y)》之铭言：
: 如果今天我们的币值是25元、20元、10元、5元、1元
: 利用以上方法 40元就不适用了
: 最後 因为这个是一个资工作业
: 所以老师要我们写一个程式解决第二种币值要找出最小铜板数的问题
我想最後这两句才是重点，这本来就是一个找不太出逻辑的问题。
所以让程式去跑才是最实在的。
在这里1元的角色是比较特别的，剩下找不出来的钱，再用1元补就好。
我想到的方法是，用4个回圈分别对应25元、20元、10元、5元，
回圈要跑的东西是该种币值从最少可以用几个到最多可以用几个，
例如25元就是从0到1。
for (i=...)
for (j=...)
for (k=...)
for (l=...)
用一个变数储存你用了几个硬币，
找到比较小的解的时候就把他覆盖过去。
当然还要排除一些不可能的状况，
例如25元用2个和20元用2个的时候，就超过40元了
碰到这种状况的时候就让程式跳过就好。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 59.115.225.126
1F：推 ddavid:这是一个dynamic programming问题，用你的方法效率会较差 04/18 02:01
2F：→ ddavid:实际用来解决的方法在第一篇teves的推文已有提到 04/18 02:02
3F：推 ddavid:另外这并不是一个找不出逻辑的题目 04/18 02:04
4F：→ ddavid:我没记错的话这个题目是已经被研究过的题目了。 04/18 02:05
5F：推 allen65535:效率差我也知道,不过作业本来就是每个人都要不一样啊XD 04/18 02:13
6F：→ allen65535:如果有限定要用dynamic programming老师应该会讲吧 04/18 02:14
7F：推 ddavid:有最佳做法的题目，当你想到了最好那个方法， 04/18 02:15
8F：→ ddavid:那跟别人一样是正常的啊XD 04/18 02:15