百度面试之蚂蚁爬杆

有一根27厘米的细木杆在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细不能同时通过一只蚂蚁。开始时蚂蚁的头朝左还是朝右是任意的它们只会朝前走或调头但不会后退。当任意两只蚂蚁碰头时两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。编写程序求所有蚂蚁都离开木杆的最小时间和最大时间。1. 创建C源代码文件 ant.cpp#includeiostream #includedeque using namespace std ; class AntInfo{ public: bool Orientation; //方向 int Position; //位置 }; dequeAntInfo AntDeque; //蚂蚁信息双头队列 const int Pos[5]{3,7,11,17,23}; //蚂蚁的初始位置 int Time[32]{0}; //共有32种情况存储每种情况的用时 int main(){ for(int i0; i32; i){ cout初始位置/方向: ; for(int j0; j5; j){ AntInfo Ant; Ant.PositionPos[j]; //初始位置赋值 Ant.Orientation(bool)(i(1j)); //初始方向赋值 AntDeque.push_front(Ant); // 5只蚂蚁信息依次压栈入双向列队 //打印5只蚂蚁初始位置和方向 coutPos[j]/; if(Ant.Orientation) cout右 ; else cout左 ; } while(!AntDeque.empty()){ Time[i]; //每一秒蚂蚁移动一厘米 dequeAntInfo::iterator Pointer; //指向deque容器的迭代器重载操作符同指针 for(PointerAntDeque.begin(); PointerAntDeque.end(); Pointer){ if(Pointer-Orientation) Pointer-Position; //向右移动位置递增 else Pointer-Position--; //向左移动位置递减 } //相邻蚂蚁位置相等表示相遇,相遇两蚂蚁均改变方向 for(PointerAntDeque.begin(); PointerAntDeque.end()-1; Pointer){ if(Pointer-Position(Pointer1)-Position){ Pointer-Orientation!Pointer-Orientation; //左蚂蚁变向 (Pointer1)-Orientation!(Pointer1)-Orientation; //右蚂蚁变向 } } //判断队列首尾蚂蚁是否到达端点剔除已经到达两端的蚂蚁 if(0AntDeque.back().Position) AntDeque.pop_back(); //到达0点出栈 if(27AntDeque.front().Position) AntDeque.pop_front(); //到达27点出栈 } //打印此种情况用时 cout 用时Time[i]秒endl; } //筛选出最大最小时间并打印 int maxTimeTime[0]; int minTimeTime[0]; for(int i 1; i32; i){ if(Time[i]maxTime) maxTimeTime[i]; if(Time[i]minTime) minTimeTime[i]; } cout\n最大用时maxTime秒endl最小用时minTime秒endl; return 0; //main返回 }2. Linux系统环境编译和运行2.1 如果安装gcc编译器在命令行终端运行编译链接命令g -O3 -Wall ant.cpp -o ant.elf2.2 如果安装clang编译器在命令行终端运行编译链接命令clang -O3 -Wall ant.cpp -o ant.elf2.3 命令行终端输入如下命令运行程序./ant.elf2.4 结果xyzxyz:/media/xyz/disk_e/Linux/posix_unix_api$ g -O3 -Wall ant.cpp -o ant.elf xyzxyz:/media/xyz/disk_e/Linux/posix_unix_api$ ./ant.elf 输出的每种结果如下: 初始方向左 左 左 左 左 用时23秒 初始方向右 左 左 左 左 用时24秒 初始方向左 右 左 左 左 用时23秒 初始方向右 右 左 左 左 用时24秒 初始方向左 左 右 左 左 用时23秒 初始方向右 左 右 左 左 用时24秒 初始方向左 右 右 左 左 用时23秒 初始方向右 右 右 左 左 用时24秒 初始方向左 左 左 右 左 用时23秒 初始方向右 左 左 右 左 用时24秒 初始方向左 右 左 右 左 用时23秒 初始方向右 右 左 右 左 用时24秒 初始方向左 左 右 右 左 用时23秒 初始方向右 左 右 右 左 用时24秒 初始方向左 右 右 右 左 用时23秒 初始方向右 右 右 右 左 用时24秒 初始方向左 左 左 左 右 用时17秒 初始方向右 左 左 左 右 用时24秒 初始方向左 右 左 左 右 用时20秒 初始方向右 右 左 左 右 用时24秒 初始方向左 左 右 左 右 用时17秒 初始方向右 左 右 左 右 用时24秒 初始方向左 右 右 左 右 用时20秒 初始方向右 右 右 左 右 用时24秒 初始方向左 左 左 右 右 用时11秒 初始方向右 左 左 右 右 用时24秒 初始方向左 右 左 右 右 用时20秒 初始方向右 右 左 右 右 用时24秒 初始方向左 左 右 右 右 用时16秒 初始方向右 左 右 右 右 用时24秒 初始方向左 右 右 右 右 用时20秒 初始方向右 右 右 右 右 用时24秒 最大用时24秒 最小用时11秒3. 总结3.1. 5只蚂蚁的方向排列组合共有32中情况方向的最简赋值方法依次取出0~31的所有整数的二进制位 Ant.Orientation(bool)(i (1j)) 3.2. 每过一秒判断两两相邻的蚂蚁位置是否相等确定蚂蚁是否相遇相遇的两只蚂蚁均改变方向3.3. 用双向队列deque首尾出栈的方法剔除掉到达木杆两端的蚂蚁直到双向队列为空记录的时间数是目标结果。