Re: [問題] 硬幣交易
※ 引述《EIORU ()》之銘言：
: 某個地方的市場
: 規定東西交易時
: 買賣雙方最多可拿出兩個硬幣
先理解為雙方可"各"拿出兩個硬幣
: Q1
: 當貨物價額為1~10元
: 則該地方的貨幣面額必須有哪些
: 使得貨幣種類最少
很容易證明兩種硬幣不夠
因為最多只會有 a, b, 2a, a+b, 2b, |a-b|, |a-2b|, |2a-b|, |2a-2b| 九種
所以至少要三種 而原推文已有 {2,3,7} 一解
: Q2
: 當貨物價額為1~30元
我剛剛找到一組解: {3,5,14,21}
1 = 3 + 3 - 5 16 = 5 + 14 - 3
2 = 5 - 3 17 = 3 + 14
3 = 3 18 = 21 - 3
4 = 5 + 5 - 3 - 3 19 = 5 + 14
5 = 5 20 = 5 + 21 - 3 - 3
6 = 3 + 3 21 = 21
7 = 5 + 5 - 3 22 = 14 + 14 - 3 - 3
8 = 3 + 5 23 = 5 + 21 - 3
9 = 14 - 5 24 = 3 + 21
10 = 5 + 5 25 = 14 + 14 - 3
11 = 14 - 3 26 = 5 + 21
12 = 3 + 14 - 5 27 = 14 + 21 - 3 - 5
13 = 5 + 14 - 3 - 3 28 = 14 + 14
14 = 14 29 = 14 + 21 - 3 - 3
15 = 21 - 3 - 3 30 = 14 + 21 - 5
其實只是從「一定要兩元硬幣嗎」的想法出發的 (因為 2 在後面其實受限滿大的)
一開始的 {3,5} 可以得到 1~8 和 10
下一個數字要把範圍弄大一點所以選了 9+5=14 (正好讓 14-4 = 10 和 5+5 互補)
再往上在 15 停了 所以這次為了補多一點選了 15+6=21
然後後面多利用兩大找兩小就出來了
是不是有三種硬幣的解要再看看了...
: 如 有2元/3元
: 可以滿足1~6元
--
突然有種 Project Euler 哪天出這種題目也不奇怪的感覺...
--
1989/02/22 優希堂悟 1990/02/22 冬川こころ 1993/07/05 小町つぐみ 1994/05/21 高江
ミュウ 1995/04 歡迎來到 星野遊々 1997/03/24 守野いづみ 1997/03/24 伊野瀬チサト
1998/06/18 守野くるみ 1999/10/19 打越鋼太郎的 楠田ゆに 2000/02/15 樋口遙 2002/
12/17 八神ココ 2011/01/11 HAL18於朱倉岳墜機 2011/04/02 ∞與∫的世界 茜崎空啟動
2012/05/21 第貮日蝕計畫預定 2017/05/01~07 LeMU崩壞事故 2019/04/01~07 某大學合宿
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.28.92
討論串 (同標題文章)