百度的一道面试题(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; }