找錢問題 不知道能不能在這邊問～ - 推理遊戲

Jacky avatar
By Jacky
at 2007-04-17T00:07

Table of Contents

最近遇到一個問題 因為一直想不出要怎麼解決
爬文似乎也沒有類似的問題 不知道PO在這會不會很奇怪
希望板上大大能給一些想法

店員有25元、10元、5元、1元的幣值
要找77元給顧客，方法有很多種
其中一種找錢的方法是先把77除以25整數為3
餘數2再除以10以及5整數皆為0
2除以1整數為2
如此一來 我們可以拿出3個25元硬幣以及2個1元硬幣給顧客
而且這也是銅板總數目最小的方法
我想問的是
如果要找出一種銅板總數目最小的方法
這種把要找錢的數目先從大的幣值除
所得餘數再由第二小的幣值一直除下來的方法能夠通用在所有的錢數嗎
如果可以 要如何證明呢？

如果今天我們的幣值是25元、20元、10元、5元、1元
利用以上方法 40元就不適用了
最小的硬幣數是2個20元 而不是1個25元、1個10元以及1個5元
我想知道這兩種幣值有什麼差異
為什麼第一種幣值就可以用這種方式 而第二種不行

最後 因為這個是一個資工作業
所以老師要我們寫一個程式解決第二種幣值要找出最小銅板數的問題
希望各位大大不吝指教
感恩~ <(_ _)>

--

All Comments

Harry avatar
By Harry
at 2007-04-18T02:09
對於你的第一個問題,你都舉出反例了還用證明嗎XD
Charlotte avatar
By Charlotte
at 2007-04-21T12:48
至於你的作業,很明顯是用dynamic programming
Carol avatar
By Carol
at 2007-04-22T13:09
當你拿走任意一個硬幣以後,等同於一個金額較少的相同問題
Sandy avatar
By Sandy
at 2007-04-26T04:31
所以 數量(金額)=1+min(數量(金額-25),數量(金額-20),...)

密碼字謎 7 【題目】

Connor avatar
By Connor
at 2007-04-14T20:46
規則： 例如：謎題：xp la lxpe snnsyw xk fbw zwkf kwrutbxps wpsxpw. 　　　謎底：in my mind google is the best searching engine. =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= ...

密碼字謎 6 【題目】

Jack avatar
By Jack
at 2007-04-14T18:17
規則： 例如：謎題：xp la lxpe snnsyw xk fbw zwkf kwrutbxps wpsxpw. 　　　謎底：in my mind google is the best searching engine. =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- ...

邏輯問題

Necoo avatar
By Necoo
at 2007-04-13T23:58
我朋友拜託我解的題目之一 真是想破頭也想不出來 請幫幫忙 拜託了 謝謝 --------- 95年世新 數媒系 轉學考 11.以下數字係由某些規則排列而成 5 6 12 11 () 14 24 請問()中的數字為何? A.10 B.13 C.18 D.21 - ...

我媽問我的兩個問題

Emily avatar
By Emily
at 2007-04-13T19:15
※ 引述《idicivik ( 苦海釣叟)》之銘言 : 如果是這樣看勒 : 5 -andgt; 18 (13) 13 -andgt; 25 (12) : 18 -andgt; 43 (25) 25 -andgt; 35 (10 ...

密碼字謎 5 【題目】

Ethan avatar
By Ethan
at 2007-04-13T17:49
規則：每一個字母都恰巧代表另一個字母 例如：謎題：xp la lxpe snnsyw xk fbw zwkf kwrutbxps wpsxpw. 　　　謎底：in my mind google is the best searching engine. =-=-=-=-=-=-=-=-=-=-=-=-=- ...