程序员有趣的面试智力题3

? 17、一个圆盘被涂上了黑白二色，两种颜色各占一个半圆。圆盘以一个未知的速度、按一个未知的方向旋转。你有一种特殊的相机可以让你即时观察到圆上的一个点的颜色。你需要多少个相机才能确定圆盘旋转的方向？
????? 答案：你可以把两个相机放在圆盘上相近的两点，然后观察哪个点先变色。事实上，只需要一个相机就够了。控制相机绕圆盘中心顺时针移动，观察颜色多久变一次；然后让相机以相同的速度逆时针绕着圆盘中心移动，再次观察变色的频率。可以断定，变色频率较慢的那一次，相机的转动方向是和圆盘相同的。

???? 18、有25匹马，速度都不同，但每匹马的速度都是定值。现在只有5条赛道，无法计时，即每赛一场最多只能知道5匹马的相对快慢。问最少赛几场可以找出25匹马中速度最快的前3名？（百度2008年面试题）

每匹马都至少要有一次参赛的机会，所以25匹马分成5组，一开始的这5场比赛是免不了的。接下来要找冠军也很容易，每一组的冠军在一起赛一场就行了（第6场）。最后就是要找第2和第3名。我们按照第6场比赛中得到的名次依次把它们在前5场比赛中所在的组命名为A、B、C、D、E。即：A组的冠军是第6场的第1名，B组的冠军是第6场的第2名……每一组的5匹马按照他们已经赛出的成绩从快到慢编号：

A组：1，2，3，4，5
B组：1，2，3，4，5
C组：1，2，3，4，5
D组：1，2，3，4，5
E组：1，2，3，4，5

从现在所得到的信息，我们可以知道哪些马已经被排除在3名以外。只要已经能确定有3匹或3匹以上的马比这匹马快，那么它就已经被淘汰了。可以看到，只有上表中粗体的那5匹马是有可能为2、3名的。即：A组的2、3名；B组的1、2名，C组的第1名。取这5匹马进行第7场比赛，第7场比赛的前两名就是25匹马中的2、3名。故一共最少要赛7场。

这道题有一些变体，比如64匹马找前4名。方法是一样的，在得出第1名以后寻找后3名的候选竞争者就可以了。

????? 19、题目如下：
? 0 1 2 3 4 5 6 7 8 9
? _ _ _ _ _ _ _ _ _ _

在横线上填写数字，使之符合要求。
要求如下：对应的数字下填入的数，代表上面的数在下面出现的次数，比如3下面是1，代表3要在下面出现一次。

正确答案是：0 1 2 3 4 5 6 7 8 9
???????????????????????6 2 1 0 0 0 1 0 0 0

我的思路是：因为第二行的数字是第一行的数在下面出现的次数，下面10个格子，总共10次。。。所以第2排数字之和为10。

首先从0入手，先填9，肯定不可能，9下面要是1，只剩8个位填0，不够填8，8下面要填1，1要至少填2，后面不用再想，因为已经剩下7个位置，不够填0……如此类推。到0下面填6的时候就得到我上面的答案了。。

其实可以推出这个题目的两个关键条件：
1、第2排数字之和为10。
2、两排数字上下相乘之和也是10！
满足这两个条件的就是答案，下面来编写程序实现！