分页： 1 / 2
一道习题，据说是百度的面试题目.
发表于 ： 2006-11-13 12:52
由 oneleaf
有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。 木杆很细，不能同时通过一只蚂蚁。开始 时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。 编写程序，求所有蚂蚁都离开木杆的最小时间和最大时间。
发表于 ： 2006-11-13 12:53
由 oneleaf
代码： 全选
#!/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
发表于 ： 2006-11-22 23:34
由 sokv
厉害～
发表于 ： 2006-12-02 15:52
由 liuqinger
把你的程序稍微简化了一下
不清楚为什么你会安毫米计算，可能是怕相遇到非整数厘米的位置，但程序的设计的开始位置很好，不会出现这种情况
把程序稍微改了一下
即使出现在非整数厘米的地方也无所谓
哦，还有，题目中的位置和程序中的不一样，不知道哪个是错的
代码： 全选
#!/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]
发表于 ： 2006-12-03 15:22
由 oneleaf
呵呵，应该是我写的时候马虎了
Re: 一道习题，据说是百度的面试题目.
发表于 ： 2007-01-18 12:18
由 programus
oneleaf 写了： 木杆很细，不能同时通过一只蚂蚁。....编写程序，求所有蚂蚁都离开木杆的最小时间和最大时间。
不能同时通过一只蚂蚁…… 大家都死在原位了。呵呵……最大时间==最小时间==无穷大。
发表于 ： 2007-01-18 12:49
由 bones7456
我要开始学python了！
发表于 ： 2007-01-18 15:04
由 purewind
晕了，题目差点没看明白
我也来凑热闹
发表于 ： 2007-01-18 19:58
由 Neptune
代码： 全选
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)
怎么回事？ 空格没了
发表于 ： 2007-01-18 19:59
由 Neptune
代码： 全选
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)
使用code还是没辙，斑竹帮我删除吧
发表于 ： 2007-01-18 20:08
由 Neptune
另外to :
oneleaf 写道:
木杆很细，不能同时通过一只蚂蚁。....编写程序，求所有蚂蚁都离开木杆的最小时间和最大时间。
不能同时通过一只蚂蚁…… 大家都死在原位了。呵呵……最大时间==最小时间==无穷大。
我觉得不会啊,蚂蚁会掉头的,所以规则是在足够短的时刻只有两边的蚂蚁才有可能出去;在任意时刻棍子上的蚂蚁一定保持开始的顺序;两边的蚂蚁在足够的时间一定可以出去,因此是有解的
发表于 ： 2007-02-06 6:25
由 laborer
代码： 全选
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))
发表于 ： 2007-03-18 17:34
由 peakgg
LS让我很迷惑：算法究竟要人把问题考虑到什么地步从才算最好呢？看了4楼的程序后到网上搜了一下，知道原来有个“幽灵算法”，当时有恍然大悟之感。现在LS的程序，MS不用编程也可。
幸好看了4楼的程序，否则直接看LS的肯定如坠云雾。
这样想来这个题还是按2楼直接能看懂程序的方式编更好了？
发表于 ： 2007-04-28 18:21
由 zhouhuab
写完程序才发现规律
代码： 全选
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
发表于 ： 2007-04-28 18:50
由 gtx
碰头就调头不就是等于无干扰地继续走下去吗？