12. 两个机器人，初始时位于数轴上的不同位置。给这两个机器人输入一段相同的程序，使得这两个机器人保证可以相遇。程序只能包含“左移n个单位”、“右移n个单位”，条件判断语句If，循环语句while，以及两个返回Boolean值的函数“在自己的起点处”和“在对方的起点处”。你不能使用其它的变量和计数器。
答案：两个机器人同时开始以单位速度右移，直到一个机器人走到另外一个机器人的起点处。然后，该机器人以双倍速度追赶对方。程序如下。
while(!at_other_robots_start) {
move_right 1
}
while(true) {
move_right 2
}
13. 如果叫你从下面两种游戏中选择一种，你选择哪一种？为什么？
a. 写下一句话。如果这句话为真，你将获得10美元；如果这句话为假，你获得的金钱将少于10美元或多于10美元（但不能恰好为10美元）。
b. 写下一句话。不管这句话的真假，你都会得到多于10美元的钱。
答案：选择第一种游戏，并写下“我既不会得到10美元，也不会得到10000000美元”。
14. 你在一幢100层大楼下，有21根电线线头标有数字1..21。这些电线一直延伸到大楼楼顶，楼顶的线头处标有字母A..U。你不知道下面的数字和上面的字母的对应关系。你有一个电池，一个灯泡，和许多很短的电线。如何只上下楼一次就能确定电线线头的对应关系？
答案：在下面把2,3连在一起，把4到6全连在一起，把7到10全连在一起，等等，这样你就把电线分成了6个“等价类”，大小分别为1, 2, 3, 4, 5, 6。然后到楼顶，测出哪根线和其它所有电线都不相连，哪些线和另外一根相连，哪些线和另外两根相连，等等，从而确定出字母A..U各属于哪个等价类。现在，把每个等价类中的第一个字母连在一起，形成一个大小为6的新等价类；再把后5个等价类中的第二个字母连在一起，形成一个大小为5的新等价类；以此类推。回到楼下，把新的等价类区别出来。这样，你就知道了每个数字对应了哪一个原等价类的第几个字母，从而解决问题。
15. 某种药方要求非常严格，你每天需要同时服用A、B两种药片各一颗，不能多也不能少。这种药非常贵，你不希望有任何一点的浪费。一天，你打开装药片A的药瓶，倒出一粒药片放在手心；然后打开另一个药瓶，但不小心倒出了两粒药片。现在，你手心上有一颗药片A，两颗药片B，并且你无法区别哪个是A，哪个是B。你如何才能严格遵循药方服用药片，并且不能有任何的浪费？
答案：把手上的三片药各自切成两半，分成两堆摆放。再取出一粒药片A，也把它切成两半，然后在每一堆里加上半片的A。现在，每一堆药片恰好包含两个半片的A和两个半片的B。一天服用其中一堆即可。
16. 你在一个飞船上，飞船上的计算机有n个处理器。突然，飞船受到外星激光武器的攻击，一些处理器被损坏了。你知道有超过一半的处理器仍然是好的。你可以向一个处理器询问另一个处理器是好的还是坏的。一个好的处理器总是说真话，一个坏的处理器总是说假话。用n-2次询问找出一个好的处理器。
答案：给处理器从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. 一个圆盘被涂上了黑白二色，两种颜色各占一个半圆。圆盘以一个未知的速度、按一个未知的方向旋转。你有一种特殊的相机可以让你即时观察到圆上的一个点的颜色。你需要多少个相机才能确定圆盘旋转的方向？
答案：你可以把两个相机放在圆盘上相近的两点，然后观察哪个点先变色。事实上，只需要一个相机就够了。控制相机绕圆盘中心顺时针移动，观察颜色多久变一次；然后让相机以相同的速度逆时针绕着圆盘中心移动，再次观察变色的频率。可以断定，变色频率较慢的那一次，相机的转动方向是和圆盘相同的。
再次一个沙发
13挺简单的，不过何必那么替别人着想呢？我的答案是“我获得不少于10^10美元，但偏偏不是10美元”。留个空间给bonus嘛……
15也不难，不过我的第一想法是，再取多一粒A丸，全部磨碎~~~分两次吃~~~后来也想到这个没那么暴力的方法……
14解答超有想法，我佩服……
12我后来终于终于想出来了……
16我的做法稍有不同，拿一个处理器问其他n-2个，答“好”的是同类，否则异类。由于超过一半是好的，这n-1个中，好的处理器>=坏的。如果n-2个回答中“好”“坏”数量不等，数量多的都是好的；否则剩下那个肯定是好的~~~
17……不满……题目没说明居然是可以连续观察的……
更正一下，应该是“如果回答’好’+1回答’坏’”，或者直接说“同类和异类数量不等”
82晓得我是哪个萨？
好久没在这里留过言了，实际上我ig都是订阅的泥这里的东西哈。
刚刚看了第一个，追及也算相遇，思维狭隘了。呵呵
好久没留言了，踩一下。
15题我第一反应也是全部磨碎。。。= =||||
楼层: 地下室 | 2008-4-27 15:56 | 叉烧妖 说：
15题我第一反应也是全部磨碎。。。= =||||
好方法,磨碎后放入水中,在放入一个A,搅拌均匀.第一次喝一半.
现在的公司都喜欢出这种脑筋急转弯.
遇到变态的考官,在面试的时候让你回答这类问题.
BS华为某考官.
感觉17题的摄像机采样频率要足够高才行
没找到留言的地方，就写这里吧：
1）在学习什么是数学了，果然是不错的书；
2）祝(gamma^(ln(3)*ln(Pi))/10+2008快乐！
15题真的对么？不是不能区分三粒么？那怎么保证6个半粒分开不会产生一堆有三个半粒B的情况？
@shepherd
一粒分开后分别放入两堆，每堆保证是1个A和0.5个B。
都是很棒的题目！
13的答案看不懂，这样回答是为了为难考官？
顶第14题！！！
和10楼的同问，怎么保证呢？
第12题：设n的初始值为1
一个循环体：左移n格；右移n+1格；每进入一次循环n递增2
每次移动后判断是否到达了另一个点的起始点，如返回1则停止。
这样的程序使得机器人在起点处左右震荡，幅度越来越大，直到先碰到对方起点的那个机器人停止，另外一个机器人返回的时候两个机器人就必然相遇。
“第12题：设n的初始值为1
一个循环体：左移n格；右移n+1格；每进入一次循环n递增2
每次移动后判断是否到达了另一个点的起始点，如返回1则停止。
这样的程序使得机器人在起点处左右震荡，幅度越来越大，直到先碰到对方起点的那个机器人停止，另外一个机器人返回的时候两个机器人就必然相遇。
”
这样不行吧，不能计数，你怎末“左移n格；右移n+1格”？？
15题显然错了……还是磨碎吧……
呃……没错……
对14题目无比的佩服…
14太棒了
14题我的想法是1，2一组，3，4一组这样两两一组，最后21肯定是单独的。上楼后可以找到21的单独，然后剩下的也可以把10组都找出来。把21的和10组里面的比如说X1组的1连起来，X1组的2和X2组的1连，X2组的2和X3组的1连，这样X10里面的2剩下。下楼后找到X10的2。可以推理出来X10的1，然后就可以推理出来X9的2，依次全部对应上。
这个推导过程和实际操作似乎更麻烦，但是普适性似乎比原答案广。
其实还有个更简单的方法，上楼前分成1，10，10三组，上楼后测出单独的1，和两个10，此时不知道上面的两个10和下面的两个10如何对应，上楼后单独的1，连接其中的一个10（比如A）中的第一个，然后A中第二个连接B中第一个，A中第三个连接B中第二个，以此类推。下楼后，单独的那个连接测量出来后，就能确定10和10之间的对应关系，然后根据每组的连接测出每一个的对应的关系
多于10元美金 又不能少于10元美金 矛盾至及
我解14有解法跟答案有点不同，现根据我的解法增加下题目的难度。
你在一幢100层大楼下，有21根电线线头标有数字1..21。这些电线一直延伸到大楼楼顶，楼顶的线头处标有字母A..U。你不知道下面的数字和上面的字母的对应关系。你有一个电池，一个灯泡，和24根短的电线。如何只上下楼一次就能确定电线线头的对应关系？
注：将原来的很多短电线改成只有24根
20根就够了，其实还有个更通俗的解法，博主的1，2，3，4，5，6，7解法只能适应总数为3，6，10，15，21，28….这个数列的解决方案，如果是22根呢，或者23，24根呢
其实只需要上楼前，分成1，2，2，2，2，…的等价类，上去后测出1根和2，2，2的等价类，然后将1和第一个2的其中一个相连，再将剩下的那个和第二个2中的一个相连，再将第二个2中剩下的和第三个2中的一个相连，以此类推，到楼下再测就可以了
其实还有个更简单的方法，只要12根线，上楼前分成1，10，10三组，上楼后测出单独的1，和两个10，此时不知道上面的两个10和下面的两个10如何对应，上楼后单独的1，连接其中的一个10（比如A）中的第一个，然后A中第二个连接B中第一个，A中第三个连接B中第二个，以此类推。下楼后，单独的那个连接测量出来后，就能确定10和10之间的对应关系，然后根据每组的连接测出每一个的对应的关系，上楼前需要两根线，上楼后需要10根线，总共12根
呃，23楼的解法完爆我25楼的题