面试常见智力题解

　　面试常见智力题解答
　　常见题目列表：
　　1.海盗分金问题
　　2.帽子/疯狗问题
　　3.称球问题
　　4.分金条问题
　　5.猴子搬香蕉问题
　　6.飞机加油问题
　　7.硬币游戏
　　8.倒水问题
　　9.帽子问题
　　10.年龄问题
　　海盗分金问题
　　Description:
　　传说，从前有五个海盗抢得了100枚金币.他们通过了一个如
　　何确定选用谁的分配方案的安排.即：
　　1.抽签决定各人的号码（1，2，3，4，5）；
　　2.先由1号提出分配方案，然后5个人表决.当且仅当超过半数
　　人同意时，方案才算被通过，否则他将被扔入大海喂鲨鱼；
　　3.当1号死后，再由2号提方案，4个人表决，当且仅当超过
　　半数同意时，方案才算通过，否则2号同样将被扔入大海喂
　　鲨鱼；
　　4.往下依次类推……
　　根据上面的这个故事，现在提出如下的一个问题.即：
　　我们假定每个海盗都是很聪明的人，并且都能够很理智地判
　　断自己的得失，从而做出最佳的选择，那么第一个海盗应当
　　提出怎样的分配方案才能够使自己不被扔入大海喂鲨鱼，而
　　且收益还能达到最大化呢？
　　海盗分金问题
　　Solution:
　　倒推，从后往前推，人数依次增加
　　如果１－３号强盗都喂了鲨鱼，只剩４号和５号的
　　话，５号一定投反对票让４号喂鲨鱼，以独吞全部
　　金币。所以，４号惟有支持３号才能保命。３号知
　　道这一点，就会提（１００，０，０）的分配方案，
　　对４号、５号一毛不拔而将全部金币归为已有，因
　　为他知道４号一无所获但还是会投赞成票，再加上
　　自己一票，他的方案即可通过。
　　海盗分金问题
　　Solution:
　　２号推知到３号的方案，就会提出（９８，０，１，１）的
　　方案，即放弃３号，而给予４号和５号各一枚金币。由于该
　　方案对于４号和５号来说比在３号分配时更为有利，他们将
　　支持他而不希望他出局而由３号来分配。这样，２号将拿走
　　９８枚金币。
　　２号的方案会被１号所洞悉，１号并将提出（９７，０，１，
　　２，０）或（９７，０，１，０，２）的方案，即放弃２号，
　　而给３号一枚金币，同时给４号（或５号）２枚金币。由于
　　１号的这一方案对于３号和４号（或５号）来说，相比２号
　　分配时更优，他们将投１号的赞成票，再加上１号自己的票，
　　１号的方案可获通过，９７枚金币可轻松落入囊中。这无疑
　　是１号能够获取最大收益的方案了！
　　帽子/疯狗问题
　　Description:
　　一群人开舞会，每人头上都戴着一顶帽子。帽子只
　　有黑白两种，黑的至少有一顶。每个人都能看到其
　　他人帽子的颜色，却不知自己的。主持人先让大家
　　看看别人头上戴的什么帽子，然后关灯，如果有人
　　认为自己戴的是黑帽子，就打自己一个耳光。第一
　　次关灯，没有声音。于是再开灯，大家再看一遍，
　　关灯时仍然鸦雀无声。一直到第三次关灯，才有劈
　　劈啪啪打耳光的声音响起。问有多少人戴着黑帽子？
　　帽子/疯狗问题
　　Solution:
　　递推归纳
　　假如只有一个人戴黑帽子，那他看到所有人都戴白
　　帽，在第一次关灯时就应自打耳光，所以应该不止
　　一个人戴黑帽子；如果有两顶黑帽子，第一次两人
　　都只看到对方头上的黑帽子，不敢确定自己的颜色，
　　但到第二次关灯，这两人应该明白，如果自己戴着
　　白帽，那对方早在上一次就应打耳光了，因此自己
　　戴的也是黑帽子―――于是也会有耳光响起；可事
　　实是第三次才响起耳光声，说明全场不止两顶黑帽，
　　依此类推，应该是关几次灯，有几顶黑帽。
　　称球问题
　　Description:
　　一共12个一样的小球， 其中只有一个重量与其它
　　不一样(未知轻重)，给你一个天平， 只称三次， 找
　　出那个不同重量的球？
　　如果一共13个一样的小球， 其中只有一个重量与
　　其它不一样(未知轻重)，给你一个天平， 只称三次，
　　找出那个不同重量的球？
　　称球问题
　　Solution:
　　充分利用所有信息
　　12个情形:将球编号1~12，分为1-4,5-8,9-12三堆
　　左1-4－右5-8
　　若平衡，坏球在9-12,左1-3－右9-11
　　若不平衡且5-8重，坏球1-8
　　左1,6,7,8－右5,9,10,11
　　右重->坏球是1或5
　　平衡->坏球为2-4且比标准球轻
　　左重->坏球在拿到左边的6-8且比标准球重
　　三种情形：再称一次得解
　　若不平衡且1-4重与上同理
　　称球问题
　　Solution:
　　13个球情形：解法类似 ,分为三组,1-4,5-8,9-12
　　左1-4－右5-8
　　不平衡情形与12球同
　　平衡时左1-3－右9-11
　　不平衡时与12球同，平衡时坏球在12/13，左1－右12
　　平衡，坏球13
　　不平衡,坏球12
　　注意：题目只需要找出重量不同的球即可
　　分金条问题
　　Description:
　　你让某些人为你工作了七天， 你要用一根金条作为
　　报酬。这根金条要被分成七块。你必须在每天的活
　　干完后交给他们一块。如果你只能将这根金条切割
　　两次，你怎样给这些工人分？
　　分金条问题
　　Solution:
　　联想：二进制:1,2,4其中若干个的和可构成1,7中任
　　何一个数
　　1/7，2/7，4/7，第一天给1/7，第二天拿2/7换
　　1/7………………
　　猴子搬香蕉问题
　　Description:
　　一个小猴子边上有100根香蕉，它要走过50米才能
　　到家，每次它最多搬50根香蕉，每走1米就要吃掉
　　一根，请问它最多能把多少根香蕉搬到家里。
　　猴子搬香蕉问题
　　Solution:
　　猜想＋验证
　　猜想：
　　设小猴从0走到50,到A点时候他可以直接抱香蕉回家了,可
　　是到A点时候他至少消耗了3A的香蕉(到A,回0,到A),一个
　　限制就是小猴只能抱50只香蕉,那么在A点小猴最多49只
　　香蕉.100-3A=49,所以A=17. 这样折腾完到家的时候香蕉
　　剩100-3A-(50-A)=50-2A=16.
　　验证:
　　以上为最优情形，只需验证这种情形可以达到即可
　　飞机加油问题
　　Description:
　　每个飞机只有一个油箱， 飞机之间可以相互加油
　　（注意是相互，没有加油机） 一箱油可供一架飞机
　　绕地球飞半圈。
　　为使至少一架飞机绕地球一圈回到起飞时的飞机场，
　　至少需要出动几架飞机？（所有飞机从同一机场起
　　飞，而且必须安全返回机场，不允许中途降落，中
　　间没有飞机场）
　　飞机加油问题
　　Solution:
　　猜想+验证
　　猜想：
　　至少需要出动5 架飞机。思路是这样的，一架飞机要想完
　　成绕地球一周的飞行，至少需要别的飞机给它提供1 箱油。
　　最划算的办法显然是，派飞机和它结伴飞行前四分之一周
　　以及后四分之一周，（因为这两段路程距离基地近所花代
　　价小。）由它独立飞行中间的半程。必须保证两个加油点，
　　前四分之一处，加满，后四分之一点，及时补充。那么必
　　须有两架飞机与目标机结伴飞行四分之一周，这两架飞机
　　需要做折返飞行，正好花费2 箱油。所以补充油的任务实
　　际上该由另外两架飞机完成。这两架飞机飞八分之一周，
　　做折返飞，正好富余1 箱油。因此，5 架飞机刚好完成任
　　务。到了此时，问题只考虑了一半。能够提供多少油并不
　　意味着就能够全部接受，受到结伴飞行的距离，即腾出的
　　油箱空间所限制。而以下做法正好可以满足此条件。
　　飞机加油问题
　　Solution:
　　验证:
　　3 架飞机同时从机场出发，飞行八分之一周，各耗油四分
　　之一。此时某架飞机给其余两架补满油，自己返回基地。
　　另一机和目标机结伴，飞至四分之一周，给目标机补满油，
　　自己返回。目标机独自飞行半周，与从基地反向出发的一
　　机相遇，2 机将油平分，飞至最后八分之一处，与从基地
　　反向出发的另一机相遇，各分四分之一油，返回。
　　硬币游戏
　　Description:
　　16个硬币，A和B轮流拿走一些，每次拿走的个数
　　只能是1，2，4中的一个数。
　　谁最后拿硬币谁输。
　　问：A或B有无策略保证自己赢？
　　硬币游戏
　　Solution:
　　博弈类问题，分清两概念
　　必胜态：有一种方法导致下一状态为必败态
　　必败态：每一种方法导致下一状态为必胜态
　　解决办法：递推
　　1:必败
　　2:必胜：取1，导致变为1状态(必败)
　　3:必胜：取2->必败态
　　4:必败：取1或2或4均导致必败态或直接失败
　　以些类推知16为必败态，即后手必胜
　　硬币游戏
　　Solution(Ⅱ):
　　剩2个时,取1个必胜;
　　剩3个时,取2个必胜;
　　剩4个时,如果对手足够聪明则必败;
　　剩5个时,去1个必胜...
　　记作 2(1) 3(2) 4(x) 5(1) 6(2) 7(x) 8(1) ...
　　从中找出规律:
　　当剩余个数K=3N-2,N为自然数时,只要对手足够聪
　　明则必败.
　　当K=3N-1时,有必胜策略: 取1个;
　　当K=3N时,有必胜策略:取2个;
　　所以,当16个时,后取者有必胜策略.
　　倒水问题
　　经典形式：
　　＂假设有一个池塘，里面有无穷多的水。现有2个
　　空水壶，容积分别为
　　5升和6升。问题是如何只用这2个水壶从池塘里取
　　得3升的水。＂
　　倒水问题
　　Solution:
　　形式化倒水问题：无穷多水，容量a,b(a<=b)的水壶
　　倒出c(c<=b)升水。
　　结论：c%gcd(a,b) == 0 时有解，可用扩展的
　　Euclid定理加以证明：即存在整数x,y，使得
　　ax+by=gcd(a,b).
　　倒水问题
　　Solution:
　　通用解法:(容量A,B的水壶倒C升水)
　　int t = 0;
　　while(t != c){
　　Do(fill A),Do(pour A B);
　　t = t+A;
　　if(t >= B){
　　t = t – B;
　　Do(empty B), Do(pour A B);
　　}
　　}
　　倒水问题
　　本题解答(5,6->3)
　　Oper a b t (A=5,B=6)
　　Fill A, Pour A B 0 5 5
　　Fill A, Pour A B 4 6 10
　　Empty B, Pour A B 0 4 4
　　Fill A, Pour A B 3 6 9
　　Empty B, Pour A B 0 3 3 (success)
　　倒水问题推广
　　也可以说是倒酒：）有三个酒杯，其中两个大
　　酒杯每个可以装8两酒，一个可以装3两酒。现
　　在两个大酒杯都装满了酒，只用这三个杯子怎
　　么把酒平均的分给4个人喝？
　　倒水问题推广
　　Solution:
　　Try and guess
　　用一个三位数表示三个杯，880，前两个为8升的杯
　　最后一个3升。开始：880_853A喝掉3升变为：
　　850_823_B喝掉2升为：
　　803_830_533_560_263_281A喝掉1升(A已经喝4
　　升完毕）为：
　　280_253_550_523_820_802_703_730_433_460_
　　163_181CD各喝一升为：080_053_350_323CD各
　　喝3升B喝2升，分水结束，ABCD四人各喝4升。
　　帽子问题
　　Description:
　　有一个牢房，有3个犯人关在其中。因为玻璃很厚，所以3个
　　人只能互相看见，不能听到对方说话的声音。＂
　　有一天，国王想了一个办法，给他们每个人头上都戴了一
　　顶帽子，只叫他们知道帽子的颜色不是白的就是黑的，不叫
　　他们知道自己所戴帽子的是什么颜色的。在这种情况下，国
　　王宣布两条如下：
　　1．谁能看到其他两个犯人戴的都是白帽子，就可以释放
　　谁；
　　2．谁知道自己戴的是黑帽子，就释放谁。
　　其实，国王给他们戴的都是黑帽子。他们因为被绑，看不
　　见自己罢了。于是他们3个人互相盯着不说话。可是不久，
　　心眼灵的A用推理的方法，认定自己戴的是黑帽子。您想，
　　他是怎样推断的
　　帽子问题
　　Solution:
　　逻辑学，假设思维
　　现在假设3个犯人是A、B和我
　　那么我的推断是：
　　第一种：我戴的是白帽子
　　那么A会这么想：如果自己戴的是白帽子，那么B就会看到2
　　个白帽子，那么他根据国王的第一条就马上会被释放，但是
　　B现在没有被释放，说明我戴的不是白的，是黑的，哈哈，
　　我知道自己是黑的拉，我可以要求国王释放我拉
　　结论：如果我戴的是白帽子，那么根据A犯人的想法得出：A
　　和B必然有一个会被释放，但是现在2个人都没有被释放，所
　　以我一定不是白的，而是黑的，所以我会知道自己是黑的，
　　要求国王释放我，这样，我就被放了
　　同理，A和B根据别人的想法也都算出自己是黑帽子，这样3
　　个犯人同时被释放
　　年龄问题
　　Description:
　　一普查員問一女人,＂你有多少個孩子,他們多少歲＂
　　女人回答:＂我有三個孩子,他們的歲數相乘是36,歲數
　　相加就等於隔離間屋的門牌號碼.＂普查員立刻走到
　　隔鄰,看了一看,回來說:＂我還需要多少資料.＂女人回
　　答:＂我現在很忙,我最大的孩子正在樓上睡覺.＂普查
　　員說:＂謝謝,我己知道了
　　問題:那三個孩子的歲數是多少。
　　年龄问题
　　Solution:
　　9，2，2
　　分析，设三个人的年龄组成自然数组合(x,y,z)，一共三个条
　　件，
　　条件一：三个人岁数乘起来为36；选出满足x*y*z=36的组合;
　　条件二：知道三个人岁数之和后还是不能确定它们的年龄；
　　从上面的到的组合中找出xyz之和有相同的组合；
　　只有 (9,2,2)=13,(6,6,1)=13
　　条件三：三个孩子中有一个年龄比其他两个大。符合条件的
　　组合只有(9，2，2)