面试常见智力题解

　　面试常见智力题解答
　　常见题目列表：
　　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个情形：将球编号112，分为14，58，912三堆
　　左14右58
　　若平衡，坏球在912，左13右911
　　若不平衡且58重，坏球18
　　左1，6，7，8右5，9，10，11
　　右重坏球是1或5
　　平衡坏球为24且比标准球轻
　　左重坏球在拿到左边的68且比标准球重
　　三种情形：再称一次得解
　　若不平衡且14重与上同理
　　称球问题
　　Solution：
　　13个球情形：解法类似，分为三组，14，58，912
　　左14右58
　　不平衡情形与12球同
　　平衡时左13右911
　　不平衡时与12球同，平衡时坏球在1213，左1右12
　　平衡，坏球13
　　不平衡，坏球12
　　注意：题目只需要找出重量不同的球即可
　　分金条问题
　　Description：
　　你让某些人为你工作了七天，你要用一根金条作为
　　报酬。这根金条要被分成七块。你必须在每天的活
　　干完后交给他们一块。如果你只能将这根金条切割
　　两次，你怎样给这些工人分？
　　分金条问题
　　Solution：
　　联想：二进制：1，2，4其中若干个的和可构成1，7中任
　　何一个数
　　17，27，47，第一天给17，第二天拿27换
　　17
　　猴子搬香蕉问题
　　Description：
　　一个小猴子边上有100根香蕉，它要走过50米才能
　　到家，每次它最多搬50根香蕉，每走1米就要吃掉
　　一根，请问它最多能把多少根香蕉搬到家里。
　　猴子搬香蕉问题
　　Solution：
　　猜想验证
　　猜想：
　　设小猴从0走到50，到A点时候他可以直接抱香蕉回家了，可
　　是到A点时候他至少消耗了3A的香蕉（到A，回0，到A），一个
　　限制就是小猴只能抱50只香蕉，那么在A点小猴最多49只
　　香蕉。1003A49，所以A17。这样折腾完到家的时候香蕉
　　剩1003A（50A）502A16。
　　验证：
　　以上为最优情形，只需验证这种情形可以达到即可
　　飞机加油问题
　　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）。。。
　　从中找出规律：
　　当剩余个数K3N2，N为自然数时，只要对手足够聪
　　明则必败。
　　当K3N1时，有必胜策略：取1个；
　　当K3N时，有必胜策略：取2个；
　　所以，当16个时，后取者有必胜策略。
　　倒水问题
　　经典形式：
　　“假设有一个池塘，里面有无穷多的水。现有2个
　　空水壶，容积分别为
　　5升和6升。问题是如何只用这2个水壶从池塘里取
　　得3升的水。”
　　倒水问题
　　Solution：
　　形式化倒水问题：无穷多水，容量a，b（b）的水壶
　　倒出c（b）升水。
　　结论：cgcd（a，b）0时有解，可用扩展的
　　Euclid定理加以证明：即存在整数x，y，使得
　　axbygcd（a，b）。
　　倒水问题
　　Solution：
　　通用解法：（容量A，B的水壶倒C升水）
　　intt0；
　　while（t！c）｛
　　Do（fillA），Do（pourAB）；
　　ttA；
　　if（B）｛
　　ttB；
　　Do（emptyB），Do（pourAB）；
　　｝
　　｝
　　倒水问题
　　本题解答（5，63）
　　O（A5，B6）
　　FillA，PourAB055
　　FillA，PourAB4610
　　EmptyB，PourAB044
　　FillA，PourAB369
　　EmptyB，PourAB033（success）
　　倒水问题推广
　　也可以说是倒酒：）有三个酒杯，其中两个大
　　酒杯每个可以装8两酒，一个可以装3两酒。现
　　在两个大酒杯都装满了酒，只用这三个杯子怎
　　么把酒平均的分给4个人喝？
　　倒水问题推广
　　Solution：
　　Tryandguess
　　用一个三位数表示三个杯，880，前两个为8升的杯
　　最后一个3升。开始：880853A喝掉3升变为：
　　850823B喝掉2升为：
　　803830533560263281A喝掉1升（A已经喝4
　　升完毕）为：
　　280253550523820802703730433460
　　163181CD各喝一升为：080053350323CD各
　　喝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；选出满足xyz36的组合；
　　条件二：知道三个人岁数之和后还是不能确定它们的年龄；
　　从上面的到的组合中找出xyz之和有相同的组合；
　　只有（9，2，2）13，（6，6，1）13
　　条件三：三个孩子中有一个年龄比其他两个大。符合条件的
　　组合只有（9，2，2）