百度的一道面试题(5只蚂蚁爬木棍)
有一根27厘米的细木杆,在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细,只能同时通过一只蚂蚁。开始时,蚂蚁的头向(右,左,右,左,左),它们只会朝前走或调头,但不会后退。当任意两只蚂蚁碰头时,两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。定义一个蚂蚁类Ant,编写程序,求所有蚂蚁都离开木杆的时间。注意:程序要有较详细的注释,用c++实现,要完整的程序,打酱油者免开尊口!
程序代码:#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
程序代码:#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;
}
程序代码:#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;
}
程序代码:#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;
}
