[转]面试智力题(下)

12. 两个机器人,初始时位于数轴上的不同位置。给这两个机器人输入一段相同的程序,使得这两个机器人保证可以相遇。程序只能包含“左移n个单位”、“右移n个单位”,条件判断语句If,循环语句while,以及两个返回Boolean值的函数“在自己的起点处”和“在对方的起点处”。你不能使用其它的变量和计数器。

13. 如果叫你从下面两种游戏中选择一种,你选择哪一种?为什么?
a. 写下一句话。如果这句话为真,你将获得10美元;如果这句话为假,你获得的金钱将少于10美元或多于10美元(但不能恰好为10美元)。
b. 写下一句话。不管这句话的真假,你都会得到多于10美元的钱。


14. 你在一幢100层大楼下,有21根电线线头标有数字1..21。这些电线一直延伸到大楼楼顶,楼顶的线头处标有字母A..U。你不知道下面的数字和上面的字母的对应关系。你有一个电池,一个灯泡,和许多很短的电线。如何只上下楼一次就能确定电线线头的对应关系?
15. 某种药方要求非常严格,你每天需要同时服用A、B两种药片各一颗,不能多也不能少。这种药非常贵,你不希望有任何一点的浪费。一天,你打开装药片A的药瓶,倒出一粒药片放在手心;然后打开另一个药瓶,但不小心倒出了两粒药片。现在,你手心上有一颗药片A,两颗药片B,并且你无法区别哪个是A,哪个是B。你如何才能严格遵循药方服用药片,并且不能有任何的浪费?
16. 你在一个飞船上,飞船上的计算机有n个处理器。突然,飞船受到外星激光武器的攻击,一些处理器被损坏了。你知道有超过一半的处理器仍然是好的。你可以向一个处理器询问另一个处理器是好的还是坏的。一个好的处理器总是说真话,一个坏的处理器总是说假话。用n-2次询问找出一个好的处理器。
17. 一个圆盘被涂上了黑白二色,两种颜色各占一个半圆。圆盘以一个未知的速度、按一个未知的方向旋转。你有一种特殊的相机可以让你即时观察到圆上的一个点的颜色。你需要多少个相机才能确定圆盘旋转的方向?
 

 

 

 

 

 

 

 

 

 

 

 

 

答案:

12.  两个机器人同时开始以单位速度右移,直到一个机器人走到另外一个机器人的起点处。然后,该机器人以双倍速度追赶对方。程序如下。

while(!at_other_robots_start) {
move_right 1
}
while(true) {
move_right 2
}
13. 选择第一种游戏,并写下“我既不会得到10美元,也不会得到10000000美元”。

14. 在下面把2,3连在一起,把4到6全连在一起,把7到10全连在一起,等等,这样你就把电线分成了6个“等价类”,大小分别为1, 2, 3, 4, 5, 6。然后到楼顶,测出哪根线和其它所有电线都不相连,哪些线和另外一根相连,哪些线和另外两根相连,等等,从而确定出字母A..U各属于哪个等价类。现在,把每个等价类中的第一个字母连在一起,形成一个大小为6的新等价类;再把后5个等价类中的第二个字母连在一起,形成一个大小为5的新等价类;以此类推。回到楼下,把新的等价类区别出来。这样,你就知道了每个数字对应了哪一个原等价类的第几个字母,从而解决问题。

15. 把手上的三片药各自切成两半,分成两堆摆放。再取出一粒药片A,也把它切成两半,然后在每一堆里加上半片的A。现在,每一堆药片恰好包含两个半片的A和两个半片的B。一天服用其中一堆即可。

16. 给处理器从1到n标号。用符号a→b表示向标号为a的处理器询问处理器b是不是好的。首先问1→2,如果1说不是,就把他们俩都去掉(去掉了一个好的和一个坏的,则剩下的处理器中好的仍然过半),然后从3→4开始继续发问。如果1说2是好的,就继续问2→3,3→4,……直到某一次j说j+1是坏的,把j和j+1去掉,然后问j-1 → j+2;或者从j+2 → j+3开始发问,如果前面已经没有j-1了(之前已经被去掉过了)。注意到你始终维护着这样一个“链”,前面的每一个处理器都说后面那个是好的。这条链里的所有处理器要么都是好的,要么都是坏的。当这条链越来越长,剩下的处理器越来越少时,总有一个时候这条链超过了剩下的处理器的一半,此时可以肯定这条链里的所有处理器都是好的。或者,越来越多的处理器都被去掉了,链的长度依旧为0,而最后只剩下一个或两个处理器没被问过,那他们一定就是好的了。另外注意到,第一个处理器的好坏从来没被问过,仔细想想你会发现最后一个处理器的好坏也不可能被问到(一旦链长超过剩余处理器的一半,或者最后没被去掉的就只剩这一个了时,你就不问了),因此询问次数不会超过n-2。

17. 你可以把两个相机放在圆盘上相近的两点,然后观察哪个点先变色。事实上,只需要一个相机就够了。控制相机绕圆盘中心顺时针移动,观察颜色多久变一次;然后让相机以相同的速度逆时针绕着圆盘中心移动,再次观察变色的频率。可以断定,变色频率较慢的那一次,相机的转动方向是和圆盘相同的。

Leave a Reply

Your email address will not be published. Required fields are marked *