作者ddavid (星舞弦独角兽神话忆)
看板Inference
标题Re: [问题]找钱问题 不知道能不能在这边问～
时间Wed Apr 18 02:14:08 2007
实际程式化的话是这样，以{25, 20, 10, 5, 1}来说：
// 隔这个define去取data[a]的值只不过预防取到a < 0，其中MAX_INT是个很大的值
// ，使得如果取到a < 0时给出很大的值，就会直接被min舍弃掉
#define DATA(a) ((a >= 0) ? (data[a]) : (MAX_INT))
// 价值0时用的硬币数为0
data[0] = 0;
// 从价值1开始跑到MAX_NUM
for(i = 1; i < MAX_NUM; i++)
{
// 某价值所需最少硬币，就是扣掉各个币值後的各个价值中，选用币数最少的那个
// 加上1
data[i] = 1 + min(DATA(i - 25), DATA(i - 20), DATA(i - 10), DATA(i - 5),
DATA(i - 1));
}
主程式这样就搞定了，跑完data[x]就是代表x这个价值需要多少硬币。
令m为钱币种类数、n为要算的最大价值的话，这程式时间复杂度是O(mn)，会远
比用多层回圈硬干的O(n^m)好上太多。
--
「去质疑亲眼所见的事是最愚昧的行为。这又分为两种－－质疑自己所见是不是
真的，或是用见到的事去质疑没见到的事。呵。」
－－芙莉雅，谎言事务所实现使者
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.31.182
1F：推 allen65535:专业的来了，我看不懂 XD 04/18 02:17
2F：推 ddavid:补加上注解说明了。 04/18 02:33
※ 编辑: ddavid 来自: 140.112.31.182 (04/18 02:35)
3F：推 weiluner:虽然我不是资工系的 但我已经有点了解 感谢大大们的回答딠 04/18 11:53
4F：推 teves:你不是资工系的还要写资工作业? 跑去修资工的课? 04/18 18:16
5F：推 darkbuffoon:请问签名档的由来？ 04/19 07:40
6F：推 weiluner:我是生科系的 这是资工系开的生物资讯课程~ 04/19 11:03
7F：推 ddavid:签名档是自己的作品XD 04/20 03:54
8F：推 tdk4:看原Po的签名档就知道你没有研究魔术XD 04/27 14:20
9F：推 SantaLucas:好奇学过魔术的人会怎麽改写这句话？ 04/29 11:22