当前时区为 UTC + 8 小时



发表新帖 回复这个主题  [ 25 篇帖子 ]  前往页数 1, 2  下一页
作者 内容
1 楼 
 文章标题 : 一道习题,据说是百度的面试题目.
帖子发表于 : 2006-11-13 12:52 
论坛管理员

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


页首
 用户资料  
 
2 楼 
 文章标题 :
帖子发表于 : 2006-11-13 12:53 
论坛管理员

注册: 2005-03-27 0:06
帖子: 10116
系统: Ubuntu 12.04
送出感谢: 7
接收感谢: 128
代码:
#!/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


页首
 用户资料  
 
3 楼 
 文章标题 :
帖子发表于 : 2006-11-22 23:34 

注册: 2006-07-22 18:44
帖子: 61
送出感谢: 0 次
接收感谢: 0 次
厉害~


页首
 用户资料  
 
4 楼 
 文章标题 :
帖子发表于 : 2006-12-02 15:52 

注册: 2006-05-03 12:02
帖子: 9
送出感谢: 0 次
接收感谢: 0 次
把你的程序稍微简化了一下
不清楚为什么你会安毫米计算,可能是怕相遇到非整数厘米的位置,但程序的设计的开始位置很好,不会出现这种情况
把程序稍微改了一下
即使出现在非整数厘米的地方也无所谓
哦,还有,题目中的位置和程序中的不一样,不知道哪个是错的
代码:
#!/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]


页首
 用户资料  
 
5 楼 
 文章标题 :
帖子发表于 : 2006-12-03 15:22 
论坛管理员

注册: 2005-03-27 0:06
帖子: 10116
系统: Ubuntu 12.04
送出感谢: 7
接收感谢: 128
呵呵,应该是我写的时候马虎了


页首
 用户资料  
 
6 楼 
 文章标题 : Re: 一道习题,据说是百度的面试题目.
帖子发表于 : 2007-01-18 12:18 

注册: 2007-01-13 20:22
帖子: 15
送出感谢: 0 次
接收感谢: 0 次
oneleaf 写道:
木杆很细,不能同时通过一只蚂蚁。....编写程序,求所有蚂蚁都离开木杆的最小时间和最大时间。


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


页首
 用户资料  
 
7 楼 
 文章标题 :
帖子发表于 : 2007-01-18 12:49 
头像

注册: 2006-04-12 20:05
帖子: 8495
地址: 杭州
送出感谢: 0 次
接收感谢: 8
我要开始学python了!


页首
 用户资料  
 
8 楼 
 文章标题 :
帖子发表于 : 2007-01-18 15:04 

注册: 2006-11-18 15:40
帖子: 452
送出感谢: 0 次
接收感谢: 0 次
晕了,题目差点没看明白


_________________
linux什么最重要?硬件要旧,软件要新!
Ubuntu什么最重要?源要全!网要快!
不是你不明白,是linux变化快
人品也很重要


页首
 用户资料  
 
9 楼 
 文章标题 : 我也来凑热闹
帖子发表于 : 2007-01-18 19:58 

注册: 2006-08-02 23:33
帖子: 13
送出感谢: 0 次
接收感谢: 0 次
代码:
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)


页首
 用户资料  
 
10 楼 
 文章标题 : 怎么回事? 空格没了
帖子发表于 : 2007-01-18 19:59 

注册: 2006-08-02 23:33
帖子: 13
送出感谢: 0 次
接收感谢: 0 次
代码:
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)


页首
 用户资料  
 
11 楼 
 文章标题 : 使用code还是没辙,斑竹帮我删除吧
帖子发表于 : 2007-01-18 20:08 

注册: 2006-08-02 23:33
帖子: 13
送出感谢: 0 次
接收感谢: 0 次
另外to :

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


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


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


页首
 用户资料  
 
12 楼 
 文章标题 :
帖子发表于 : 2007-02-06 6:25 
头像

注册: 2005-10-25 11:15
帖子: 1016
送出感谢: 0 次
接收感谢: 1
代码:
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


页首
 用户资料  
 
13 楼 
 文章标题 :
帖子发表于 : 2007-03-18 17:34 
头像

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


页首
 用户资料  
 
14 楼 
 文章标题 :
帖子发表于 : 2007-04-28 18:21 

注册: 2007-04-28 18:17
帖子: 2
送出感谢: 0 次
接收感谢: 0 次
写完程序才发现规律
代码:
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


页首
 用户资料  
 
15 楼 
 文章标题 :
帖子发表于 : 2007-04-28 18:50 

注册: 2005-10-28 17:40
帖子: 172
送出感谢: 0 次
接收感谢: 0 次
碰头就调头不就是等于无干扰地继续走下去吗?


页首
 用户资料  
 
显示帖子 :  排序  
发表新帖 回复这个主题  [ 25 篇帖子 ]  前往页数 1, 2  下一页

当前时区为 UTC + 8 小时


在线用户

正在浏览此版面的用户:没有注册用户 和 2 位游客


不能 在这个版面发表主题
不能 在这个版面回复主题
不能 在这个版面编辑帖子
不能 在这个版面删除帖子
不能 在这个版面提交附件

前往 :  
本站点为公益性站点,用于推广开源自由软件,由 DiaHosting VPSBudgetVM VPS 提供服务。
我们认为:软件应可免费取得,软件工具在各种语言环境下皆可使用,且不会有任何功能上的差异;
人们应有定制和修改软件的自由,且方式不受限制,只要他们自认为合适。

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
简体中文语系由 王笑宇 翻译