Re: [問題]找錢問題 不知道能不能在這邊問～
※ 引述《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個才能表示，並可能更差。
--
「可是妳......不是天使嗎？」
「天使？」她緩緩的轉過頭來，用悲傷的表情。「天使，只不過是神創造出來的
不死玩偶。」
「而神，也只不過是詛咒下的偽善使者。」
－－星．幻．夢的傳說
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.31.182
※ 編輯: ddavid 來自: 140.112.31.182 (04/17 03:49)
討論串 (同標題文章)
Inference 近期熱門文章
3
13
PTT遊戲區 即時熱門文章
37
48
17
19