笔试面试知识|程序员面试逻辑题解析笔记(一)

题目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美元

2.四轮赌局,四位顾问,其中3位可以随意说谎,另一位四次中必须至少3次说实话,在这种情况下,你能保证赢多少?
(暂略)
3.如果你可以参加5局,“不总说实话”的顾问5次中必须有四次说实话,另外三位可以随意说谎,这种情况下,你能保证最后至少还有150美元吗?
(暂略)


    推荐阅读