程序员有趣的面试智力题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！
满足这两个条件的就是答案，下面来编写程序实现！

//原始数值: 0,1,2,3,4,5,6,7,8,9
//出现次数: 6,2,1,0,0,0,1,0,0,0
#include "iostream"
using namespace std;
#define len 10
class NumberTB
{
private:
    int top[len];
    int bottom[len];
    bool success;
public:
    NumberTB();
    int *getBottom();
    void setNextBottom();
    int getFrequecy(int num);
};
NumberTB::NumberTB()
{
    success = false;
    //format top
    for(int i = 0; i < len; i++)
    {
        top[i] = i;
    }
}
int *NumberTB::getBottom()
{
    int i = 0;
    while(!success)
    {
        i++;
        setNextBottom();
    }
    return bottom;
}
//set next bottom
void NumberTB::setNextBottom()
{
    bool reB = true;
    for(int i = 0; i < len; i++)
    {
        int frequecy = getFrequecy(i);
        if(bottom[i] != frequecy)
        {
            bottom[i] = frequecy;
            reB = false;
        }
    }
    success = reB;
}
//get frequency in bottom
int NumberTB::getFrequecy(int num) //此处的num 即指上排的数i
{
    int count = 0;
    for(int i = 0; i < len; i++)
    {
        if(bottom[i] == num)
            count++;
    }
    return count; //cout 即对应frequecy
}
int main(void)
{
    int i;
    NumberTB nTB;
    int *result = nTB.getBottom();
    cout<<"原始数值：";
    for(i=0;i<10;i++)
        cout<<i<<"  ";
    cout<<endl;
    cout<<"出现次数：";
    for(i = 0; i < len; i++)
    {
        cout << *result++ <<"  ";
    }
    cout<<endl;
    system("pause");
    return 0;
}