1.1 甜食爱好者个人解答思路_程序员面试逻辑题解析书评-查字典图书网
查字典图书网
当前位置: 查字典 > 图书网 > 编程 > 程序员面试逻辑题解析 > 1.1 甜食爱好者个人解答思路
七月 程序员面试逻辑题解析 的书评 发表时间:2014-08-19 23:08:55

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

使用过的方法:
罗列出的等式,解方程组(线性代数知识)。

文中解决思路文字过多,个人尝试将其抽象化。
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.1 甜食爱好者个人解答思路”的回应

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)。
公平的做法就是:每一次,当其中一人切下一块蛋糕,选择权则归另外一个人。