作者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