标题:百度的一道面试题(5只蚂蚁爬木棍)
只看楼主
longzhixuan
Rank: 1
等 级:新手上路
帖 子:10
专家分:2
注 册:2010-10-8
结帖率:100%
已结贴  问题点数:20 回复次数:22 
百度的一道面试题(5只蚂蚁爬木棍)
  有一根27厘米的细木杆,在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细,只能同时通过一只蚂蚁。开始时,蚂蚁的头向(右,左,右,左,左),它们只会朝前走或调头,但不会后退。当任意两只蚂蚁碰头时,两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。定义一个蚂蚁类Ant,编写程序,求所有蚂蚁都离开木杆的时间。

   注意:程序要有较详细的注释,用c++实现,要完整的程序,打酱油者免开尊口!
搜索更多相关主题的帖子: 面试 蚂蚁 木棍 百度 
2010-11-09 20:05
lintaoyn
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:605
专家分:2489
注 册:2009-4-8
得分:0 
打酱油是什么意思?

迭代的是人,递归的是神。
2010-11-10 11:25
kingsroot
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:1
帖 子:284
专家分:1159
注 册:2010-3-28
得分:4 
程序代码:
#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
2010-11-10 12:44
kingsroot
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:1
帖 子:284
专家分:1159
注 册:2010-3-28
得分:4 
程序代码:
#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;
}
2010-11-10 12:44
kingsroot
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:1
帖 子:284
专家分:1159
注 册:2010-3-28
得分:4 
程序代码:
#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;
   
}
2010-11-10 12:45
kingsroot
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:1
帖 子:284
专家分:1159
注 册:2010-3-28
得分:0 
希望对你有所帮助
2010-11-10 12:47
lintaoyn
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:605
专家分:2489
注 册:2009-4-8
得分:4 
程序代码:
#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;
}

迭代的是人,递归的是神。
2010-11-10 13:18
lintaoyn
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:605
专家分:2489
注 册:2009-4-8
得分:0 
回复 6楼 kingsroot
我的没用到类,但是希望对你简化你的代码有帮助。
同一时刻,同一位置,不会有两只移动方向相同的蚂蚁。
void fun()这个函数用来处理经过一秒的移动后两只蚂蚁面碰面的情况。
void f()这个函数用来处理两只擦肩而过的蚂蚁。
希望对你有帮助~你的代码和变量命名让人看的清爽,羡慕中……

迭代的是人,递归的是神。
2010-11-10 13:29
kk900800
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2010-11-10
得分:0 
楼主不发布答案么?
2010-11-10 13:44
kingsroot
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:1
帖 子:284
专家分:1159
注 册:2010-3-28
得分:0 
回复 8楼 lintaoyn
别人要求用类来处理!而且刚才看你程序出的结果好像不对!
2010-11-10 14:11



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-325410-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 1.374869 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved