BlogJava-╰⊙д⊙╯。oо○ -最新评论http://www.blogjava.net/dreamingnest/CommentsRSS.aspx面朝大海·春暖花开zh-cnSun, 12 Oct 2008 09:33:45 GMTSun, 12 Oct 2008 09:33:45 GMTcnblogsre: BFS和DFS两种方法获取指定目录下的所有目录和文件http://www.blogjava.net/dreamingnest/archive/2008/07/16/201424.html#215290fejayfejayWed, 16 Jul 2008 11:23:00 GMThttp://www.blogjava.net/dreamingnest/archive/2008/07/16/201424.html#215290

fejay 2008-07-16 19:23 发表评论
]]>re: 关于蚂蚁问题（Ants）http://www.blogjava.net/dreamingnest/archive/2008/06/12/199672.html#207414zdhzdhThu, 12 Jun 2008 08:06:00 GMThttp://www.blogjava.net/dreamingnest/archive/2008/06/12/199672.html#207414 序列中的元素带有方向，进行负值部分移动到负值区域，正值部分移动到正值区域时就不再发生碰撞，此时绝对值最小的值决定剩余爬行时间

zdh 2008-06-12 16:06 发表评论
]]>re: 关于蚂蚁问题（Ants）http://www.blogjava.net/dreamingnest/archive/2008/06/12/199672.html#207412zdhzdhThu, 12 Jun 2008 08:00:00 GMThttp://www.blogjava.net/dreamingnest/archive/2008/06/12/199672.html#207412

zdh 2008-06-12 16:00 发表评论
]]>re: 关于蚂蚁问题（Ants）http://www.blogjava.net/dreamingnest/archive/2008/05/12/199672.html#200034bluesbluesMon, 12 May 2008 07:53:00 GMThttp://www.blogjava.net/dreamingnest/archive/2008/05/12/199672.html#200034至于为什么说27-3是最长，我中间跳跃一些而已。
就是观察分析了两端的蚂蚁后说的， A离左边3， E离右边4。
所以最长就是27-3=24。 上一句分析我省略了而已，SORRY。

最短：
我只是将五个蚂蚁的最短时间列出来而已， 最长时间列出来没意义了。
如果用式子总结便是： 最靠近杆中间点的那个蚂蚁的最短时间，即C距离左边。


@dreamingnest


blues 2008-05-12 15:53 发表评论
]]>re: 关于蚂蚁问题（Ants）http://www.blogjava.net/dreamingnest/archive/2008/05/12/199672.html#200028dreamingnestdreamingnestMon, 12 May 2008 07:26:00 GMThttp://www.blogjava.net/dreamingnest/archive/2008/05/12/199672.html#200028
·最长时间：是按照你说的“蚂蚁不调头，即擦肩而过，继续沿原来方向前进（与调头是一样的，只是换了一只蚂蚁而已）”这样，但有两点说明：（1）通过分析，我们只需判断最两端的两只蚂蚁便足够了，证明见二楼“银河使者”的解释。（2）一定要求出4个数进行比较后才可以，假设最左端和最右端的位置为L和R，中长度为T，那么最长的时间为max(max(L,T-L),max(R,T-R))。

·最短时间：通过分析后，也只需看最中间的一个（共奇数蚂蚁）或两个（共偶数蚂蚁）蚂蚁到达某一端的最短时间，对于奇数：min(L,T-L)，对于偶数：max(min(L,T-L),min(R,T-R))。

·通过程序来实现是有必要的，这算是一道模拟题目，可在情况类似的计算应用中会遇到，正如英文描述中可能出现1000000数量级别的，这样我们便无法直接得出结果。此题能作为面试题，而不是笔试题，就是在考察一种思想，避开“一根不能同时通过两只蚂蚁”的迷惑。

·感谢大家能仔细讨论这个问题，写程序相信每个人都能实现，只是这道题给我们的启发是非常大的～

dreamingnest 2008-05-12 15:26 发表评论
]]>re: 关于蚂蚁问题（Ants）http://www.blogjava.net/dreamingnest/archive/2008/05/12/199672.html#200007bluesbluesMon, 12 May 2008 06:22:00 GMThttp://www.blogjava.net/dreamingnest/archive/2008/05/12/199672.html#200007我认为还有更好的方法，我在原文给出了最长时间的分析。
这里我加上最短时间分析：

其实文中蚂蚁相撞两蚂蚁调头
可以这样看问题，如果相撞后，杆可以过两只蚂蚁
蚂蚁不调头，即擦肩而过，继续沿原来方向前进（与调头是一样的，只是换了一只蚂蚁而已）
这样问题就简化了，呵呵。
即所有蚂蚁中离杆其中一端最远的那只蚂蚁，即为最长时间。
即27-3=24

同理，最短时间为
所有蚂蚁使用时间：A最短是3， B最短是7， C最短11， D最短是10， E最短是4。
所以总的最短时间为11.

不知道小弟的思路是否正确？~~~~


blues 2008-05-12 14:22 发表评论
]]>re: 关于蚂蚁问题（Ants）http://www.blogjava.net/dreamingnest/archive/2008/05/10/199672.html#199704银河使者银河使者Sat, 10 May 2008 06:14:00 GMThttp://www.blogjava.net/dreamingnest/archive/2008/05/10/199672.html#199704 下面用数学归纳法证明一下这个算法。让我们先来看最简单的形式（m=1)，有两只蚂蚁的情况，假设细木杆的长度为n，两只蚂蚁的位置分别为p1和p2。并且p2 > p1。其他的条件如原题。下面分别用p1和p2来代表两只蚂蚁。

对于两只蚂蚁，方向组合只有四种，分别如下：
1. p1、p2都向左 最长时间：time(p2)
2. p1、p2都向右 最长时间：time(p1)
3. p1向左、p2向右 最长时间：max(time(p1), time(n - p2))
4. p1向右、p2向左（这种情况会发生碰撞）

最长时间：max(time(n - p1), time(p2))

对于这种情况，实际上p2的时间为time(((p2 - p1) / 2 ) * 2 + n - p2 )= time(n - p1)
p1的时间为time(((p2 - p1) / 2 ) * 2 + p1) = time(p2)，
从最终结果看，A- >, < -B 就相当于< -B , A - > 相当于A、B互相穿越而过，并且B只走到A最初的位置，而A也只走到B最初的位置。

从上面四种情况的最长时间可看出，正好将两种蚂蚁p1和p2可能存在的的四种可能：p1、p2、n - p1、n-p2 。我们要做的就是求这四个值的最大值，即max(time(p1)、time(p2)、time(n - p1)、time(n-p2))。 如果用文字来描述的话，就是任意一只蚂蚁到达两端的最长时间就是最终结果。

最简单的情况已经ok了，现在假设m只蚂蚁也成立，那么这m只蚂蚁也可以看成是一只蚂蚁，而m+1只蚂蚁当然就相当于两只蚂蚁了。所以
m = 1 成立
假设m成立
而证明了m+1也成立
所以“任意一只蚂蚁到达两端的最长时间就是最终结果”的结论成立

银河使者 2008-05-10 14:14 发表评论
]]>re: 关于蚂蚁问题（Ants）http://www.blogjava.net/dreamingnest/archive/2008/05/10/199672.html#199699漠漠漠漠Sat, 10 May 2008 05:29:00 GMThttp://www.blogjava.net/dreamingnest/archive/2008/05/10/199672.html#199699

漠漠 2008-05-10 13:29 发表评论
]]>