Re: [問題]找錢問題 不知道能不能在這邊問~
※ 引述《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
推
04/18 00:20, , 1F
04/18 00:20, 1F
推
04/18 00:29, , 2F
04/18 00:29, 2F
→
04/18 00:30, , 3F
04/18 00:30, 3F
推
04/18 00:33, , 4F
04/18 00:33, 4F
→
04/18 00:35, , 5F
04/18 00:35, 5F
→
04/18 00:36, , 6F
04/18 00:36, 6F
→
04/18 00:37, , 7F
04/18 00:37, 7F
→
04/18 00:38, , 8F
04/18 00:38, 8F
推
04/18 00:41, , 9F
04/18 00:41, 9F
討論串 (同標題文章)
Inference 近期熱門文章
3
13
PTT遊戲區 即時熱門文章
37
48
17
19