作者:pengkuny
   百度到我们学校来招人的一道面试题,被贴在本校BBS上, 发帖者不屑一顾的加一句:"心算答案都出来了".
      我和寝室同学讨论了老半天,也没找到什么有效的算法,(当然那种遍历求解的算法不叫算法,小学生都会.)

     直到我获知"鬼魂算法"后,才拍案叫绝啊!它的思想真是"好,很好,非常好,好得很哪,真得非常好,不是一般的好!".所谓"鬼魂算法",是一个非正式名称,网络上都搜不到,也即把蚂蚁视作鬼魂,可以彼此穿过对方的身体.
     废话少说,且看贴.

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

    再三说明,32种情况遍历求解傻瓜也会,不要提它!
    
    好好想一想吧,尤其是最大时间是多少?

    也有人有更另类的想法,不过感觉那种方法不太适合于编程.
posted on 2006-11-09 23:05 哈哈 阅读(2963) 评论(17)  编辑 收藏 引用

评论:
# re: 百度公司来科大的面试题 2006-11-10 00:18 | 江水兽
简单 相当于是智力题目吧 呵呵呵

只要将每个蚂蚁看作是木棍上的唯一的蚂蚁 计算其通过的时间 再累加便可以了

估计这也就是你说的“鬼魂算法”吧 呵呵呵  回复  更多评论
  
# re: 百度公司来科大的面试题 2006-11-10 00:55 | Asp
POJ上面好像也有这道题,当时好像一下子没想出来,原来这么简单?  回复  更多评论
  
# re: 百度公司来科大的面试题 2006-11-10 09:37 | pengkuny
@江水兽
好像不是哦,
你说说最小时间和最大时间的具体数值吧  回复  更多评论
  
# re: 百度公司来科大的面试题 2006-11-10 10:25 | 沐枫
呵呵,确实是智力题啊。
最小时间很快就出来了。
最大时间,刚一开始给矇了。然后看到提示,就霍然开朗了。
然后果然心算就出答案了。
--
问题是心算出答案的题目,如果用程序实现,那不变成了直接输出答案了,这如何写算法呢?太简单的算法,不如不写。写复杂了,就不是最优算法了。  回复  更多评论
  
# re: 百度公司来科大的面试题 2006-11-10 10:35 | pengkuny
@沐枫
确实有这个问题,不知道那些毕业的师兄师姐们如何处理
真要写的话,也可以吧.O(1)时间完成  回复  更多评论
  
# re: 百度公司来科大的面试题 2006-11-10 10:54 | 沐枫
27cm,对半后是13.5cm.
1. 这样,离最近末端最大距离是11cm,因此,最小时间是11秒。
2. 离最远的末端最大的距离是27-3=24cm,因此,最大时间是24秒。

对不对,请指教?  回复  更多评论
  
# re: 百度公司来科大的面试题 2006-11-10 11:06 | pengkuny
@沐枫
没错  回复  更多评论
  
# re: 百度公司来科大的面试题 2006-11-10 11:52 | 江水兽
@pengkuny

哎呀 是我搞错了 呵呵呵 真是不好意思呵!
不是求和累加 而应该是取最大最小值 呵呵呵  回复  更多评论
  
# re: 百度公司来科大的面试题 2006-11-10 19:04 | chenger
说实在的,一下就想到了作者所说的鬼魂算法。
是个智力题  回复  更多评论
  
# re: 百度公司来科大的面试题 2006-11-11 15:18 | 王小龙
我是这么看的:
1,最少的时间,不用说是11秒,即最难出来的蚂蚁出来的时间。
2,我们可以把5只蚂蚁看成是无差别的,那么相遇后碰头,再转方向其实可以看成没转向,只是另一只蚂蚁帮它完成任务,即交换任务(因为是无差别的,所以相当于没掉头),这样,最大时间就是3位置的蚂蚁出来的最大时间,是24。
最大的时间24
最小是11
  回复  更多评论
  
# re: 百度公司来科大的面试题 2006-11-12 10:11 | pengkuny
@王小龙
没错.
不过,我想要是把各蚂蚁的速度改成各不相同,
这道题就会变得很难,
不知道又该如何解答?  回复  更多评论
  
# re: 百度公司来科大的面试题 2006-11-13 08:51 | 路人
速度不一样就会有追逐,估计追上的那只蚂蚁要转向。这题没说,不严谨。  回复  更多评论
  
# re: 百度公司来科大的面试题 2006-11-16 21:38 | 愚蠢的人
(当然那种遍历求解的算法不叫算法,小学生都会.)??

照楼主这么说,我看这道题变成填空题好了,为什么不想用编程来验证这种口算结果的正确性呢?
编程是为了让机器算,而不是人算,我认为"鬼魂算法"是一种"神"算法,有人把递归算法看做神,那么它应该是"超神",超神你知道吧,就是你根本不能用它做任何事,它只是告诉你结果. #@#@?@#$%#$??? 说明白一点,想出"鬼魂算法"只是一些聪明人(包括你在内)发现了一个有趣的现象.你需要做的是编程,然后让机器去算出每一种结果,这样谁都会知道正确的答案.
  回复  更多评论
  
# re: 百度公司来科大的面试题 2006-11-17 09:40 | pengkuny
@愚蠢的人
学过算法课的都知道,
算法设计就是要找到一种最优代价的算法来解决问题,
比如时间复杂度最优或兼顾空间复杂度,
如果是不讲究优化,
一切交给计算机去算,
那么,算法的意义何在?
举个例,"深蓝"超级计算机大战卡斯帕罗夫,(国际象棋)
每一步,计算机都必须考虑它现在下的棋以及以后可能走的棋,
每一步,都有10的401次方种走法,
如果每次都让计算机去算这10的401次方种走法,然后从中选择一种最可能赢的走法,那么,超级计算机需要算上几个世纪!

而即便是小规模问题,优化的算法的重要性也同样重要.因为实际问题就是由无数个小规模问题组成.

一个有趣的方法不仅仅是"just for fun",更重要的是,它代表了一种崭新的思路.

如果你熟悉各种排序算法的话,就会知道,counting sort(计数排序)思想是多么的巧妙,它甚至根本不必比较元素,任何规模的数组,它都在O(n+k)时间内排序完毕.

不说了.  回复  更多评论
  
# re: 百度公司来科大的面试题 2006-11-20 00:16 | Asp
Ns.....  回复  更多评论
  
# re: 百度公司来科大的面试题 2006-11-29 23:26 | ATP
这题为什么很难呢?
有一道关于小球运动的物理竞赛题(是高中的)和它异曲同工,一样的思路,但要烦得多,一下找不到,过一段时间贴吧  回复  更多评论
  
# re: 百度公司来科大的面试题 2006-12-12 16:52 | Dain
可能都被题目中提到的写程序实现搞懵了
其实仔细想想,这题就是一个智力题  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理