木杆上的蚂蚁问题
来源:一方有 责任编辑:栏目编辑 发表时间:2013-07-01 09:20 点击:次
有一根27厘米的细木杆,在第3厘米、7厘米、 11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。
木杆很细,不能同时通过一只蚂蚁。开始时,蚂蚁的头朝左还是朝右是任意的,它们只会朝前走或调头,
但不会后退。当任意两只蚂蚁碰头时,两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。
求所有蚂蚁都离开木杆的最小时间和最大时间。
输入木杆长度 L
输入蚂蚁的个数 n
输入每个蚂蚁在木杆上的位置 x1,x2……xn
输出所有蚂蚁离开木杆的最小时间和最大时间
下面是我解题的方法
- /*
- gcc test.c -o test
- ./test 27 5 3,7,11,17,23
- 假设只有两只蚂蚁A,B
- A在第3厘米a处,B在第7厘米b处
- 若是A,B相向而行,如
- 0 3 5 7 27
- +---+---+--+-------------------------------------------------+
- x a o b y
- A-> <-B
- 则A,B在第5厘米o处相遇后,同时调头朝反方向走
- 则A走过的路程为ao+ox=7
- 则B走过的路程为bo+oy=20
- 则A+B=ao+ox+bo+oy=(ao+oy)+(bo+ox)=ay+bx
- 发现
- 在任意两只蚂蚁碰头时,两只蚂蚁会同时调头朝反方向走情况下走过的总路程=在任意两只蚂蚁碰头时,两只蚂蚁会交换位置不转向往前走情况下走过的总路程
- 因此在计算最大最小时间时,可以忽略
- 任意两只蚂蚁碰头时,两只蚂蚁会同时调头朝反方向走的条件
- 时间最短时,A往离她最近的那头走,就是3,B往离她最近的那头走,就是7
- 时间最多时,A往离她最远的那头走,就是27-3,B往离她最远的那头走,就是27-7
- 当蚂蚁为n时,时间最短时,所有蚂蚁都离她最近的那头走,取出路程最大的那只蚂蚁,一般是中间那只
- 当蚂蚁为n时,时间最多时,所有蚂蚁都离她最远的那头走,取出路程最大的那只蚂蚁,一般是最靠近两头那只
- *系统环境:windows/linux
- *编译环境:gcc/vc++ 6.0
- *输入参数:多个参数时空格分隔
相关新闻>>
- 发表评论
-
- 最新评论 更多>>