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

oneleaf · #1

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

oneleaf · #2

代码：全选

#!/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 · #3

厉害～

liuqinger · #4

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

代码：全选

#!/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 · #5

呵呵，应该是我写的时候马虎了

programus · #6

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

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

bones7456 · #7

我要开始学python了！

purewind · #8

晕了，题目差点没看明白

Neptune · #9

代码：全选

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 · #10

代码：全选

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 · #11

另外to :

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

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

我觉得不会啊,蚂蚁会掉头的,所以规则是在足够短的时刻只有两边的蚂蚁才有可能出去;在任意时刻棍子上的蚂蚁一定保持开始的顺序;两边的蚂蚁在足够的时间一定可以出去,因此是有解的

laborer · #12

代码：全选

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))

peakgg · #13

LS让我很迷惑：算法究竟要人把问题考虑到什么地步从才算最好呢？看了4楼的程序后到网上搜了一下，知道原来有个“幽灵算法”，当时有恍然大悟之感。现在LS的程序，MS不用编程也可。
幸好看了4楼的程序，否则直接看LS的肯定如坠云雾。
这样想来这个题还是按2楼直接能看懂程序的方式编更好了？

zhouhuab · #14

写完程序才发现规律

代码：全选

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 · #15

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