免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12下一页
最近访问板块 发新帖
查看: 3336 | 回复: 14

求大家帮忙看一道题 [复制链接]

论坛徽章:
0
发表于 2013-03-13 15:15 |显示全部楼层
-   Acm改编:--------------------------------------------------------------------------------------
Problem
有一根m厘米的细木杆,杆上非始末端不同位置存在k个蚂蚁。蚂蚁的目标是全部从木杆上离开,但在细木杆上只会朝前走或调头而不能后退。当任意两只蚂蚁碰头时,会同时调头朝反方向走。假定木杆很细,只能同时通过一只蚂蚁;蚂蚁长度可忽略且每秒钟可以走1厘米的距离。

Input
本题给定数据为两行,第一行是整数m(25<m<100);
第二行为k个整数(2<=k<=5),分别代表k个蚂蚁的位置;值代表离木杆始端的距离,若为正数则蚂蚁开始时头朝向末端,为负数则蚂蚁开始时头朝向始端。

Output
对于给定数据和规则,输出蚂蚁全部离开需要的秒数t及最后离开蚂蚁的初始位置值k(带正负号),用空格分开。

Sample Input
27
3 -7 11 -17 23

Sample Output
24 11

----------------------------------------------------------------------------------------------------------------------------------------------
我用python写的
现在只让返回时间先不考虑哪只最后离开


  1. def ant(m,*args):
  2.     t = 0
  3.     x = []
  4.     xx = [i for i in range(1,m)] #在木桥长度遍历
  5.     temp = []
  6.     #temp = (i for i in x if i in xx)
  7.     count = len(temp)
  8.     for arg in args:
  9.         x.append(arg)
  10.     num = len(x)
  11.     #last = x[0]
  12.     #return left
  13.     while 1:
  14.         if count != 1:
  15.             x = [i+1 for i in x]
  16.             t += 1
  17.             temp = (i for i in x if abs(i) in xx)
  18.             for j in range(0,num):
  19.                 for k in range(0,num):
  20.                     if j != k and abs(x[j]) == abs(x[k]):
  21.                         x[j] = -x[j]
  22.                         x[k] = -x[k]
  23.         else:
  24.             return t

  25.         

  26.         
  27. #print (ant(10,-1,5))
复制代码
然后Shell就各种假死,我觉得没写错啊。
有哪位能帮忙看看或者示写一下给我参照参照的。万分感谢。

论坛徽章:
0
发表于 2013-03-13 16:38 |显示全部楼层
新人不懂
我没有看明白题意
是要输入一个值来模拟什么吗?

论坛徽章:
0
发表于 2013-03-13 17:40 |显示全部楼层
input
一个是 长度 比如例子中的 27(桥的长度)
一个是 蚂蚁的坐标

论坛徽章:
1
15-16赛季CBA联赛之新疆
日期:2017-03-09 12:33:45
发表于 2013-03-13 22:16 |显示全部楼层
本帖最后由 jeppeter 于 2013-03-13 22:46 编辑

回复 1# lapertem44


    下面是我测试过的代码,你可以再测试一下,如果有错,告诉我。
  1. def ValidateAnts(l,a):
  2.         lastone = 0.0
  3.         for v in a:
  4.                 if abs(v) <= 0.0 or abs(v) >= l:
  5.                         raise Exception('error input %d for long %d'%(v,l))
  6.                 if abs(v) < abs(lastone):
  7.                         raise Exception('input value %d or ascending order'%(v))
  8.                 lastone = v

  9. def AntSplit(l,a):
  10.         lastone = 0
  11.         totalsize = 0
  12.         pos = list()
  13.         # we assume first one to be select
  14.         lastsel = 1
  15.         ValidateAnts(l,a)
  16.         for i in xrange(1,len(a)+1):
  17.                 pos.append(i)
  18.         cura = []
  19.         for v in a:
  20.                 cura.append(float(v))
  21.         logging.info('a is %s'%(repr(a)))
  22.         while len(cura) > 0 :
  23.                 leastsize = l
  24.                 lastv = cura[0]
  25.                 if lastv < 0:
  26.                         leastsize = abs(lastv)                       
  27.                 for v in cura[1:]:
  28.                         # if we have 2 value
  29.                         # if we have the opposite direction
  30.                         # so we calcuate the most size to step when
  31.                         # we should test
  32.                         if lastv >0 and v < 0:
  33.                                 size = (abs(v) - abs(lastv))/2
  34.                                 if size < leastsize :
  35.                                         leastsize = size
  36.                         lastv = v
  37.                 if cura[-1] > 0:
  38.                         size = l - abs(cura[-1])
  39.                         if size < leastsize:
  40.                                 leastsize = size
  41.                 # now we do not met in the way
  42.                 if leastsize == l:
  43.                         if cura[0] > 0:
  44.                                 # if it is the leftmost ,so it will
  45.                                 lastsel = pos[0]
  46.                                 # now to set the one
  47.                                 totalsize += (l - cura[0])
  48.                         else:
  49.                                 lastsel = pos[-1]
  50.                                 # now to set the step
  51.                                 totalsize += (l + cura[-1])
  52.                         break
  53.                 logging.info('leastsize %f'%(leastsize))
  54.                 # now to check for the
  55.                 curb = []
  56.                 lastone = cura[0]+leastsize
  57.                 for i in xrange(1,len(cura)):
  58.                         # now to modify the value
  59.                         v = cura[i] + leastsize
  60.                         if abs(lastone) == abs(v):
  61.                                 # if we met ,so turn opposite
  62.                                 lastone = -lastone
  63.                                 v = -v
  64.                         #logging.info('push %f into curb v %f'%(lastone,v))
  65.                         curb.append(lastone)
  66.                         lastone = v
  67.                 # we append last one when nothing is on
  68.                 #logging.info('push %f into curb'%(lastone))
  69.                 curb.append(lastone)
  70.                 assert(len(curb) == len(cura))
  71.                 logging.info('len curb(%d) len cura (%d)'%(len(curb),len(cura)))
  72.                 logging.info('curb %s'%(repr(curb)))
  73.                 #assert(len(curb) == len(cura))
  74.                 totalsize += leastsize
  75.                 cura = []
  76.                 for i in xrange(0,len(curb)):
  77.                         v = curb[i]
  78.                         if abs(v) > 0 and abs(v) < l:
  79.                                 cura.append(v)
  80.                         else:
  81.                                 logging.info('delete %d %d'%(i,pos[i]))
  82.                                 lastsel = pos[i]
  83.                                 del pos[i]
  84.                 logging.info('cura %s'%(repr(cura)))
  85.                 logging.info('pos %s'%(repr(pos)))
  86.                        

  87.         return lastsel,totalsize
复制代码
这里解释一下代码,
   函数的输入参数是两个:
  1, l 就是你前面所说的长度
   2,  a,就是你所说的要输入的数列。
  这里的第11-22行是初始化一些参数,
  生成 cura表示是我们要处理的数列,这里把数据变成float类型,是更好的把你的问题变成可能是因为会出现0.5的数字处理。
  而pos就是一个数列,可以得到最后一个离开棒子的蚂蚁的初始位置
  

24-41 :计算,不引起数据变化的最大长度,这里要满足两个条件:
          1, 没有蚂蚁走出棒子,换句话说,就是没有一个值abs(v) <= 0 or abs(v) >= l (棒子长度)
          2, 没有蚂蚁要转向。
         26-27 是因为,有可能最左边的蚂蚁是向左爬,那它可能不在棒子上,就是在最左边离棒子的距离。
         33-36 是计算,如果两个蚂蚁是相向而行,也就是在左边的蚂蚁向右,而在右边的蚂蚁向左,则它们会在多少时间相遇。
          38-41 是计算,如果最右边的蚂蚁向右爬,它可能不在棒子上,与最右边的距离。
         以上的计算,就是得到当前引起变化的最小距离。

43-53  前面的计算,可能会得到最大值就是棒子的长度,(现在来看,不会出现),这个时候,就是已经结束了。这个值就是所有的蚂蚁向一个方向,或者是向左,或者是向右,
          44-48 如果向右,则取最左边的蚂蚁距离最右端点的距离是步长。 而现在保留的最左边的蚂蚁当时的点就是最后一个蚂蚁的最初点。pos[0]
          49-53 如果向左,则取最右边的蚂蚁距离最左端点的距离是步长。 而现在保留的最右边的蚂蚁当时的点就是最后一个蚂蚁的最初点。pos[-1]


57-70 生成因为改变了,下一次迭代所有的蚂蚁的位置与方向信息。
         57 保留前一次,因为前一次,会与当前的有关系。
         59-67 生成下一次的蚂蚁位置与方向。
                   60 这个就是得到当前的蚂蚁的位置,因为这个蚂蚁如果是-7+2 表示向右,前进2,那位置就是-5
                   61 如果两个蚂蚁碰头。这个是前一个(就是左边的蚂蚁)与后一个(就是右边的蚂蚁)相遇了,这个时候,要它们转向。
                        所以, 这个时候,要修改原来的符号,这样就转向了。
          70 ,这个可能整个数据没有了,那就把最后一个加入。

75 加上了这一次引起变化,步长是多少。

76-85  这一次得到下一次迭代的蚂蚁位置。
         79-80 ,如果蚂蚁不在边界的位置(也就是在棒子的两头),则加入下一次的迭代。
          82-84 ,如果已经在边界的位置,则去除这个蚂蚁,它不在下一次迭代的范围内。
            83 是表示最后一个离开棒子的蚂蚁的初始位置,在while循环之外会有用。
            84 去除这个位置的信息,


上面的解释希望能对你有帮助。谢谢。         

论坛徽章:
1
15-16赛季CBA联赛之新疆
日期:2017-03-09 12:33:45
发表于 2013-03-13 22:49 |显示全部楼层
回复 1# lapertem44


    如果要让上面的代码运行,请在所有的代码前面加上
    import logging

论坛徽章:
2
射手座
日期:2014-10-10 15:59:4715-16赛季CBA联赛之上海
日期:2016-03-03 10:27:14
发表于 2013-03-13 23:35 |显示全部楼层

论坛徽章:
1
15-16赛季CBA联赛之新疆
日期:2017-03-09 12:33:45
发表于 2013-03-14 07:22 |显示全部楼层
回复 1# lapertem44
  1. def ValidateAnts(l,a):
  2.         lastone = 0.0
  3.         for v in a:
  4.                 if abs(v) <= 0.0 or abs(v) >= l:
  5.                         raise Exception('error input %d for long %d'%(v,l))
  6.                 if abs(v) < abs(lastone):
  7.                         raise Exception('input value %d or ascending order'%(v))
  8.                 lastone = v

  9. def AntSplit(l,a):
  10.         lastone = 0
  11.         totalsize = 0
  12.         pos = list()
  13.         # we assume first one to be select
  14.         lastsel = 1
  15.         ValidateAnts(l,a)
  16.         for i in xrange(1,len(a)+1):
  17.                 pos.append(i)
  18.         cura = []
  19.         for v in a:
  20.                 cura.append(float(v))
  21.         logging.info('a is %s'%(repr(a)))
  22.         while len(cura) > 0 :
  23.                 leastsize = l
  24.                 lastv = cura[0]
  25.                 if lastv < 0:
  26.                         leastsize = abs(lastv)                       
  27.                 for v in cura[1:]:
  28.                         # if we have 2 value
  29.                         # if we have the opposite direction
  30.                         # so we calcuate the most size to step when
  31.                         # we should test
  32.                         if lastv >0 and v < 0:
  33.                                 size = (abs(v) - abs(lastv))/2
  34.                                 if size < leastsize :
  35.                                         leastsize = size
  36.                         lastv = v
  37.                 if cura[-1] > 0:
  38.                         size = l - abs(cura[-1])
  39.                         if size < leastsize:
  40.                                 leastsize = size
  41.                 # now we do not met in the way
  42.                 if leastsize == l:
  43.                         if cura[0] > 0:
  44.                                 # if it is the leftmost ,so it will
  45.                                 lastsel = pos[0]
  46.                                 # now to set the one
  47.                                 totalsize += (l - cura[0])
  48.                         else:
  49.                                 lastsel = pos[-1]
  50.                                 # now to set the step
  51.                                 totalsize += (l + cura[-1])
  52.                         break
  53.                 logging.info('leastsize %f'%(leastsize))
  54.                 # now to check for the
  55.                 curb = []
  56.                 lastone = cura[0]+leastsize
  57.                 for i in xrange(1,len(cura)):
  58.                         # now to modify the value
  59.                         v = cura[i] + leastsize
  60.                         if abs(lastone) == abs(v):
  61.                                 # if we met ,so turn opposite
  62.                                 lastone = -lastone
  63.                                 v = -v
  64.                         #logging.info('push %f into curb v %f'%(lastone,v))
  65.                         curb.append(lastone)
  66.                         lastone = v
  67.                 # we append last one when nothing is on
  68.                 #logging.info('push %f into curb'%(lastone))
  69.                 curb.append(lastone)
  70.                 assert(len(curb) == len(cura))
  71.                 logging.info('len curb(%d) len cura (%d)'%(len(curb),len(cura)))
  72.                 logging.info('curb %s'%(repr(curb)))
  73.                 #assert(len(curb) == len(cura))
  74.                 totalsize += leastsize
  75.                 cura = []
  76.                 delpos = []
  77.                 for i in xrange(0,len(curb)):
  78.                         v = curb[i]
  79.                         if abs(v) > 0 and abs(v) < l:
  80.                                 cura.append(v)
  81.                         else:
  82.                                 logging.info('delete %d %d'%(i,pos[i]))
  83.                                 lastsel = pos[i]
  84.                                 delpos.append(i)
  85.                 while len(delpos) > 0:
  86.                         i = delpos.pop()
  87.                         del pos[i]
  88.                 logging.info('cura %s'%(repr(cura)))
  89.                 logging.info('pos %s'%(repr(pos)))
  90.                        

  91.         return lastsel,totalsize
复制代码
这里的代码有修正。
1,对于返回值,lastsel表明的是最后一个退出棒子的蚂蚁的最初位于棒子左边的第几个
2, 修改了delpos 这个是可以处理两个 以上被删除的点。
   

ant.rar

1.26 KB, 下载次数: 1

源代码

论坛徽章:
3
CU大牛徽章
日期:2013-03-13 15:32:35CU大牛徽章
日期:2013-03-13 15:38:15CU大牛徽章
日期:2013-03-13 15:38:52
发表于 2013-03-14 10:40 |显示全部楼层
来看看。。python还不是太好的说

论坛徽章:
21
白羊座
日期:2013-08-23 15:49:17金牛座
日期:2013-10-08 17:00:03处女座
日期:2013-10-12 11:54:11CU十二周年纪念徽章
日期:2013-10-24 15:41:34午马
日期:2013-11-27 14:07:21巨蟹座
日期:2013-12-04 10:56:03水瓶座
日期:2013-12-04 15:58:00亥猪
日期:2014-05-24 16:02:3115-16赛季CBA联赛之辽宁
日期:2016-11-07 13:52:53戌狗
日期:2013-08-23 16:15:31白羊座
日期:2013-08-24 21:59:24巨蟹座
日期:2013-08-25 16:34:24
发表于 2013-03-14 12:19 |显示全部楼层
好深啊,不会。

论坛徽章:
0
发表于 2013-03-14 14:19 |显示全部楼层
围观学习
好深奥~
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

DTCC2020中国数据库技术大会

【架构革新 高效可控】2020年12月21日-23日第十一届中国数据库技术大会将在北京隆重召开。

大会设置2大主会场,20+技术专场,将邀请超百位行业专家,重点围绕数据架构、AI与大数据、传统企业数据库实践和国产开源数据库等内容展开分享和探讨,为广大数据领域从业人士提供一场年度盛会和交流平台。

http://dtcc.it168.com


大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP