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

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

题目如下:

  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本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

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

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

《代码整洁之道》 马丁(Robert C. Martin) (作者), 韩磊 (译者)

软件质量,不但依赖于架构及项目管理,而且与代码质量紧密相关。这一点,无论是敏捷开发流派还是传统开发流派,都不得不承认。《代码整洁之道》提出一种观念:代码质量与其整洁度成正比。干净的代码,既在质量上较为可靠,也为后期维护、升级奠定了良好基础。作为编程领域的佼佼者,《代码整洁之道》作者给出了一系列行之有效的整洁代码操作实践。这些实践在《代码整洁之道》中体现为一条条规则(或称“启示”),并辅以来自现实项目的正、反两面的范例。只要遵循这些规则,就能编写出干净的代码,从而有效提升代码质量。

更多计算机宝库...