简明现代魔法 -> 计算机算法 -> 蚂蚁爬木杆问题的一点思考

蚂蚁爬木杆问题的一点思考

2010-10-19

题目如下:

  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 <iostream>  
#include <string>  
#include <cmath>  
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<getL(ads[i])) L=getL(ads[i]);  
        if (S<getS(ads[i])) S=getS(ads[i]);  
    };  
    cout<<"最长所需"<<L<<"秒。\n最短所需"<<S<<"秒。"<<endl;  
    return 0;  
}  
/* 
 输出: 
 最长所需24秒。 
 最短所需11秒。 
 Press any key to continue 
*/  
随机文章推荐
网站分类


注:如需转载本文,请注明出处(原文链接),谢谢。更多精彩内容,请进入简明现代魔法首页。

进入新博客
喜欢本文,就分享它吧
给我留言
您的名字:
您的邮件:
您的网站:


 

copyright © 2009 简明现代魔法    学习、分享、进步

power by Gonn 感谢所有关心和支持本站的朋友们