作者laymu (炎羅)
看板STU
標題[閒聊] 題目看起來很簡單的數學問題…資工或金融系請進
時間Wed Apr 29 00:22:11 2009
好像還滿多同學喜歡解題的，
我就把之前沒解出來的題目丟出來請大家幫忙吧。
--
作者：暴暴小聖＠流連忘返（
http://www.wasabistudio.ca/）
買一棵搖錢樹需要10元，賣掉只有5元，每棵搖錢樹每回合能生產1元。
玩家一開始有50元，每回合只能選擇買樹、買樹或什麼都不做。
買樹或賣樹的那回合，既有的搖錢樹不會生產，搖錢樹沒有買賣數量的限制。
請問玩家最快第幾回合能有1000元。
--
我的解貼在我的無名:
http://www.wretch.cc/blog/laymu/21638687
--
男人會衡量他身邊所有異性跟他發生性行為的可能性。
by 亞里斯多德
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.227.65.27
1F：→ laymu :有詳解的話請用回文的，方便日後編輯，謝謝。 04/29 00:23
2F：推 jieing :之前逛版大的blog看過了 XD 數學家就是你了 04/29 00:23
3F：→ laymu :我朋友說這要用到機率統計的工具算…我也不清楚 04/29 00:24
4F：推 slcgboy :買述的時候 是新買的不會生產還是所有的都不會生產 04/29 00:25
5F：→ laymu :都不會。買樹或賣樹的那回合，既有的搖錢樹不會生產 04/29 00:26
6F：→ laymu :最笨的方法就是讓程式慢慢跑，把各種組合都嘗試一遍 04/29 00:27
7F：推 jieing :讓我想到我還要做assembly language的homework...... 04/29 01:46
8F：→ jieing :噢 幹你媽的交作業大學 老子決定今天熬夜看書了 XD 04/29 01:47
9F：推 ozibz :有錯字!!買樹、"買"樹或什麼都不做~ 04/29 08:31
10F：推 YahooTaiwan :我好奇的是 除了即將到達1000時需賣樹外 還有什麼情 04/29 08:57
11F：→ YahooTaiwan :況會賣樹？ 04/29 08:57
賣樹的效果：虧5元、接下來的回合不能再生產、這回合不能生產、獲得5元現金。
可知：(1)賣樹對往後的生產沒有幫助、(2)(比照不賣樹)不會獲得更多的樹
∴在任何回合賣樹都沒好處，除了最後一回合(因為沒有後續的回合)
假設某回合有N棵樹、M的現金(M>=0且屬於整數、N屬於自然數)
若(1)最後把樹賣光，則至少需要[(1000-M-5N)/N]+1回合，現金才能超過1000；
若(2)最後不賣樹，則至少需要[(1000-M)/N]+1回合，現金才能超過1000。
∵分母均為N 且 1000-M-5N < 1000-M
∴(1)需要的回合數 < (2)需要的回合數。
∴最後一定要把樹賣光，才會快。
※ 編輯: laymu 來自: 61.227.66.17 (04/29 09:52)
12F：推 runtime :沒意外可以降到3X回以下 04/29 11:15
13F：推 OpenGoodHate:這個讓我想到…Recursive 04/29 11:42
14F：→ laymu :用程式寫的確可以用Recursive慢慢試，不過如果用算的 04/29 11:53
15F：→ laymu :我就不會了…XD 04/29 11:53
16F：推 runtime :我剛看到 有寫個半殘的 Recursive 就有試到36以下 04/29 16:44
今天睡覺前我也寫個Recursive好了，睡覺的時候開著讓他自己慢慢跑…
另外還是有個東西得證明：
每次買樹的時候，是否一定要「能買多少就買多少」才是最快的？
不過就算沒有證明，我的程式會基於這個假設去run。
※ 編輯: laymu 來自: 61.227.73.241 (04/29 17:24)
17F：推 runtime :會跑到你瘋掉 記得要把結果存出來 04/29 17:36