作者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
推 tzhou:我想到的是: 可能不是光兩倍就比較好的概念耶 也許跟mod有關 04/18 00:20
推 teves:我認為若幣值互為倍數,可以肯定可以由大選到小 04/18 00:29
→ teves:若幣值不互為倍數,可能得檢查到兩者的最小公倍數. 04/18 00:30
推 tzhou:所以根據2樓的想法 25是因為可用10 5湊出 但11 5卻湊不出25 04/18 00:33
→ teves:應該是不用檢查到最小公倍數那麼多,但是應該要往上檢查 04/18 00:35
→ teves:像11跟5就需要檢查5的倍數中有沒有用掉11會比較差的 04/18 00:36
→ teves:25跟10其實還是應該要檢查有沒有10的倍數用25會變差的的 04/18 00:37
→ teves:舉例:25,10,1 那30就不能用1個25跟5個1 04/18 00:38
推 teves:我又想了想,其實不只倍數,其他的數也要檢查,真的很麻煩- - 04/18 00:41