百度的一道面试题（5只蚂蚁爬木棍） - 编程论坛

#2

lintaoyn2010-11-10 11:25

打酱油是什么意思？

#3

kingsroot2010-11-10 12:44

程序代码：

#ifndef BRD_ANT_H
#define BRD_ANT_H

#include <stdint.h>

class Ant
{
    public:
        typedef enum tagDir
        {
            Right,
            Left
        }Dir;

    public:
        /*************************************
        *函数名:Ant
        *用途:构造函数
        *参数:无
        *输出:无
        *返回值:无
        **************************************/
        Ant( uint32_t AntID, uint32_t InitPosition, Dir InitDir );

        /*************************************
        *函数名:~Ant
        *用途:析构函数
        *参数:无
        *输出:无
        *返回值:无
        **************************************/
        ~Ant();

        /*************************************
        *函数名:DisPlay
        *用途:打印蚂蚁离开木杆的时间
        *参数:无
        *输出:无
        *返回值:无
        **************************************/
        void DisPlay( uint32_t Seconds );

        /*************************************
        *函数名:GetPosition
        *用途:获取当前的坐标
        *参数:无
        *输出:无
        *返回值:当前蚂蚁的位置
        **************************************/
        uint32_t GetPosition( void );

        /*************************************
        *函数名:MoveNext
        *用途:移动到下一个位置
        *参数:无
        *输出:无
        *返回值:无
        **************************************/
        void MoveNext( void );

        /*************************************
        *函数名:ChangeDir
        *用途:调换方向
        *参数:无
        *输出:无
        *返回值:无
        **************************************/
        void ChangeDir( void );

    private:
        /*************************************
        *函数名:++
        *用途:自增当前的坐标
        *参数:无
        *输出:无
        *返回值:当前蚂蚁对象引用
        **************************************/
        Ant& operator ++( void );

        /*************************************
        *函数名:--
        *用途:自减当前的坐标
        *参数:无
        *输出:无
        *返回值:当前蚂蚁对象引用
        **************************************/
        Ant& operator --( void );

    private:
        //当前坐标
        uint32_t     m_uiPosition;
        //方向
        Dir            m_eDiraction;
        //当前蚂蚁的ID
        uint32_t     m_uiAntID;
        //花费的时间
        uint32_t     m_uiSeconds;
        //标记是否已经完成任务
        bool        m_bOver;
};

#endif

#4

kingsroot2010-11-10 12:44

程序代码：

#include "ant.h"
#include <iostream>
#include <stdlib.h>

Ant::Ant( uint32_t AntID, uint32_t InitPosition, Dir InitDir )
{
    if( InitPosition >= 27 )
    {
        std::cerr << "The InitPosition error!\n Create intance error!\n The Program will exit!\n";
        exit( EXIT_FAILURE );
    }
    if( AntID > 5 )
    {
        std::cerr << "The AntID error!\n Create intance error!\n The Program will exit!\n";
        exit( EXIT_FAILURE );
    }

    m_uiPosition     = InitPosition;

    m_uiAntID        = AntID;

    m_eDiraction    = InitDir;

    m_uiSeconds        = 0;

    m_bOver            = false;

}

Ant::~Ant()
{

}

void Ant::DisPlay( uint32_t Seconds )
{
    if( !m_bOver )
    {
        std::cout << "The " << m_uiAntID << "'s ant has leave the pole" << "and cast time is "<< Seconds << std::endl;
    }
}

uint32_t Ant::GetPosition( void )
{
    return m_uiPosition;
}

void Ant::MoveNext( void )
{
    if( !m_bOver )
    {
        if( m_eDiraction == Right )
            ++(*this);
        else
            --(*this);
    }
}

void Ant::ChangeDir( void )
{
    if( !m_bOver )
    {
        if( m_eDiraction == Right )
        {
            m_eDiraction = Left;
        }
        else
        {
            m_eDiraction = Right;
        }
    }
}

Ant& Ant::operator ++( void )
{
    m_uiPosition++;
    if( m_uiPosition > 27 )
    {
        DisPlay( m_uiSeconds );
        m_bOver = true;
    }
    m_uiSeconds++;

    return *this;
}

Ant& Ant::operator --( void )
{
    m_uiPosition--;
    if( m_uiPosition <= 0 )
    {
        DisPlay( m_uiSeconds );
        m_bOver = true;
    }
    m_uiSeconds++;

    return *this;
}

#5

kingsroot2010-11-10 12:45

程序代码：

#include "ant.h"
#include <iostream>
#include <cstdlib>
#include <map>
#include <stdio.h>

int main( void )
{

    std::map< uint32_t, uint32_t > Clock;
    std::map< uint32_t, uint32_t >::iterator iter;

    for( uint32_t Temp = 1; Temp <= 27; Temp++ )
    {
        Clock.insert( std::pair< uint32_t, uint32_t >( Temp, 0 ));
    }

    Ant ant1( 1, 3,  Ant::Right );
    iter = Clock.find( 3 );
    (*iter).second = 1;

    Ant ant2( 2, 7,  Ant::Left  );
    iter = Clock.find( 7 );
    (*iter).second = 1;

    Ant ant3( 3, 11, Ant::Right );
    iter = Clock.find( 11 );
    (*iter).second = 1;

    Ant ant4( 4, 17, Ant::Left  );
    iter = Clock.find( 17 );
    (*iter).second = 1;

    Ant ant5( 5, 23, Ant::Left  );
    iter = Clock.find( 23 );
    (*iter).second = 1;

    while( true )
    {
        iter = Clock.find( ant1.GetPosition() );
        (*iter).second--;
        ant1.MoveNext();
        iter = Clock.find( ant1.GetPosition() );
        (*iter).second++;

        iter = Clock.find( ant2.GetPosition() );
        (*iter).second--;
        ant2.MoveNext();
        iter = Clock.find( ant2.GetPosition() );
        (*iter).second++;

        iter = Clock.find( ant3.GetPosition() );
        (*iter).second--;
        ant3.MoveNext();
        iter = Clock.find( ant3.GetPosition() );
        (*iter).second++;

        iter = Clock.find( ant4.GetPosition() );
        (*iter).second--;
        ant4.MoveNext();
        iter = Clock.find( ant4.GetPosition() );
        (*iter).second++;

        iter = Clock.find( ant5.GetPosition() );
        (*iter).second--;
        ant5.MoveNext();
        iter = Clock.find( ant5.GetPosition() );
        (*iter).second++;

        for( uint32_t Temp = 1; Temp <= 27; Temp++ )
        {
            iter = Clock.find( Temp );
            if( (*iter).second > 1 )
            {
                if( ant1.GetPosition() == (*iter).first )
                {
                    ant1.ChangeDir();
                }
                if( ant2.GetPosition() == (*iter).first )
                {
                    ant2.ChangeDir();
                }
                if( ant3.GetPosition() == (*iter).first )
                {
                    ant3.ChangeDir();
                }
                if( ant4.GetPosition() == (*iter).first )
                {
                    ant4.ChangeDir();
                }
                if( ant5.GetPosition() == (*iter).first )
                {
                    ant5.ChangeDir();
                }
            }
        }
        uint32_t Lable = 0;
        for( iter = Clock.begin(); iter != Clock.end(); iter++ )
        {
            Lable = Lable + (*iter).second;
        }
        if( Lable == 0 )
            break;
    }

    return EXIT_SUCCESS;

}

#6

kingsroot2010-11-10 12:47

希望对你有所帮助

#7

lintaoyn2010-11-10 13:18

程序代码：

#include<iostream>
using std::cout;
using std::endl;
using std::swap;
int left[29];
int right[29];
void fun()
{
    for(int i = 1; i != 29; ++i)
        if(left[i] && right[i])
            swap(left[i],right[i]);
}
void f()
{
    for(int i = 1; i != 29; ++i)
        if(left[i]&&right[i+1])
        {
            swap(left[i],right[i]);
            swap(left[i+1],right[i+1]);
        }
}
void move()
{
    for(int i = 1; i != 29; ++i)
    {
        left[i-1] = left[i];
        right[29-i] = right[29-1-i];
    }
}
int main()
{

    right[3]  = 1;
    right[11] = 2;
    left[7]   = 3;
    left[17]   = 4;
    left[23]  = 5;
    int count = 0;
    for(int i = 1; count != 5;++i )
    {
        fun();
        move();
        f();
        if(left[0] && ++count) cout << left[0] <<"号蚂蚁在第 "<<i<<" 秒爬出\n" ;
        if(right[28] && ++count) cout << right[28] <<"号蚂蚁在第 "<<i<<" 秒爬出\n" ;
    }
    return 0;
}

#8

lintaoyn2010-11-10 13:29

回复 6楼 kingsroot

我的没用到类，但是希望对你简化你的代码有帮助。
同一时刻，同一位置，不会有两只移动方向相同的蚂蚁。
void fun()这个函数用来处理经过一秒的移动后两只蚂蚁面碰面的情况。
void f()这个函数用来处理两只擦肩而过的蚂蚁。
希望对你有帮助~你的代码和变量命名让人看的清爽，羡慕中……

#9

kk9008002010-11-10 13:44

楼主不发布答案么？

#10

kingsroot2010-11-10 14:11

回复 8楼 lintaoyn

别人要求用类来处理！而且刚才看你程序出的结果好像不对！

#11

lintaoyn2010-11-10 14:58

回复 10楼 kingsroot

是么~可能咱们在什么才算爬出去的问题上有出入~我的结果比你多了一秒~我定义的“木棍的长度是29~~”

#12

kingsroot2010-11-10 15:37

回复 11楼 lintaoyn

蚂蚁可以从棍子2头爬出去哦！不是只限于一头哦

#13

lintaoyn2010-11-10 15:52

嗯…我错了，没写注释是我的错。学好英语单词

#14

ljt2010-11-10 18:26

回复 3楼 kingsroot

stdint.h这个还真的没见过，查了下还和vc6.0不兼容，要vs才行

#15

kingsroot2010-11-10 20:28

回复 14楼 ljt

我在Linux环境下的！！

#16

玩出来的代码2010-11-10 20:35

楼上各位写的没个说明的,看着累,有个思路也行的。
两个蚂蚁相撞时需要反向走,那就先判断那两个蚂蚁会相撞吧,
设置标志,向左走为0,向右走位1,设置首次相撞时的条件为,这对蚂蚁中第一个蚂蚁向右走,第二个向左走
并且在所有的符合向右向左走的蚂蚁对中之间的距离最短,
第一步先找符合方向的蚂蚁对计算之间的距离,找出距离最短的蚂蚁对,另外可能有不只一对的蚂蚁符合条件
也就是可能在同一时刻有两对蚂蚁相撞,那就得将他们都记录下来,设置一vector,记录符合情况的蚂蚁对中的第一个蚂蚁的信息
第二个就不用记录了,看程序，Mindist记录下最短距离

根据Mindist调整各个蚂蚁在木杆上的位置,若蚂蚁向左走则用自己当前的位置减去Mindist,若向右则加上Mindist，同时设置相撞的蚂蚁对的方向,取反就行了,其他的蚂蚁反向不变,这需要在上一步中vector的记录中查找,此时若有蚂蚁向左走走到了0,或向右走到了27,就将其dist设置为0下次就不用判断了,
虽然有个类的但只是对数据进行简单的封装,主要功能的事项还是在外面的函数中,也方便。
另外效率也是一个值得思考的问题
写的可能有点乱了，刚才写了一堆,不小心删了

重复上述步骤。大致就是这了，详细看代码吧。

#17

玩出来的代码2010-11-10 20:36

代码不见了。在贴下看看

程序代码：

#include<iostream>
#include<vector>
#include<string>
#include<functional>
#include<algorithm>
using namespace std;
class Ant
{
public:
    Ant(int _dist,bool _dirct)
    {
        dist=_dist;
        dirct=_dirct;
        time=0;
    }
    void ChangeValue(int i,bool j,int k)
    {
        dist+=i;
        dirct=!j;
        time+=k;
    }
    int& GetDist()
    {
        return dist;
    }
    bool GetDirct()
    {
        return dirct;
    }
    int& GetTime()
    {
        return time;
    }
public:
    static int totletime;    //所有蚂蚁离开木杆的时间，这个也可以没有
private:
    int dist;    //位置
    bool dirct;    //反向
    int time;    //离开木杆所用的时间

};
int Ant::totletime=0;

void Modify(vector<Ant>::iterator begin,int Mindist)
{
    if(begin->GetDist()<=0)
    {
        begin->GetTime()-=abs(begin->GetDist());
        begin->GetDist()=0;
    }
    else if(begin->GetDist()>=27)
    {
        begin->GetTime()-=(begin->GetDist()-27);
        begin->GetDist()=0;
    }
}

template<typename T>
class Myequal_to: public binary_function<T,T,bool>
{
public:
    bool operator()(const T& x,const T& y)const
    {
        return x==y;
    }
};

bool Solve(vector<Ant>::iterator first,vector<Ant>::iterator last)
{
    vector<Ant>::iterator old=first,begin=first;
    vector<vector<Ant>::iterator> iter;
    int Mindist=27,Mintmp;
    while(++first!=last)
    {
        Mintmp=28;//当距离不为0,第一个蚂蚁向由(为1),
        if(old->GetDist()!=0 && first->GetDist()!=0 && old->GetDirct() && !first->GetDirct())
        {
            Mintmp=abs(old->GetDist()-first->GetDist());
        }
        if(Mindist>=Mintmp)
        {
            if(Mindist==27 || Mindist==Mintmp)
            {
                iter.push_back(old);//第一次进入时,或有距离相同的蚂蚁对
            }
            else //若有距离最小的记录,清空先前的,重新设置
            {
                iter.clear();
                iter.push_back(old);
            }
            Mindist=Mintmp;
        }
        old=first;
    }
    if(Mindist!=0 && Mindist!=27)
    {
        Mindist>>=1;    //距离/2
        while(begin!=last)
        {
            if(begin->GetDist()==0)     //为0不处理
            {
                begin++;
                continue;
            }//在第一步中设置的vector中查找
            if(find_if(iter.begin(),iter.end(),bind2nd(Myequal_to<vector<Ant>::iterator>(),begin))==iter.end())
            {
                begin->ChangeValue(Mindist=begin->GetDirct()?abs(Mindist):-abs(Mindist),!begin->GetDirct(),abs(Mindist));
                Modify(begin,Mindist);
            }
            else
            {        //设置符合条件的蚂蚁对的第一个蚂蚁的信息
                begin->ChangeValue(abs(Mindist),begin->GetDirct(),abs(Mindist));
                Modify(begin,Mindist);
                begin++;//调整第二个蚂蚁的信息
                begin->ChangeValue(-abs(Mindist),begin->GetDirct(),abs(Mindist));
                Modify(begin,Mindist);
            }
            begin++;
        }
        Ant::totletime+=abs(Mindist);
        return true;
    }
    return false;
}

int GetMaxDist(vector<Ant>::iterator first,vector<Ant>::iterator last)
{
        //计算所有未走出木杆的蚂蚁走出木杆所需要的时间,此时个蚂蚁所对应的dist就是蚂蚁在木杆上的位置
    //并且不会再相撞了
    int LeftMax=0,RightMax=0;
    while(first!=last)
    {
        if(first->GetDist()!=0)
        {
            if(first->GetDirct()==0)
            {
                first->GetTime()+=first->GetDist();
                LeftMax=LeftMax<first->GetDist()?first->GetDist():LeftMax;
            }
            else
            {
                first->GetTime()+=27-first->GetDist();
                RightMax=RightMax<27-first->GetDist()?27-first->GetDist():RightMax;
            }
        }
        first++;
    }
    return LeftMax<RightMax?RightMax:LeftMax;
}

int main()
{
    vector<Ant> vec;
    int dist,dirct;
    for(int i=0;i<5;i++)//输入时按照从小到大输入
    {
        cin>>dist>>dirct;
        vec.push_back(Ant(dist,dirct));
    }
    while(1)
    {
        if(!Solve(vec.begin(),vec.end()))  //循环调用步骤1,2
            break;
    }
    cout<<Ant::totletime<<endl;
    Ant::totletime+=GetMaxDist(vec.begin(),vec.end());
    for(size_t j=0;j!=vec.size();j++)
    {
        cout<<vec[j].GetTime()<<' ';
    }
    cout<<Ant::totletime<<endl;
    return 0;
}

[ 本帖最后由玩出来的代码于 2010-11-10 20:38 编辑 ]

#18

longzhixuan2010-11-10 21:38

多谢各位啊！

#19

longzhixuan2010-11-10 21:42

再说声感谢各位，开始时弄的分少了，没有给上分的大侠，希望别介意！感谢给位！学习了！

#20

2010-11-14 18:49

回复 2楼 lintaoyn

打酱油就是路过

#21

2010-11-14 22:01

回复楼主 longzhixuan

能告诉我答案是多少吗？谢谢了

#22

Alar302010-11-15 10:49

俺来学习的。。。

#23

archerdang2010-11-16 12:10

只能从某一头出，还是两头都能出？？