您现在的位置:计算机技术学习网 > 技术中心 > 编程开发 > C >

木杆上的蚂蚁问题

来源:一方有 责任编辑:栏目编辑 发表时间:2013-07-01 09:20 点击:

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


输入木杆长度 L
输入蚂蚁的个数 n
输入每个蚂蚁在木杆上的位置 x1,x2……xn
输出所有蚂蚁离开木杆的最小时间和最大时间

下面是我解题的方法

 

  1. /*  
  2. gcc test.c -o test  
  3. ./test 27 5 3,7,11,17,23  
  4.  
  5. 假设只有两只蚂蚁A,B  
  6. A在第3厘米a处,B在第7厘米b处  
  7.  
  8.  
  9. 若是A,B相向而行,如  
  10. 0   3   5  7                                                 27   
  11. +---+---+--+-------------------------------------------------+  
  12. x   a   o  b                                                 y  
  13.     A->  <-B  
  14.  
  15. 则A,B在第5厘米o处相遇后,同时调头朝反方向走  
  16. 则A走过的路程为ao+ox=7  
  17. 则B走过的路程为bo+oy=20  
  18. 则A+B=ao+ox+bo+oy=(ao+oy)+(bo+ox)=ay+bx  
  19. 发现  
  20. 在任意两只蚂蚁碰头时,两只蚂蚁会同时调头朝反方向走情况下走过的总路程=在任意两只蚂蚁碰头时,两只蚂蚁会交换位置不转向往前走情况下走过的总路程  
  21. 因此在计算最大最小时间时,可以忽略  
  22. 任意两只蚂蚁碰头时,两只蚂蚁会同时调头朝反方向走的条件  
  23. 时间最短时,A往离她最近的那头走,就是3,B往离她最近的那头走,就是7  
  24. 时间最多时,A往离她最远的那头走,就是27-3,B往离她最远的那头走,就是27-7  
  25.  
  26. 当蚂蚁为n时,时间最短时,所有蚂蚁都离她最近的那头走,取出路程最大的那只蚂蚁,一般是中间那只  
  27. 当蚂蚁为n时,时间最多时,所有蚂蚁都离她最远的那头走,取出路程最大的那只蚂蚁,一般是最靠近两头那只  
  28.  
  29. *系统环境:windows/linux  
  30. *编译环境:gcc/vc++ 6.0  
  31. *输入参数:多个参数时空格分隔  

    相关新闻>>

      发表评论
      请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
      用户名: 验证码:点击我更换图片
      最新评论 更多>>
      网站首页 - 友情链接 - 网站地图 - TAG标签 - RSS订阅 - 内容搜索
      Copyright © 2008-2015 计算机技术学习交流网. 版权所有

      豫ICP备11007008号-1