※ 引述《ddavid (星舞絃獨角獸神話憶)》之銘言： : ※ 引述《weiluner (遊戲人間^^y)》之銘言： : : 店員有25元、10元、5元、1元的幣值 : : 我想問的是 : : 如果要找出一種銅板總數目最小的方法 : : 這種把要找錢的數目先從大的幣值除 : : 所得餘數再由第二小的幣值一直除下來的方法能夠通用在所有的錢數嗎 : : 如果可以 要如何證明呢？ 對不起 可能我寫的不夠清楚 第一個問題的前提是只有第一種幣值情形下 要如何證明用上述方式就可以找到最小硬幣數(其實等同第二個問題拉~) : : 如果今天我們的幣值是25元、20元、10元、5元、1元 : : 利用以上方法 40元就不適用了 : : 最小的硬幣數是2個20元 而不是1個25元、1個10元以及1個5元 : : 我想知道這兩種幣值有什麼差異 : : 為什麼第一種幣值就可以用這種方式 而第二種不行 : 原因是，第一種幣值的情況，每一個幣值都大於等於兩倍的比它小幣值。這確保 : 了「當可以用某幣值表現的值，其中一個硬幣／鈔票換成更小的來表現時一定得用兩 : 個或以上。」 : 比如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 所以只能證明哪種幣值用此方法可以找到最小值 不一定每種能用此法找到最小值的幣值都是符合這個條件嗎? --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 163.25.93.75