当前位置： 查字典图书网> 编程> 程序员面试逻辑题解析> 1.1 甜食爱好者个人解答思路

1.1 甜食爱好者个人解答思路

七月 对 程序员面试逻辑题解析 的书评 发表时间：2014-08-19 23:08:55

使用过的方法：
罗列出的等式，解方程组（线性代数知识）。

文中解决思路文字过多，个人尝试将其抽象化。
n块蛋糕时，Marie有 M(n)块，Jeremy有J(n)块。
(n-1): M(n-1)，J(n-1)。
新增加一块时，分为f和(1-f)，f>(1-f)。

边界条件：Marie先挑 = Jeremy先挑
对于M：
M(n-1)+f = (n-1)/2 + (1-f), M(n) = M(n-1)+f
对于J:
J(n-1)+(1-f) = (n-1)/2 + f, J(n) = J(n-1)+(1-f)

solve the equations, we get:
M(n) = M(n-1)/2 + (n+1)/4
J(n) = J(n-1)/2 + (n+1)/4

因此，二者差别在于上一次蛋糕相差数的1/2
然后就是非常简单的递归。
2块相差 1/2(3/4, 5/4)块。
3块相差 1/4块。
……

这样子避免了比较难解的某方程。

有用 1 无用 0

您对该书评有什么想说的？

对“1.1 甜食爱好者个人解答思路”的回应

colorcenter
colorcenter 2014-10-26 11:17:41

1. 假设杰里第i次切出的大块为X（N+1-i）。这种奇怪的命名在后面会用到。
2. 从玛丽的角度来看，她行使所有（N-1）选择机会后得到的蛋糕才能最多
3. 从杰里的角度来看，他最后一次切蛋糕只有两种可能：均分（X(N)=1/2;让玛丽选）或者切下来几乎整块（X(N)=1）留给自己。
4. 杰里要保证所的到的最多最好的策略是切除的蛋糕，让玛丽无论怎么选她所得到的结果都一样。N N≥2；玛丽一共得到的蛋糕为:前N-1次选大块的T(N)=X(N)+X(N-1)+…+X(2)。
5. 分析玛丽的选择行为：
a) 第一次不选：T(N)=1-X(N)+(N-1)/2=(N+1)/2-X(1)
b) 第一次选择：T(N)=X(N)+T(N-1)
c) 所以有：N≥2，T(N-1)+2X(N)=(N+1)/2；即N≥2，2X(N)-X(N-1)=(1/2)^N
d) 当N=2时，X(2)=3/4，T(2)=3/4。
到这里，计算机就可以穷举出所有项了；但是注意程序中设置临时变量，将不用的值社区，注意时间复杂度。
易得：X(N)=1/2+(1/2)^N。（Cn、Cn-1两式相见的到X(N)的递归式；递归式一次乘以1/2相加消去中间项，得到X(N),X(2)的关系即可求出X(N）。
公平的做法就是：每一次，当其中一人切下一块蛋糕，选择权则归另外一个人。

回应他

《程序员面试逻辑题解析》热门书评

程序员面试逻辑题解析

书名： 程序员面试逻辑题解析
作者： 萨沙
出版社： 人民邮电出版社
原作名： Puzzles for Programmers and Pros
译者： 朱学武  |  费若愚
出版年： 2013-1
页数： 208
定价： 35.00元
装帧： 平装
ISBN： 9787115301956