快好知 kuaihz订阅看过栏目大字版

 

 

面试常见智力题解

面试常见智力题解答

常见题目列表:

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:

倒推,从后往前推,人数依次增加

如果1-3号强盗都喂了鲨鱼,只剩4号和5号的

话,5号一定投反对票让4号喂鲨鱼,以独吞全部

金币。所以,4号惟有支持3号才能保命。3号知

道这一点,就会提(100,0,0)的分配方案,

对4号、5号一毛不拔而将全部金币归为已有,因

为他知道4号一无所获但还是会投赞成票,再加上

自己一票,他的方案即可通过。

海盗分金问题

Solution:

2号推知到3号的方案,就会提出(98,0,1,1)的

方案,即放弃3号,而给予4号和5号各一枚金币。由于该

方案对于4号和5号来说比在3号分配时更为有利,他们将

支持他而不希望他出局而由3号来分配。这样,2号将拿走

98枚金币。

2号的方案会被1号所洞悉,1号并将提出(97,0,1,

2,0)或(97,0,1,0,2)的方案,即放弃2号,

而给3号一枚金币,同时给4号(或5号)2枚金币。由于

1号的这一方案对于3号和4号(或5号)来说,相比2号

分配时更优,他们将投1号的赞成票,再加上1号自己的票,

1号的方案可获通过,97枚金币可轻松落入囊中。这无疑

是1号能够获取最大收益的方案了!

帽子/疯狗问题

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)

搜索建议:面试常见智力题解  题解  题解词条  智力  智力词条  面试  面试词条  常见  常见词条  面试常见智力题解词条  
求职

 ​面试24条小帖士

面试 是你整个求职过程中最重要的阶段。成败均决定于你 面试 时的短短一瞬间的表现。每个人都能够学会怎么出色地 面试 ,而且绝大多数的错误都可以预期并且避免,下面...(展开)

求职

 你工作怎么样?“还好/OK/还不...

你的工作怎么样?“还好/OK/还不错/还凑合/就那样啦……”,这样的对话是否很熟悉?我们中99%的人,都有着一份还可以的工作。我们朝九晚五,夜以继日。我们上班,...(展开)

求职

 简历制作的8条基本原则

不容忽略的简历制作的基本原则来源|有道词典小组 作者|mandolanzy简历,就是关于个人学历、经历、能力等的简要介绍。在英式美语中,简历以前多称为perso...(展开)