一道习题,据说是百度的面试题目.

Python/PHP/Perl 开发与设计
头像
oneleaf
论坛管理员
帖子: 10218
注册时间: 2005-03-27 0:06
系统: Ubuntu 12.04
送出感谢: 7 次
接收感谢: 102 次

一道习题,据说是百度的面试题目.

#1

帖子 oneleaf » 2006-11-13 12:52

有一根27厘米的细木杆,在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。 木杆很细,不能同时通过一只蚂蚁。开始 时,蚂蚁的头朝左还是朝右是任意的,它们只会朝前走或调头,但不会后退。当任意两只蚂蚁碰头时,两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。 编写程序,求所有蚂蚁都离开木杆的最小时间和最大时间。
头像
oneleaf
论坛管理员
帖子: 10218
注册时间: 2005-03-27 0:06
系统: Ubuntu 12.04
送出感谢: 7 次
接收感谢: 102 次

#2

帖子 oneleaf » 2006-11-13 12:53

代码: 全选

#!/bin/python
class Ant:
    def __init__(self, position, direction):
        self.position = position
        self.direction = direction

    def move(self,step):
        if self.direction:
            self.position=self.position+step
        else:
            self.position=self.position-step

    def change(self):
        self.direction=not self.direction

    def __str__(self):
        return self.name+':'+str(self.position)

def run(a1,a2,a3,a4,a5):
    ant1=Ant(30,a1)
    ant2=Ant(70,a2)
    ant3=Ant(110,a3)
    ant4=Ant(230,a4)
    ant5=Ant(270,a5)
    dept=0
    step=1
    while 1:
        if (ant1.position>=270 or ant1.position<=0) and \
           (ant2.position>=270 or ant2.position<=0) and \
           (ant3.position>=270 or ant3.position<=0) and \
           (ant4.position>=270 or ant4.position<=0) and \
           (ant5.position>=270 or ant5.position<=0):
            return dept/10
            break
        dept=dept+step
        ant1.move(step)
        ant2.move(step)
        ant3.move(step)
        ant4.move(step)
        ant5.move(step)
        if (ant1.position==ant2.position):
            ant1.change()
            ant2.change()
        if (ant2.position==ant3.position):
            ant2.change()
            ant3.change()
        if (ant3.position==ant4.position):
            ant3.change()
            ant4.change()
        if (ant4.position==ant5.position):
            ant4.change()
            ant5.change()

if __name__ == "__main__":
    m=[]
    for a1 in (True,False):
        for a2 in (True,False):
            for a3 in (True,False):
                for a4 in (True,False):
                    for a5 in (True,False):
                        m.append(run(a1,a2,a3,a4,a5))
    print max(m),min(m)



$ python ant.py
27 11
sokv
帖子: 61
注册时间: 2006-07-22 18:44
送出感谢: 0
接收感谢: 0

#3

帖子 sokv » 2006-11-22 23:34

厉害~
liuqinger
帖子: 9
注册时间: 2006-05-03 12:02
送出感谢: 0
接收感谢: 0
联系:

#4

帖子 liuqinger » 2006-12-02 15:52

把你的程序稍微简化了一下
不清楚为什么你会安毫米计算,可能是怕相遇到非整数厘米的位置,但程序的设计的开始位置很好,不会出现这种情况
把程序稍微改了一下
即使出现在非整数厘米的地方也无所谓
哦,还有,题目中的位置和程序中的不一样,不知道哪个是错的

代码: 全选

#!/usr/bin/python
class AntGhost:
   def __init__(self, position, direction):
      self.position = position
      self.direction = direction

   def move(self,step):
      if self.direction:
         self.position=self.position+step
      else:
         self.position=self.position-step
               
   def __str__(self):
      return self.name+':'+str(self.position)
                        
def run(a1,a2,a3,a4,a5):
      ghost1=AntGhost(3,a1)
      ghost2=AntGhost(7,a2)
      ghost3=AntGhost(11,a3)
      ghost4=AntGhost(23,a4)
      ghost5=AntGhost(27,a5)
      dept=0
      step=1
      
      while 1:
         if (ghost1.position>=27 or ghost1.position<=0) and \
            (ghost2.position>=27 or ghost2.position<=0) and \
            (ghost3.position>=27 or ghost3.position<=0) and \
            (ghost4.position>=27 or ghost4.position<=0) and \
            (ghost5.position>=27 or ghost5.position<=0):
         
            return dept
            break
            
         dept=dept+step
         ghost1.move(step)
         ghost2.move(step)
         ghost3.move(step)
         ghost4.move(step)
         ghost5.move(step)
         
if __name__ == "__main__":
   m=[]
   for a1 in (True,False):
      for a2 in (True,False):
         for a3 in (True,False):
            for a4 in (True,False):
               for a5 in (True,False):
                  m.append(run(a1,a2,a3,a4,a5))
                  
   print max(m), min(m)
[/code]
头像
oneleaf
论坛管理员
帖子: 10218
注册时间: 2005-03-27 0:06
系统: Ubuntu 12.04
送出感谢: 7 次
接收感谢: 102 次

#5

帖子 oneleaf » 2006-12-03 15:22

呵呵,应该是我写的时候马虎了
programus
帖子: 15
注册时间: 2007-01-13 20:22
送出感谢: 0
接收感谢: 0

Re: 一道习题,据说是百度的面试题目.

#6

帖子 programus » 2007-01-18 12:18

oneleaf 写了: 木杆很细,不能同时通过一只蚂蚁。....编写程序,求所有蚂蚁都离开木杆的最小时间和最大时间。


不能同时通过一只蚂蚁…… 大家都死在原位了。呵呵……最大时间==最小时间==无穷大。
:P
头像
bones7456
论坛版主
帖子: 8495
注册时间: 2006-04-12 20:05
来自: 杭州
送出感谢: 0
接收感谢: 8 次
联系:

#7

帖子 bones7456 » 2007-01-18 12:49

我要开始学python了!
purewind
帖子: 452
注册时间: 2006-11-18 15:40
送出感谢: 0
接收感谢: 0

#8

帖子 purewind » 2007-01-18 15:04

晕了,题目差点没看明白
linux什么最重要?硬件要旧,软件要新!
Ubuntu什么最重要?源要全!网要快!
不是你不明白,是linux变化快
人品也很重要
Neptune
帖子: 13
注册时间: 2006-08-02 23:33
送出感谢: 0
接收感谢: 0

我也来凑热闹

#9

帖子 Neptune » 2007-01-18 19:58

代码: 全选

slice = 0.5 / 1
maxnum = 0
minnum = 999999     
position = [3,7,11,17,23] 

class ant():
  def __init__(self,position,direction):
    self.posi = position
    self.dirt = direction
  def run(self,length=0.5):
    self.posi += length * self.dirt 
  def __str__(self):
    return 'posistion:%s,direction:%s' %(self.posi,self.dirt)

li = range(5)
for li[0] in range(-1,3,2):
 for li[1] in range(-1,3,2):
  for li[2] in range(-1,3,2):
   for li[3] in range(-1,3,2):
    for li[4] in range(-1,3,2):
      print li
      slicenum = 0
      ants = [ant(position[i],li[i]) for i in range(5)]
      while len(ants) >0:
        slicenum += 1
        [a.run() for a in ants]
        if ants[0].posi < 0 or ants[0].posi > 27: del ants[0]
        if ants != [] and (ants[0].posi < 0 or ants[-1].posi > 27):del ants[-1]
        for i in range(len(ants)-1):
          if ants[i].posi == ants[i+1].posi:
            ants[i].dirt = -1
            ants[i].dirt = 1
      if slicenum < minnum: minnum = slicenum           
      if slicenum > maxnum: maxnum = slicenum                         
      print 'slicenum',slicenum

print 'min time:%s seconds' % (minnum*slice)       
print 'max time:%s seconds' % (maxnum*slice)
Neptune
帖子: 13
注册时间: 2006-08-02 23:33
送出感谢: 0
接收感谢: 0

怎么回事? 空格没了

#10

帖子 Neptune » 2007-01-18 19:59

代码: 全选

slice = 0.5 / 1
maxnum = 0
minnum = 999999     
position = [3,7,11,17,23] 

class ant():
  def __init__(self,position,direction):
    self.posi = position
    self.dirt = direction
  def run(self,length=0.5):
    self.posi += length * self.dirt 
  def __str__(self):
    return 'posistion:%s,direction:%s' %(self.posi,self.dirt)

li = range(5)
for li[0] in range(-1,3,2):
 for li[1] in range(-1,3,2):
  for li[2] in range(-1,3,2):
   for li[3] in range(-1,3,2):
    for li[4] in range(-1,3,2):
      print li
      slicenum = 0
      ants = [ant(position[i],li[i]) for i in range(5)]
      while len(ants) >0:
        slicenum += 1
        [a.run() for a in ants]
        if ants[0].posi < 0 or ants[0].posi > 27: del ants[0]
        if ants != [] and (ants[0].posi < 0 or ants[-1].posi > 27):del ants[-1]
        for i in range(len(ants)-1):
          if ants[i].posi == ants[i+1].posi:
            ants[i].dirt = -1
            ants[i].dirt = 1
      if slicenum < minnum: minnum = slicenum           
      if slicenum > maxnum: maxnum = slicenum                         
      print 'slicenum',slicenum

print 'min time:%s seconds' % (minnum*slice)       
print 'max time:%s seconds' % (maxnum*slice)
Neptune
帖子: 13
注册时间: 2006-08-02 23:33
送出感谢: 0
接收感谢: 0

使用code还是没辙,斑竹帮我删除吧

#11

帖子 Neptune » 2007-01-18 20:08

另外to :

oneleaf 写道:
木杆很细,不能同时通过一只蚂蚁。....编写程序,求所有蚂蚁都离开木杆的最小时间和最大时间。


不能同时通过一只蚂蚁…… 大家都死在原位了。呵呵……最大时间==最小时间==无穷大。


我觉得不会啊,蚂蚁会掉头的,所以规则是在足够短的时刻只有两边的蚂蚁才有可能出去;在任意时刻棍子上的蚂蚁一定保持开始的顺序;两边的蚂蚁在足够的时间一定可以出去,因此是有解的
头像
laborer
帖子: 1016
注册时间: 2005-10-25 11:15
送出感谢: 0
接收感谢: 1 次
联系:

#12

帖子 laborer » 2007-02-06 6:25

代码: 全选

a=[3,7,11,17,23]
print 'min:', 13.5-min([abs(i-13.5) for i in a])
print 'max:', max(max(a),27-min(a))
hreiser@oakland:~$ killall -9 wife
police@oakland:~$ sudo find / -user hreiser
court@oakland:~$ sudo mv /home/hreiser /jail/
court@oakland:~$ sudo usermod -d /jail/hreiser -s "/usr/sbin/chroot /jail/" hreiser
头像
peakgg
帖子: 1122
注册时间: 2006-10-10 9:40
送出感谢: 1 次
接收感谢: 0
联系:

#13

帖子 peakgg » 2007-03-18 17:34

LS让我很迷惑:算法究竟要人把问题考虑到什么地步从才算最好呢?看了4楼的程序后到网上搜了一下,知道原来有个“幽灵算法”,当时有恍然大悟之感。现在LS的程序,MS不用编程也可。
幸好看了4楼的程序,否则直接看LS的肯定如坠云雾。
这样想来这个题还是按2楼直接能看懂程序的方式编更好了?
zhouhuab
帖子: 2
注册时间: 2007-04-28 18:17
送出感谢: 0
接收感谢: 0

#14

帖子 zhouhuab » 2007-04-28 18:21

写完程序才发现规律

代码: 全选

import sys
pos_ants = [3, 7, 11, 17, 23]
len_rod = 27
pos_ants_r = [len_rod - p for p in pos_ants]
maxtime = max([max(pos_ants), max(pos_ants_r)])
print maxtime

mintime = sys.maxint
for i in range(len(pos_ants) - 1):
    mintime = min(mintime, max([pos_ants[i], pos_ants_r[i + 1]]))
print mintime
gtx
帖子: 172
注册时间: 2005-10-28 17:40
送出感谢: 0
接收感谢: 0

#15

帖子 gtx » 2007-04-28 18:50

碰头就调头不就是等于无干扰地继续走下去吗?
回复

回到 “Python/Php/Perl”