作者weiluner (游戏人间^^y)
看板Inference
标题Re: [问题]找钱问题 不知道能不能在这边问～
时间Tue Apr 17 23:51:43 2007
※ 引述《weiluner (游戏人间^^y)》之铭言：
: ※ 引述《ddavid (星舞弦独角兽神话忆)》之铭言：
: 对不起 可能我写的不够清楚
: 第一个问题的前提是只有第一种币值情形下
: 要如何证明用上述方式就可以找到最小硬币数(其实等同第二个问题拉~)
: : 原因是，第一种币值的情况，每一个币值都大於等於两倍的比它小币值。这确保
: : 了「当可以用某币值表现的值，其中一个硬币／钞票换成更小的来表现时一定得用两
: : 个或以上。」
: : 比如25 > 2 * 10，所以25可用1 * 25，换成用比它小的就要2 * 10 + 1 * 5共
: : 三个。
: : 而第二种币值中，25 < 20 * 2，这表示至少在20 * 2 = 40这个值上以25来表现
: : 无法确保比用20来表现用更少的币数，因为20只要2个就能表现，但25用了1个之後还
: : 剩余15，等於是至少要用2个才能表示，并可能更差。
: 我有想过这个方法
: 但是如果币值是5元、4元、3元、2元、1元我却找不到反例
: 5 < 4*2
: 所以只能证明哪种币值用此方法可以找到最小值
: 不一定每种能用此法找到最小值的币值都是符合这个条件吗?
我们有想到这个方法
但是如果币值是25.11.5.1 也符合上面的条件
找33元 只需3个11元硬币
但却需要1个25元 1个5元 3个1元
这样是不是要用上述方法 还需要一些特殊条件呢？
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 163.25.118.149
1F：推 tzhou:我想到的是: 可能不是光两倍就比较好的概念耶 也许跟mod有关 04/18 00:20
2F：推 teves:我认为若币值互为倍数,可以肯定可以由大选到小 04/18 00:29
3F：→ teves:若币值不互为倍数,可能得检查到两者的最小公倍数. 04/18 00:30
4F：推 tzhou:所以根据2楼的想法 25是因为可用10 5凑出 但11 5却凑不出25 04/18 00:33
5F：→ teves:应该是不用检查到最小公倍数那麽多,但是应该要往上检查 04/18 00:35
6F：→ teves:像11跟5就需要检查5的倍数中有没有用掉11会比较差的 04/18 00:36
7F：→ teves:25跟10其实还是应该要检查有没有10的倍数用25会变差的的 04/18 00:37
8F：→ teves:举例:25,10,1 那30就不能用1个25跟5个1 04/18 00:38
9F：推 teves:我又想了想,其实不只倍数,其他的数也要检查,真的很麻烦- - 04/18 00:41