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

其实更像一个脑筋急转弯
服务器君一共花费了217.816 ms进行了5次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

题目如下:

  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 
*/  

本文地址:http://www.nowamagic.net/librarys/veda/detail/235,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/235

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《致加西亚的信》 阿尔伯特·哈伯德(Hubbard.E.) (作者), 赵立光 (译者), 艾柯 (译者)

《致加西亚的信(经典盒装版)》内容简介:美西战争爆发以后,美国必须立即与古巴起义军首领加西亚取得联系,并获得他的合作。但当时,加西亚身在古巴的深山里——没有人知道他的确切地点,所以没法与他取得联系。这时,有人向总统推荐一个名叫罗文的人,说他有办法找到加西亚,而且也只有他才能找得到。他们找来罗文,交给他一封写给加西亚的信。三周后,罗文徒步走过一个危机四伏的国家,最终把那封信交给了加西亚。 此后,罗文的事迹被传为佳话,“送信”成为了敬业、忠诚、勤奋的象征,罗文便成了每个领导都想找到的人和每个员工都应该学习和效仿的榜样。

更多计算机宝库...