→ jurian0101 :具體來說有186360種從(10,10)走到(1,3)不超界的方法 05/30 01:43
※ 引述《wtkao780302 (青空)》之銘言：
: 「一瓶飲料2元 兩個瓶蓋可再換一瓶 四個無瓶蓋空瓶又可換一瓶 請問20元可喝多少瓶」
: 我媽昨天打電話問我這個
分析一下內容物價值，2元=身+蓋+水=2蓋=4身，因此身=0.5, 蓋=1, 水=0.5
每次喝掉的是值0.5元的水，不能回收。所以能喝到的瓶數上限值是 20/0.5=40瓶
但前幾樓的細心分析發現怎樣都只能喝到35瓶，剩下1個蓋子3個瓶身
35* 1/2 + 1 + 3* 1/2 = 20元
~~~~~~~~~~
2.5
先岔開說，這個分析在「5根菸屁股換一支菸，今有23支(這數字隨意)能抽幾根」的問題
很有效
因為每次等於抽掉4/5根菸, 23 = 4/5 * 28 + 3/5
~~ 28 = 23 + 4 + 1，剩3根菸屁股
好吧，價值守恆無誤，但怎麼一題能達到理想，一題就換不完？差在哪
容我鍵盤圖解！
一開始擁有 (蓋,身) 狀態是 (10, 10)，正好畫在X-Y軸格子點上，畫好了沒？
換飲料步驟翻譯成：
用蓋子換一次是前進 (-1, 1) 向量, 但只有在蓋 > 1才能走
用瓶身換一次是前進 (1, -3) 向量, 但只有在身 > 3才能走
觀察可知這個限制的直接結果是，換完後頂多停在x=1 或 y=1線上，不可能停在x/y 軸
換不完是一定的。
接著探討怎樣能最接近 (0,0) 並且使得剩下材料價值 X+0.5Y 最小，
重點是觀察最後能停在哪，決定之後就能逆推。
我們把格子點塗黑白，也就是說觀察X+Y座標的奇偶性，太好了，從X+Y=20≡0開始
兩種換法都使座標的奇偶性恆定。
也就是說 (1,2) 和 (2,1) 一看就知道走不到，因為X+Y=3≡1,
而 (1,1) 也到不了，沒有上一步的餘地。
(2,2)和(3,1)都能使用換瓶蓋步驟前進到 (1,3)
而這個點的剩餘價值，也就是2.5元的確是最低的了。
(20-2.5)/0.5=35，具體怎麼走試著畫，很好玩，但太多種了，不重要。
有興趣，其實有多少種不同順序的換法也算得出來wwww
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.213.88
※ 文章網址: http://www.ptt.cc/bbs/Math/M.1401384550.A.E3D.html