免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12
最近访问板块 发新帖
楼主: lapertem44

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

论坛徽章:
4
金牛座
日期:2013-10-11 16:12:50卯兔
日期:2014-07-31 09:17:19辰龙
日期:2014-08-08 09:28:02狮子座
日期:2014-09-14 20:32:05
发表于 2013-03-14 18:36 |显示全部楼层
本帖最后由 ssfjhh 于 2013-03-14 18:44 编辑

我也贴一个,没有验证用户输入的数据的有效性。
  1. def ant(m, *position):
  2.     t = 0
  3.     p = {i:i for i in position}
  4.     temp = []
  5.     result = []
  6.     while True:
  7.         t += 1
  8.         p= {k:v+1 for k,v in p.items()}
  9.         for i in tuple(p.keys()):
  10.             if abs(p[i]) in (0,m):
  11.                 result.append((i,t))
  12.                 p.pop(i)
  13.         if p == {}:
  14.             return result
  15.         temp = [abs(i) for i in p.values()]
  16.         for k,v in p.items():
  17.             if temp.count(abs(v)) == 2:
  18.                 p[k] = -v
  19. print(ant(27,3,-7,11,-17,23))
复制代码
贴个结果,看对否。
[(23, 4), (3, 7), (-17, 16), (-7, 17), (11, 24)]

列表的顺序表示先后离开的顺序。

论坛徽章:
4
金牛座
日期:2013-10-11 16:12:50卯兔
日期:2014-07-31 09:17:19辰龙
日期:2014-08-08 09:28:02狮子座
日期:2014-09-14 20:32:05
发表于 2013-03-14 21:24 |显示全部楼层
本帖最后由 ssfjhh 于 2013-03-14 21:28 编辑

回复 11# ssfjhh


    ls的代码是不对的,没有考虑到两只蚂蚁可能在非整数的位置相遇的情况。修改代码如下。
  1. def ant(m, *position):
  2.     t = 0
  3.     p = {i:i for i in position}
  4.     temp = []
  5.     result = []
  6.     x = []
  7.     while True:
  8.         t += 1
  9.         x = sorted(((k,v) for k,v in p.items()), key = lambda j: abs(j[1]))
  10.         for i in range(len(x)-1):
  11.             if x[i][1] > 0 and x[i+1][1] < 0 and x[i+1][1] + x[i][1] > -2:
  12.                 p[x[i][0]] = x[i+1][1]
  13.                 p[x[i+1][0]] = x[i][1]
  14.         p = {k:v+1 for k,v in p.items()}
  15.         for i in tuple(p.keys()):
  16.             if abs(p[i]) in (0,m):
  17.                 result.append((i,t))
  18.                 p.pop(i)
  19.         if p == {}:
  20.             return result
  21.         temp = [abs(i) for i in p.values()]
  22.         for k,v in p.items():
  23.             if temp.count(abs(v)) == 2:
  24.                 p[k] = -v
  25.                
  26. print(ant(27,3,-7,11,-17,23))
复制代码
这段代码的运行结果如下:
  1. [(23, 4), (-7, 7), (-17, 16), (3, 17), (11, 24)]
复制代码
程序的原理是蚂蚁的初始位置为整数位置,那么在整数秒数时一定在整数位置。

论坛徽章:
4
金牛座
日期:2013-10-11 16:12:50卯兔
日期:2014-07-31 09:17:19辰龙
日期:2014-08-08 09:28:02狮子座
日期:2014-09-14 20:32:05
发表于 2013-03-15 09:11 |显示全部楼层
lz,未经你允许我给转到c版了,这里太冷清。
地址:
http://bbs.chinaunix.net/thread-4071846-1-1.html

论坛徽章:
4
金牛座
日期:2013-10-11 16:12:50卯兔
日期:2014-07-31 09:17:19辰龙
日期:2014-08-08 09:28:02狮子座
日期:2014-09-14 20:32:05
发表于 2013-03-15 09:38 |显示全部楼层
再贴一个,把输出格式给调整了一下
  1. def ant(m, *position):
  2.     t = 0
  3.     p = {i:i for i in position}
  4.     temp = []
  5.     result = {}
  6.     x = []
  7.     while True:
  8.         t += 1
  9.         x = sorted(((k,v) for k,v in p.items()), key = lambda j: abs(j[1]))
  10.         for i in range(len(x)-1):
  11.             if x[i][1] > 0 and x[i+1][1] < 0 and x[i+1][1] + x[i][1] > -2:
  12.                 p[x[i][0]] = x[i+1][1]
  13.                 p[x[i+1][0]] = x[i][1]
  14.         p = {k:v+1 for k,v in p.items()}
  15.         for i in tuple(p.keys()):
  16.             if abs(p[i]) in (0,m):
  17.                 try:
  18.                     result[t].append(i)
  19.                 except:
  20.                     result[t] = [i]
  21.                 p.pop(i)
  22.         if p == {}:
  23.             return result
  24.         temp = [abs(i) for i in p.values()]
  25.         for k,v in p.items():
  26.             if temp.count(abs(v)) == 2:
  27.                 p[k] = -v

  28. result = ant(27,3,-7,11,-17,23)
  29. print("time", "\t:\t", "ant")
  30. for k,v in sorted(result.items()):
  31.     print(k,'\t:\t', ','.join(map(str,v)))
复制代码
  1. >>>
  2. time         :         ant
  3. 4         :         23
  4. 7         :         -7
  5. 16         :         -17
  6. 17         :         3
  7. 24         :         11
  8. >>>
复制代码
“:”左边表示离开的时间,右边表示离开的蚂蚁,如果“:”右边有两个值,表示这两只蚂蚁是同时离开的。

论坛徽章:
4
金牛座
日期:2013-10-11 16:12:50卯兔
日期:2014-07-31 09:17:19辰龙
日期:2014-08-08 09:28:02狮子座
日期:2014-09-14 20:32:05
发表于 2013-03-15 14:56 |显示全部楼层
11楼的情况没有考虑到两只蚂蚁在非整数位置相遇的情况,然后我在12楼里加入了相应的代码。
但是新加代码有问题,计算出的最大时间是对的,但是原始蚂蚁的位置是有误的。

很讽刺的是原来没有考虑到这种情况的代码反倒是对的,我动手计算的。

后来看了c版高手的回复,然后我又写了一个代码来计算,非常精简,没有经过证明,我自己验证了一两个例子,结果是正确的。求验证
  1. def ant(m, *args):
  2.     p = sorted(args, key = abs)
  3.     t = [-i for i in p if i<0] + [m- i for i in p if i >0]
  4.     return sorted((k,v) for k,v in zip(t,p))
  5. print(ant(27,3,-7,11,-17,23))
复制代码
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP