蚂蚁爬杆

noski

<P>&nbsp;</P>
<P>有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细，不能同时通过两只蚂蚁。开始时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。求所有蚂蚁都离开木杆的最短时间和最长时间，以及每种情况它们的头都是朝向什么方向的。</P>
<P>&nbsp;</P>
<P>＝＝＝＝＝＝＝＝＝＝</P>
<P>PS：这道题是我看《编程之美》时看到的一道题，觉得思路很巧妙，于是就发出来让大家欣赏一下。有什么好思路，或者后绪问题，欢迎讨论。。</P>

gozichen

穷举法好象太累了，noski说的思路巧妙，我估计是用镜向的原理，把两个蚂蚁碰头掉头可以看成它们互相穿过沿着不变的方向继续走。<BR>
这样的话，最长时间实际上就是看最远那只蚂蚁了。<BR>
不知道对不对

gozichen

还要算头朝向就有点头疼了

veteranhit

说得很对啊，只要3厘米处的蚂蚁向24厘米的路径走，不用管其他蚂蚁的朝向啊，最长时间为24秒。不过时间最短需要大家都往最短的路径上运动，数11厘米的耗时，最短也得11秒。不知道对不对，大家继续讨论。

魔鱼儿

哪位强人能来详细的解释一下啊,

kexin_xiao

蚂蚁是相同的，当两只蚂蚁碰撞，他们同时转向，以相同速率、相反方向继续爬行可以看成两只蚂蚁以原速率前进，互不干涉。实际上，问题就变成了5只蚂蚁，一部分向杆一段爬行，另一部分向另一端爬行，什么时候木棍上一只蚂蚁都不剩。

kexin_xiao

<P>最小时间肯定大家都很容易就想到了, 就是蚂蚁们分别向左或向右走, 其中在11厘米处的蚂蚁应该向左走比较近, 所以最小时间就是中间的蚂蚁向0处走出杆的时间, 也就是11秒。</P>
<P>最大时间，如果用穷举，一共只有2^5=32种情况，有点麻烦。简单地说，按照我6楼的说法, 最大时间也就是找到那只走出杆最久的蚂蚁, 很显然是3厘米的蚂蚁往右走(也就是木杆27厘米处), 时间为24秒。</P>

魔鱼儿

原来是这么回事哦,学习了

noski

嗯，果然难不到大家，gozichen、veteranhit、kexin_xiao都说对了，就是把两只蚂蚁的相遇掉头看成是擦肩而过。那么，最短时间就是让所有蚂蚁都朝自己较近的那一头走就行了。而最长时间则是让所有蚂蚁都朝自己较远那一头前进。

Atato

欣然不时也会显示一下数学本领啊 呵呵