魔方吧·中文魔方俱乐部
标题:
蚂蚁爬杆
[打印本页]
作者:
noski
时间:
2008-9-26 15:09:37
标题:
蚂蚁爬杆
<P> </P>
<P>有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细，不能同时通过两只蚂蚁。开始时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。求所有蚂蚁都离开木杆的最短时间和最长时间，以及每种情况它们的头都是朝向什么方向的。</P>
<P> </P>
<P>＝＝＝＝＝＝＝＝＝＝</P>
<P>PS：这道题是我看《编程之美》时看到的一道题，觉得思路很巧妙，于是就发出来让大家欣赏一下。有什么好思路，或者后绪问题，欢迎讨论。。</P>
作者:
gozichen
时间:
2008-9-26 15:21:40
穷举法好象太累了，noski说的思路巧妙，我估计是用镜向的原理，把两个蚂蚁碰头掉头可以看成它们互相穿过沿着不变的方向继续走。<BR>
这样的话，最长时间实际上就是看最远那只蚂蚁了。<BR>
不知道对不对
作者:
gozichen
时间:
2008-9-26 15:23:28
还要算头朝向就有点头疼了
作者:
veteranhit
时间:
2008-9-26 15:36:06
标题:
回复 3# 的帖子
说得很对啊，只要3厘米处的蚂蚁向24厘米的路径走，不用管其他蚂蚁的朝向啊，最长时间为24秒。不过时间最短需要大家都往最短的路径上运动，数11厘米的耗时，最短也得11秒。不知道对不对，大家继续讨论。
作者:
魔鱼儿
时间:
2008-9-26 16:27:56
哪位强人能来详细的解释一下啊,
作者:
kexin_xiao
时间:
2008-9-26 16:39:15
蚂蚁是相同的，当两只蚂蚁碰撞，他们同时转向，以相同速率、相反方向继续爬行可以看成两只蚂蚁以原速率前进，互不干涉。实际上，问题就变成了5只蚂蚁，一部分向杆一段爬行，另一部分向另一端爬行，什么时候木棍上一只蚂蚁都不剩。
作者:
kexin_xiao
时间:
2008-9-26 16:44:39
<P>最小时间肯定大家都很容易就想到了, 就是蚂蚁们分别向左或向右走, 其中在11厘米处的蚂蚁应该向左走比较近, 所以最小时间就是中间的蚂蚁向0处走出杆的时间, 也就是11秒。</P>
<P>最大时间，如果用穷举，一共只有2^5=32种情况，有点麻烦。简单地说，按照我6楼的说法, 最大时间也就是找到那只走出杆最久的蚂蚁, 很显然是3厘米的蚂蚁往右走(也就是木杆27厘米处), 时间为24秒。</P>
作者:
魔鱼儿
时间:
2008-9-26 16:49:09
标题:
回复 7# 的帖子
原来是这么回事哦,学习了
作者:
noski
时间:
2008-9-26 17:07:57
嗯，果然难不到大家，gozichen、veteranhit、kexin_xiao都说对了，就是把两只蚂蚁的相遇掉头看成是擦肩而过。那么，最短时间就是让所有蚂蚁都朝自己较近的那一头走就行了。而最长时间则是让所有蚂蚁都朝自己较远那一头前进。
作者:
Atato
时间:
2008-9-26 17:18:16
欣然不时也会显示一下数学本领啊 呵呵
作者:
kexin_xiao
时间:
2008-9-26 17:39:04
标题:
回复 10# 的帖子
千万别让金眼睛看到，他追着我作题！
作者:
7阶4分
时间:
2008-9-26 18:04:21
楼上已经有答案了啊！
作者:
bbshanwei
时间:
2008-9-27 14:52:52
欣然被金眼睛问怕了。
作者:
kexin_xiao
时间:
2008-9-27 15:27:02
标题:
回复 13# 的帖子
是啊，相当的怕啊
作者:
金眼睛
时间:
2008-9-27 20:39:20
<P>呵呵，欣然还是相当有实力滴，总是不经意间露一小手，只不过有时候过于谦虚了啊！提出批评，嘿嘿，<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/lol.gif" border=0 smilieid="12"> </P>
<P> </P>
<P>这道题虽不难，但可以转化为一道有相当难度的问题，蚂蚁觅食的问题，我自己随便想的，o(∩_∩)o...</P>
<P> </P>
<P>就是说平面上有一只蚂蚁发现了食物，去召唤平面上任意N个伙伴，将食物拖回平面上的某点——蚁穴。运货物的速度与蚂蚁的数量成正比，以最求耗时最短为目标。</P>
<P> </P>
<P>也没怎么仔细想，初步分析了一下，觉得还是很难的：</P>
<P>1：蚂蚁可以一传十，十传百，这存在优化问题。除了传消息的，其他蚂蚁可以立刻动身去运食物。</P>
<P>2：如果某只蚂蚁距离过远，有可能不需要去通知它。</P>
<P>3：第一只蚂蚁不一定首先通知距其最近的蚂蚁，有可能要考虑到蚂蚁聚集程度的影响。</P>
<P>4：如果某只蚂蚁距蚁穴很近，其他蚂蚁及食物在反方向很远的地方，有可能先运食物到某一点，再去通知较优。</P>
<P> </P>
<P>初步想法，也不一定对，呵呵，问题比较复杂啊，也没有编出题目来。大家可以随便讨论讨论。</P>
作者:
kexin_xiao
时间:
2008-9-28 16:39:13
标题:
回复 15# 的帖子
我估计要用计算机模拟了
作者:
kexin_xiao
时间:
2008-9-28 16:39:49
还好你只是想在一个平面，而不是空间
作者:
625845786
时间:
2008-9-29 16:55:54
请问蚂蚁是多长，如果忽略不记的话,2楼说的对，如果蚂蚁自身的长度也算上的话，估计会有改变,以为如果是按延长线,那么少算了一个蚂蚁自身
欢迎光临 魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)
Powered by Discuz! X2
