Chinaunix
标题:
求大家帮忙看一道题
[打印本页]
作者:
lapertem44
时间:
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写的
现在只让返回时间先不考虑哪只最后离开
def ant(m,*args):
t = 0
x = []
xx = [i for i in range(1,m)] #在木桥长度遍历
temp = []
#temp = (i for i in x if i in xx)
count = len(temp)
for arg in args:
x.append(arg)
num = len(x)
#last = x[0]
#return left
while 1:
if count != 1:
x = [i+1 for i in x]
t += 1
temp = (i for i in x if abs(i) in xx)
for j in range(0,num):
for k in range(0,num):
if j != k and abs(x[j]) == abs(x[k]):
x[j] = -x[j]
x[k] = -x[k]
else:
return t
#print (ant(10,-1,5))
复制代码
然后Shell就各种假死，我觉得没写错啊。
有哪位能帮忙看看或者示写一下给我参照参照的。万分感谢。
作者:
Linux_JinYuan
时间:
2013-03-13 16:38
新人不懂
我没有看明白题意
是要输入一个值来模拟什么吗？
作者:
lapertem44
时间:
2013-03-13 17:40
input
一个是 长度 比如例子中的 27（桥的长度）
一个是 蚂蚁的坐标
作者:
jeppeter
时间:
2013-03-13 22:16
本帖最后由 jeppeter 于 2013-03-13 22:46 编辑
回复
1#
lapertem44
下面是我测试过的代码，你可以再测试一下，如果有错，告诉我。
def ValidateAnts(l,a):
lastone = 0.0
for v in a:
if abs(v) <= 0.0 or abs(v) >= l:
raise Exception('error input %d for long %d'%(v,l))
if abs(v) < abs(lastone):
raise Exception('input value %d or ascending order'%(v))
lastone = v
def AntSplit(l,a):
lastone = 0
totalsize = 0
pos = list()
# we assume first one to be select
lastsel = 1
ValidateAnts(l,a)
for i in xrange(1,len(a)+1):
pos.append(i)
cura = []
for v in a:
cura.append(float(v))
logging.info('a is %s'%(repr(a)))
while len(cura) > 0 :
leastsize = l
lastv = cura[0]
if lastv < 0:
leastsize = abs(lastv)
for v in cura[1:]:
# if we have 2 value
# if we have the opposite direction
# so we calcuate the most size to step when
# we should test
if lastv >0 and v < 0:
size = (abs(v) - abs(lastv))/2
if size < leastsize :
leastsize = size
lastv = v
if cura[-1] > 0:
size = l - abs(cura[-1])
if size < leastsize:
leastsize = size
# now we do not met in the way
if leastsize == l:
if cura[0] > 0:
# if it is the leftmost ,so it will
lastsel = pos[0]
# now to set the one
totalsize += (l - cura[0])
else:
lastsel = pos[-1]
# now to set the step
totalsize += (l + cura[-1])
break
logging.info('leastsize %f'%(leastsize))
# now to check for the
curb = []
lastone = cura[0]+leastsize
for i in xrange(1,len(cura)):
# now to modify the value
v = cura[i] + leastsize
if abs(lastone) == abs(v):
# if we met ,so turn opposite
lastone = -lastone
v = -v
#logging.info('push %f into curb v %f'%(lastone,v))
curb.append(lastone)
lastone = v
# we append last one when nothing is on
#logging.info('push %f into curb'%(lastone))
curb.append(lastone)
assert(len(curb) == len(cura))
logging.info('len curb(%d) len cura (%d)'%(len(curb),len(cura)))
logging.info('curb %s'%(repr(curb)))
#assert(len(curb) == len(cura))
totalsize += leastsize
cura = []
for i in xrange(0,len(curb)):
v = curb[i]
if abs(v) > 0 and abs(v) < l:
cura.append(v)
else:
logging.info('delete %d %d'%(i,pos[i]))
lastsel = pos[i]
del pos[i]
logging.info('cura %s'%(repr(cura)))
logging.info('pos %s'%(repr(pos)))
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 去除这个位置的信息，
上面的解释希望能对你有帮助。谢谢。
作者:
jeppeter
时间:
2013-03-13 22:49
回复
1#
lapertem44
如果要让上面的代码运行，请在所有的代码前面加上
import logging
作者:
yinyuemi
时间:
2013-03-13 23:35
回复
1#
lapertem44
http://bbs.chinaunix.net/thread-3575029-1-1.html
作者:
jeppeter
时间:
2013-03-14 07:22
回复
1#
lapertem44
def ValidateAnts(l,a):
lastone = 0.0
for v in a:
if abs(v) <= 0.0 or abs(v) >= l:
raise Exception('error input %d for long %d'%(v,l))
if abs(v) < abs(lastone):
raise Exception('input value %d or ascending order'%(v))
lastone = v
def AntSplit(l,a):
lastone = 0
totalsize = 0
pos = list()
# we assume first one to be select
lastsel = 1
ValidateAnts(l,a)
for i in xrange(1,len(a)+1):
pos.append(i)
cura = []
for v in a:
cura.append(float(v))
logging.info('a is %s'%(repr(a)))
while len(cura) > 0 :
leastsize = l
lastv = cura[0]
if lastv < 0:
leastsize = abs(lastv)
for v in cura[1:]:
# if we have 2 value
# if we have the opposite direction
# so we calcuate the most size to step when
# we should test
if lastv >0 and v < 0:
size = (abs(v) - abs(lastv))/2
if size < leastsize :
leastsize = size
lastv = v
if cura[-1] > 0:
size = l - abs(cura[-1])
if size < leastsize:
leastsize = size
# now we do not met in the way
if leastsize == l:
if cura[0] > 0:
# if it is the leftmost ,so it will
lastsel = pos[0]
# now to set the one
totalsize += (l - cura[0])
else:
lastsel = pos[-1]
# now to set the step
totalsize += (l + cura[-1])
break
logging.info('leastsize %f'%(leastsize))
# now to check for the
curb = []
lastone = cura[0]+leastsize
for i in xrange(1,len(cura)):
# now to modify the value
v = cura[i] + leastsize
if abs(lastone) == abs(v):
# if we met ,so turn opposite
lastone = -lastone
v = -v
#logging.info('push %f into curb v %f'%(lastone,v))
curb.append(lastone)
lastone = v
# we append last one when nothing is on
#logging.info('push %f into curb'%(lastone))
curb.append(lastone)
assert(len(curb) == len(cura))
logging.info('len curb(%d) len cura (%d)'%(len(curb),len(cura)))
logging.info('curb %s'%(repr(curb)))
#assert(len(curb) == len(cura))
totalsize += leastsize
cura = []
delpos = []
for i in xrange(0,len(curb)):
v = curb[i]
if abs(v) > 0 and abs(v) < l:
cura.append(v)
else:
logging.info('delete %d %d'%(i,pos[i]))
lastsel = pos[i]
delpos.append(i)
while len(delpos) > 0:
i = delpos.pop()
del pos[i]
logging.info('cura %s'%(repr(cura)))
logging.info('pos %s'%(repr(pos)))
return lastsel,totalsize
复制代码
这里的代码有修正。
1，对于返回值，lastsel表明的是最后一个退出棒子的蚂蚁的最初位于棒子左边的第几个
2， 修改了delpos 这个是可以处理两个 以上被删除的点。
ant.rar
2013-03-14 07:22 上传
点击文件名下载附件
1.26 KB, 下载次数: 1
源代码
作者:
g361031315
时间:
2013-03-14 10:40
来看看。。python还不是太好的说
作者:
zongg
时间:
2013-03-14 12:19
好深啊，不会。
作者:
Linux_JinYuan
时间:
2013-03-14 14:19
围观学习
好深奥~
作者:
ssfjhh
时间:
2013-03-14 18:36
本帖最后由 ssfjhh 于 2013-03-14 18:44 编辑
我也贴一个，没有验证用户输入的数据的有效性。
def ant(m, *position):
t = 0
p = {i:i for i in position}
temp = []
result = []
while True:
t += 1
p= {k:v+1 for k,v in p.items()}
for i in tuple(p.keys()):
if abs(p[i]) in (0,m):
result.append((i,t))
p.pop(i)
if p == {}:
return result
temp = [abs(i) for i in p.values()]
for k,v in p.items():
if temp.count(abs(v)) == 2:
p[k] = -v
print(ant(27,3,-7,11,-17,23))
复制代码
贴个结果，看对否。
[(23, 4), (3, 7), (-17, 16), (-7, 17), (11, 24)]
列表的顺序表示先后离开的顺序。
作者:
ssfjhh
时间:
2013-03-14 21:24
本帖最后由 ssfjhh 于 2013-03-14 21:28 编辑
回复
11#
ssfjhh
ls的代码是不对的，没有考虑到两只蚂蚁可能在非整数的位置相遇的情况。修改代码如下。
def ant(m, *position):
t = 0
p = {i:i for i in position}
temp = []
result = []
x = []
while True:
t += 1
x = sorted(((k,v) for k,v in p.items()), key = lambda j: abs(j[1]))
for i in range(len(x)-1):
if x[i][1] > 0 and x[i+1][1] < 0 and x[i+1][1] + x[i][1] > -2:
p[x[i][0]] = x[i+1][1]
p[x[i+1][0]] = x[i][1]
p = {k:v+1 for k,v in p.items()}
for i in tuple(p.keys()):
if abs(p[i]) in (0,m):
result.append((i,t))
p.pop(i)
if p == {}:
return result
temp = [abs(i) for i in p.values()]
for k,v in p.items():
if temp.count(abs(v)) == 2:
p[k] = -v
print(ant(27,3,-7,11,-17,23))
复制代码
这段代码的运行结果如下：
[(23, 4), (-7, 7), (-17, 16), (3, 17), (11, 24)]
复制代码
程序的原理是蚂蚁的初始位置为整数位置，那么在整数秒数时一定在整数位置。
作者:
ssfjhh
时间:
2013-03-15 09:11
lz，未经你允许我给转到c版了，这里太冷清。
地址：
http://bbs.chinaunix.net/thread-4071846-1-1.html
作者:
ssfjhh
时间:
2013-03-15 09:38
再贴一个，把输出格式给调整了一下
def ant(m, *position):
t = 0
p = {i:i for i in position}
temp = []
result = {}
x = []
while True:
t += 1
x = sorted(((k,v) for k,v in p.items()), key = lambda j: abs(j[1]))
for i in range(len(x)-1):
if x[i][1] > 0 and x[i+1][1] < 0 and x[i+1][1] + x[i][1] > -2:
p[x[i][0]] = x[i+1][1]
p[x[i+1][0]] = x[i][1]
p = {k:v+1 for k,v in p.items()}
for i in tuple(p.keys()):
if abs(p[i]) in (0,m):
try:
result[t].append(i)
except:
result[t] = [i]
p.pop(i)
if p == {}:
return result
temp = [abs(i) for i in p.values()]
for k,v in p.items():
if temp.count(abs(v)) == 2:
p[k] = -v
result = ant(27,3,-7,11,-17,23)
print("time", "\t:\t", "ant")
for k,v in sorted(result.items()):
print(k,'\t:\t', ','.join(map(str,v)))
复制代码
>>>
time : ant
4 : 23
7 : -7
16 : -17
17 : 3
24 : 11
>>>
复制代码
“：”左边表示离开的时间，右边表示离开的蚂蚁，如果“：”右边有两个值，表示这两只蚂蚁是同时离开的。
作者:
ssfjhh
时间:
2013-03-15 14:56
11楼的情况没有考虑到两只蚂蚁在非整数位置相遇的情况，然后我在12楼里加入了相应的代码。
但是新加代码有问题，计算出的最大时间是对的，但是原始蚂蚁的位置是有误的。
很讽刺的是原来没有考虑到这种情况的代码反倒是对的，我动手计算的。
后来看了c版高手的回复，然后我又写了一个代码来计算，非常精简，没有经过证明，我自己验证了一两个例子，结果是正确的。求验证
def ant(m, *args):
p = sorted(args, key = abs)
t = [-i for i in p if i<0] + [m- i for i in p if i >0]
return sorted((k,v) for k,v in zip(t,p))
print(ant(27,3,-7,11,-17,23))
复制代码
欢迎光临 Chinaunix (http://bbs.chinaunix.net/)
Powered by Discuz! X3.2
