一道百度笔试题目

百度技术研发笔试题目

/*百度面试题

 * 有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。

 * 木杆很细，不能同时通过一只蚂蚁。开始 时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，

 * 但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。

#include <stdio.h>
#include <iostream>
using namespace std;
struct ant    {
    int isout;
    int postion;
    int direct;
};
struct ant ant[5];
#define STICK_LENGTH    27
void init_ant_postion(void)
{
    ant[0].postion = 3;
    ant[1].postion = 7;
    ant[2].postion = 11;
    ant[3].postion = 17;
    ant[4].postion = 23;
    int i = 0;
    for(i = 0;i < 5;i++)
        ant[i].isout = 0;
}
#define    DIRECTION_MASK 0x1
void init_ant_driect(int a)
{
    int i = 0;
    for(i = 0;i < 5;i++)
    {
        ant[i].direct = a&DIRECTION_MASK ? 1:-1;
        a >>= 1;
    }
}
void antisout(void)
{
    int i;
    for( i =0 ;i < 5;i++)
        if(ant[i].postion < 0 || ant[i].postion > 27)
            ant[i].isout =1;
}

int allout(void)
{
    int i ;
    for(i = 0; i < 5;i++)
        if(ant[i].isout == 0)
            return 0;
    return 1;
}
void swap(int *x, int* y)
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}
void ismeet(void)
{
    int i ;
    for( i = 0; i <=3;i++)
    {
        if(ant[i].isout == 0 && ant[i+1].isout == 0)
            if(ant[i].postion == ant[i+1].postion)
            {
                swap(&(ant[i].direct),&(ant[i+1].direct));
            }
    }
}
void walk(void)
{
    int i = 0;
    for(i = 0; i < 5;i++)
        ant[i].postion += ant[i].direct;
}
int ant_walk(void)
{
    int time = 0;//时间
    while(++time)
    {
        walk();//每一只蚂蚁走一步
        ismeet();//是否有两只蚂蚁相遇，如果相遇，那么掉头
        antisout();//是否有蚂蚁走出木棍，如果是，那么就修改isout标志位
        if(allout())//所有的蚂蚁是否离开木杆
            break;
    }
    return time;
}
int main(void)
{
    int min = 27,max = 0;
    for(int i = 0; i < 32;i++)//32 = 2^5
    {
        int time;
        init_ant_postion();
        init_ant_driect(i);
        time = ant_walk();
//        printf("%d\n",time);
        if(time < min)
            min =time;
        if(time > max)
            max = time;
    }
    printf("max = %d ,min = %d \n",max,min);
    return 0;
}

其实这道题目是一道智力题，因为所有的蚂蚁的速度是一样的，所以当两只蚂蚁相遇的时候

可以认为并没有掉头，而是相互擦肩而过，这样理解的话，就容易多了，所有的蚂蚁都是直线爬行的