蚂蚁爬木杆问题的算法思路

题目如下：

1. 有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。
2. 木杆很细，不能同时通过两只蚂蚁。
3. 开始时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，但不会后退。
4. 当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。
5. 假设蚂蚁们每秒钟可以走一厘米的距离。

编写程序，求所有蚂蚁都离开木杆 的最小时间和最大时间。

来个形象的小图：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
    _       _        _                 _                 _
    e       f        a                 b                 g
                     →                 ←

说这个趣味题是一个编程题，其实还不如说是个脑筋急转弯，刚看这个题的时候确实是一头雾水，5 只小蚂蚁，应该怎么考虑呢？写程序该从哪个点入手呢？！貌似写程序不是很容易啊~！

不过仔细地考虑一下就会发现：当 a 蚂蚁和 b 蚂蚁相碰的时候，发生了什么呢？“两只蚂蚁会同时调头朝反方向走”，而且“假设蚂蚁们每秒钟可以走一厘米的距离”，当两只蚂蚁都掉头以后，我们把 a 蚂蚁看成 b 蚂蚁，把 b 蚂蚁看成 a 蚂蚁，若不考虑它们的名字a，b，其实这和两只蚂蚁“擦肩而过”有什么区别呢？也就是说，蚂蚁的碰撞根本不会影响“宏观”上五只蚂蚁的运动情况。

最短的时间：根据示意图，求最短时间的话，e, f, a 三只蚂蚁都向左走，b, g 两只都向右走，进而只需看 a 和 b，a 和 b 哪个距离各自的端点更近呢？a 距离左端为 11，b 距离右端为 10，那么最短时间当然取决与 a 蚂蚁，也就是 11/1 = 11 秒。

最长的时间：根据示意图，最长时间取决于“谁”呢？当然是 e 蚂蚁，没有“谁”比它距离右端更远，所以最长时间即为：(27 - 3) = 24 秒。

C语言编程实现如下：

#include   
#include   
#include   
using std::cout;  
using std::endl;  
#define SLEN 27  
int getL(int ad)  
{  
    return abs(SLEN-ad)>ad ? abs(SLEN-ad) : ad;  
};  
int getS(int ad)  
{  
    return SLEN-getL(ad);  
};  
int main(void)  
{  
    int ads[]={3,7,11,17,23};  
    int L=0,S=0; //L保存最长时间；S保存最短时间  
    for(int i=0;i<5;++i)  
    {  
        if (L												
本文地址：http://www.nowamagic.net/librarys/veda/detail/235，欢迎访问原出处。