程序员面试逻辑题解析笔记（一）

蔚落 2021-11-26 10:22 347阅读 0赞

题目1：甜食爱好者

杰里米和玛丽是两个喜欢蛋糕也喜欢数学的小孩，当玛蒂娜大厨给他们准备了两块一模一样的蛋糕后，杰里米便说服玛丽玩一个游戏。

游戏规则：杰米里先把一块蛋糕切成两块，这两份大小可能一样，也可能不一样，切完之后，玛丽决定是否要先选蛋糕。如果玛丽先选，那么她会选份大的，如果杰米里先选，玛丽可以预料杰里米会选走份大的。

随后杰里米把另外一块也切两份，注意，他可以把其中一份切得非常小，如果之前 玛丽先选，那么这次杰里米就可以拿走大的那份，如果之前是杰米里先选，那么这次玛丽就可以拿走大的那份。

假设每个小孩的目标是分得尽可能多的蛋糕，那么对于杰里米来说最好的策略是什么呢？

解析：

可以假设第一块分为两份，分别用f和1-f来表示。其中f >= 1/2。假设下面两种情况：第一种，玛丽先选择，拿走了f那块；第二种情况，玛丽后选，拿走了1-f那块。依次进行分析。

玛丽可以如下分析：

如果是我先选的情况：第一块她拿走了f，那么杰里米在分第二块时，肯定分为一块很大，一块非常小。也就是玛丽一共就得到了f。

对于我后选的情况：第一块中，玛丽得到了1-f，那么杰米里在分第二块时，之后平分，他才能获得最多的蛋糕，也即玛丽可以得到1/2

杰里米也会想到玛丽所分析的情况。所以杰米里必须使自己在两次中得到的量一样多，才能确保自己得到最多的蛋糕。

即让玛丽两种情况下得到一样多： f = 1-f + 1/2 可以知道 f = 3/4

无论第一次分时，f大于3/4或小于3/4，玛丽都会得到更多的蛋糕。

补充：

1.之后，大厨玛蒂娜做了三块一模一样的长方形蛋糕，杰里米和玛丽都非常想吃。这次的分法发生了变化。杰里米还是负责切蛋糕，但是玛丽有两次先选择蛋糕的机会，而杰里米只有一次。也就是杰米里先切一块，由玛丽决定是否先选；杰米里再切第二块，玛丽决定是否进行先选，第三块依次。但是玛丽要留其中依次机会给杰米里先选择。

解析：

如果第一块时，杰米里先选的，那么他肯定选择大的一份，即f，后面两次只能让玛丽先选，因此后两块的分割方法就是评分。杰米里得到的蛋糕为 f + 1，而玛丽得到的为 1-f +1/2 + 1/2 = 2 – f

第一块玛丽先选，则她可以得到大份蛋糕f，而剩下的两块则与上面我们的分析相同。即杰米里最多可以分得5/4，玛丽可以得到 3/4

两种情况下：玛丽得到的分别是 2 – f 与 3/4 + f，要让玛丽得到的一样多，f = 11/8

杰米里可以得到 13/8

2.假设有7块一样的蛋糕，玛丽有6次先选蛋糕的机会，谁会有优势？优势有多少？

使用归纳分析方法：假设有k块蛋糕，玛丽有k-1次先选的机会。这种情况下，假设杰米里有A块的优势（也就说杰米里可以比玛丽多分k块中的A块蛋糕），那么在有k+1块蛋糕时，杰米里依旧占有优势。分为两种情况分析：

对于第k+1块蛋糕，如果玛丽先选，则杰米里可以将蛋糕分割为1/2 – A/4和1/2 + A/4。玛丽选1/2 + A/4，比杰米里可以多A/2 的蛋糕，这样在剩下的k块蛋糕中，杰米里可以多分A块。这样他比玛丽多分了A/2块。

如果玛丽后选，杰米里选择1/2 + A/4，剩下的k块蛋糕则全部被平分，杰米里依然多得到了A/2块蛋糕。

两块蛋糕时，杰米里比玛丽多1/2，三块时，比玛丽多1/4，依次可知当7块蛋糕时，可以比玛丽多分1/64。

3.假设总是让杰里米来切蛋糕，有没有办法确保两个小孩得到一样多的蛋糕？

除非每次都是玛丽先选蛋糕，否则没有办法实现两个小孩分得的蛋糕一样多。

题目2：拜占庭赌徒

受到假想的拜占庭阴谋启发，设置如下的赌局，称为“拜占庭赌徒”。

赌局规则：你和一群“顾问”一起参与赌局。其中一个顾问会在一张纸上写下0或者1，展示给其他顾问看，但不会让你看到，然后把那张纸扣着放在你的面前。随后每个顾问都会告诉你纸上写的是什么数字。他们都是演技精湛的人，因此你无法通过任何明显的面部表情或记号分别出他们是否在说谎。每一局，你都可以选择不下注，也可以压上你的部分甚至全部资产。

问题：假设一共有四位顾问，其中两个人会一直说实话，但是你不知道是那两位。你可以玩三局，每一局都用等额投注（压注多少，则赔多少）。赌局开始时，你有100美元，你能确保赢多少钱呢？

解析：如果四个顾问中，有3个或四个给你的建议相同，那么就在他们说的那个数字上压上最大的注。因为至少有两个人总说实话，因此三个人或四个人的建议相同，那么至少一个人的话是对的，因此稳赢。

如果每两个人给的建议是相同的，那么这局可以暂时不押注，第一局结束以后就知道了那两个顾问是说实话的，那么后面的两局中，可以将压最大注，这样两局中就可以得到400美元。

因此最少可以确保赢300美元。

补充：

1.假设现在只有三位顾问，而且只有一个人会一直说实话。你还是可以玩3局，每一局都采用等额投注。赌局开始时，你有100美元，你能确保赢多少钱呢？

分析方法类似上例：

如果三个人的答案相同，那么由于其中至少一个人会说真话，因此，可以押注最大值，肯定会赢。

如果两个人答案一样，这时分为两种情况：相同的两个人是说谎的两个顾问和相同的两个人一个是说谎的顾问，一个是诚实的顾问。

首先可以拿出x元，押注那答案相同的数字。如果输了，第一局结束则知道另外一个人就是说真话的了，那么剩下两局就可以得到4\*(100-x)美元。

如果赢了，则具有100+x美元；第二局如果这两个人的答案不同，可以先不下注，等一局，第二局结束则知道说实话的人，那么第三局时可以最终获得2\*(100 + x)。因此最少可以获得这个数字的钱，或更多。

让两种情况下得到的钱数相同：4\*（100-x）= 2\*（100+x），最终可知x=100/3。那么最终至少可以得到启动资金的8/3，也即266.66美元