面试笔试经典智力题解答.ppt

面试智力题解答 常见题目列表 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升水 intt 0 while t c Do fillA Do pourAB t t A if t B t t B Do emptyB Do pourAB 倒水问题 本题解答 5 6 3 Operabt A 5 B 6 FillA PourAB055FillA PourAB4610EmptyB PourAB044FillA PourAB369EmptyB PourAB033 success 倒水问题推广 也可以说是倒酒 有三个酒杯 其中两个大酒杯每个可以装8两酒 一个可以装3两酒 现在两个大酒杯都装满了酒 只用这三个杯子怎么把酒平均的分给4个人喝 倒水问题推广 Solution Tryandguess用一个三位数表示三个杯 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 歲數相加就等於隔離間屋的門牌號碼 普查員立刻走到隔鄰 看了一看 回來說 我還需要多少資料 女人回答 我