一道习题,据说是百度的面试题目.
- oneleaf
- 论坛管理员
- 帖子: 10441
- 注册时间: 2005-03-27 0:06
- 系统: Ubuntu 12.04
一道习题,据说是百度的面试题目.
有一根27厘米的细木杆,在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。 木杆很细,不能同时通过一只蚂蚁。开始 时,蚂蚁的头朝左还是朝右是任意的,它们只会朝前走或调头,但不会后退。当任意两只蚂蚁碰头时,两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。 编写程序,求所有蚂蚁都离开木杆的最小时间和最大时间。
- oneleaf
- 论坛管理员
- 帖子: 10441
- 注册时间: 2005-03-27 0:06
- 系统: Ubuntu 12.04
代码: 全选
#!/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)
27 11
-
- 帖子: 9
- 注册时间: 2006-05-03 12:02
把你的程序稍微简化了一下
不清楚为什么你会安毫米计算,可能是怕相遇到非整数厘米的位置,但程序的设计的开始位置很好,不会出现这种情况
把程序稍微改了一下
即使出现在非整数厘米的地方也无所谓
哦,还有,题目中的位置和程序中的不一样,不知道哪个是错的[/code]
不清楚为什么你会安毫米计算,可能是怕相遇到非整数厘米的位置,但程序的设计的开始位置很好,不会出现这种情况
把程序稍微改了一下
即使出现在非整数厘米的地方也无所谓
哦,还有,题目中的位置和程序中的不一样,不知道哪个是错的
代码: 全选
#!/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)
-
- 帖子: 15
- 注册时间: 2007-01-13 20:22
Re: 一道习题,据说是百度的面试题目.
不能同时通过一只蚂蚁…… 大家都死在原位了。呵呵……最大时间==最小时间==无穷大。oneleaf 写了: 木杆很细,不能同时通过一只蚂蚁。....编写程序,求所有蚂蚁都离开木杆的最小时间和最大时间。
- bones7456
- 帖子: 8495
- 注册时间: 2006-04-12 20:05
- 来自: 杭州
- 联系:
-
- 帖子: 452
- 注册时间: 2006-11-18 15:40
-
- 帖子: 13
- 注册时间: 2006-08-02 23:33
我也来凑热闹
代码: 全选
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)
-
- 帖子: 13
- 注册时间: 2006-08-02 23:33
怎么回事? 空格没了
代码: 全选
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)
-
- 帖子: 13
- 注册时间: 2006-08-02 23:33
使用code还是没辙,斑竹帮我删除吧
另外to :
oneleaf 写道:
木杆很细,不能同时通过一只蚂蚁。....编写程序,求所有蚂蚁都离开木杆的最小时间和最大时间。
不能同时通过一只蚂蚁…… 大家都死在原位了。呵呵……最大时间==最小时间==无穷大。
我觉得不会啊,蚂蚁会掉头的,所以规则是在足够短的时刻只有两边的蚂蚁才有可能出去;在任意时刻棍子上的蚂蚁一定保持开始的顺序;两边的蚂蚁在足够的时间一定可以出去,因此是有解的
oneleaf 写道:
木杆很细,不能同时通过一只蚂蚁。....编写程序,求所有蚂蚁都离开木杆的最小时间和最大时间。
不能同时通过一只蚂蚁…… 大家都死在原位了。呵呵……最大时间==最小时间==无穷大。
我觉得不会啊,蚂蚁会掉头的,所以规则是在足够短的时刻只有两边的蚂蚁才有可能出去;在任意时刻棍子上的蚂蚁一定保持开始的顺序;两边的蚂蚁在足够的时间一定可以出去,因此是有解的
- laborer
- 帖子: 1016
- 注册时间: 2005-10-25 11:15
- 联系:
代码: 全选
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
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
-
- 帖子: 2
- 注册时间: 2007-04-28 18:17
写完程序才发现规律
代码: 全选
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