微软经典面试题：有人觉得网上这倒题给出的答案有问题不这道题出

[微软公司的运算题面试问题]★链接表和数组之间的区别是什么？ ★做一个链接表，你为什么要选择这样的方法？ ★选择一种算法来整理出一个链接表。你为什么要选择这种方法？现在用O(n)时间来做。 ★说说各种股...+阅读

微软经典面试题：有人觉得网上这倒题给出的答案有问题不这道题出

按月排3月4日 3月5日 3月8日 6月4日 6月7日 9月1日 9月5日 12月1日 12月2日 12月8日按日排9月1日 12月1日12月2日3月4日 6月4日3月5日 9月5日6月7日3月8日 12月8日分析：“小明说：如果我不知道的话，小强肯定也不知道”等同于：如果小强知道的话，小明肯定会知道。（逆否命题等价于原命题）即：如果小强知道，只有n=2或7，说明小明的m不是6就是12。“小强说：本来我也不知道，但是现在我知道了”小强本来不知道，说明小强n不是2也不是7，但他通过小明m=6或12，就能知道生日，说明小强n=4，即6月4日。（因为6月这组排除7日后只剩6月4日，而12月这组排除2日后还有12月1日和12月8日。）“小明说：哦，那我也知道了”通过小强能知道答案，小明也可以断定n=4，那么他也便知道生日了，也是6月4日。

...

微软经典面试题海盗分宝石 20分钟给出答案即可获得年薪8万美金的

反推过来想吧，进一步分析 5号：不同意，或者有条件同意轮到5号时，形成的状态是： 1得到0个宝石，死 2得到0个宝石，死 3得到0个宝石，死 4得到0个宝石，死 5得到100个宝石，活，同意此海盗是最后一个轮到，不存在生命危险，所以也没必要＂同意＂！除非有得到一定的好处但是他想捞到好处是很有难度的，因为其他海盗也很聪明！其实他当然也会意识到这点所以此海盗不会同意别人的方案，除非他获得一定的利益 4号：同意轮到4号时，形成的状态是： 1得到0个宝石，死 2得到0个宝石，死 3得到0个宝石，死 4得到0个宝石，可以保不死（但也说不定），同意 5得到100个宝石，活，同意（或不同意）此海盗最担心的是轮到他头上（祈祷中...），即使全部100个宝石奉送给5号，他才有可能保不死（仍然有风险），否则就死定了！（注意是超过半数同意才行，也就是说刚好达到半数还不够，否则就可以独吞了）所以此海盗不管如何都会同意别人的方案，否则对他来讲没有任何好处，反而增加步步逼近的危险！ 3号：不同意，或者有条件同意轮到3号时，形成的状态是： 1得到0个宝石，死 2得到0个宝石，死 3得到100个宝石，活，同意 4得到0个宝石，活，同意 5得到0个宝石，活，不同意轮到3号时，他是绝不会巴结5号的，因为不知道他需要多少＂度＂才会同意，要巴结的话只要给4号1个宝石就够了，但事实上一个都不用巴结，因为5号也会认识到这点，所以5号是绝对＂不同意＂的，介于5号＂不同意＂，4号也会猜想到这点，所以4号就不能再＂不同意＂，否则4号是自找死路，所以就固然有大于半数的支持者了但是能否轮到他呢？问题是这海盗太聪明了，事实上他进一步想，突然觉得不对，因为将不可能轮到他的，前面2号的海盗没那么傻，说不定他等下一个也得不到，所以在1号的方案时，他的要求变的很低了，＂求求1号给我1颗宝石吧，我会同意的＂....（这样也行$！$%^%&*^），哈哈：），早拿早好嘛，有一个算一个！所以此海盗肯定不同意别人的分配方案，除非有得到一点好处 2号：不同意轮到2号时，形成的状态是： 1得到0个宝石，死 2得到99个宝石，活，同意 3得到0个宝石，活，不同意 4得到0个宝石，活，同意 5得到1个宝石，活，同意要是轮到此海盗他必会拿走99颗宝石，然后给1颗5号即可！原因： 3号不同意的，因为他想要得到100个宝石的机会（如果给1个以上，或许会同意） 4号同意，否则只有坏处多多，有风险存在 5号给他1个宝石就OK了，否则到了下一轮，将一颗也得不到，不拿白不拿！所以此海盗不会同意1号的分配方案，除非给他100颗宝石其实不然，这都是错误的想法，怪就怪他们太聪明了！因为他知道1号很聪明的，他早已算出1号将会以99,0,1,0,0的分法搞定，所以轮不到他，想得到99颗的想法才是妄想，而且1号也不可能给他1-2颗宝石的，他知道1号要是这样做是在冒风险，所以他只有＂不同意＂一博 1号：此海盗当然也聪明了，他早已知道后面的海盗心里想什么，首先4号是一定同意了（因为不管哪一轮他都没有宝石，如果不早点同意的话说不定局势改变了，有风险啊），那么只要再找一个海盗同意即可安全了，左思右想，巴结谁呢？还用想...汗！ 2号肯定不给的，给了说不定也是白给 3号给1颗就能搞定，否则到了下一轮他一个也得不到 5号给1颗不一定够呀（除非给2颗，因为到了下一轮（2号决定时）他仍然有机会得到1颗宝石，所以5号干嘛急着同意呢，不急不急）最终结局的状态是： 1得到99个宝石，活，同意 2得到 0个宝石，活，不同意 3得到 1个宝石，活，同意 4得到 0个宝石，活，同意 5得到 0个宝石，活，不同意即：99,0,1,0,0 (1号利益最大化)

微软面试题一道很经典的希望解答

如果有一顶黑帽子，那么第一次关灯就会打自己，因为他看那别人都是白的，自己肯定是黑帽子。如果有2顶黑帽子，那么第二次关灯就会打自己，因为他看到别人只有一顶黑帽子，然而根据上面的推论，如果只有一顶黑帽子，则第一次就会打自己，所以自己也是黑帽子。如果有3顶黑帽子，那么第三次关灯就会打自己，道理同上。如果有n顶黑帽子，那么第n次关灯会打自己，数学归纳法。设有x个黑帽子。 x=1，则戴黑帽子的第一次就看到其他人都是白帽子，那么自己就肯定是黑帽子了。所以该打自己嘴巴。但第一次没人打，说明至少有两个黑帽子。 x=2，第一次开灯后否没人打，说明黑帽不止一个，所以第二次如果有人只看到别人只有一顶黑帽子的话，就能判断自己头上是黑帽子，就该打嘴巴，但没人打，说明至少有3个黑帽。

x=3，由于前两次没人打，所以至少三顶黑帽。第三次开灯后，有人打嘴巴，说明打嘴巴的人看到其他人只有两顶黑帽，所以能判断自己头上是黑帽。因此是三顶黑帽子。