Jump to 0 top | 1 navigation | 2 content | 3 extra information (sidebar) | 4 footer | 5 toolbar

Content

« 让我们从游戏开始──点灯(3)

让我们从游戏开始──点灯(4)

第三天
到目前为止，我们的进展都很顺利。不过我们的代码速度还不是很快，应该还有改进的余地。
昨天我们使用第一行生成了一个包含2^n个序列的list，我们认真看看，就会发现中间很多是对称的，比如n=3的时候100,001对称， 110,011对称。按照我们的算法，这些对称的的序列最后得到的开关桩状态也是对称的，那么我们把每得到一个解，就可以把对称的第一行组合去掉。那么同 理，如果第一行的某一个组合不是解，那么我们也可以把他去掉。这样不就减少了很多的循环次数啦。
首先判断list是否对称：

  1. def symmetric(alist):#判断list是否对称
  2. leng=len(alist)
  3. le=alist[:(leng/2)]
  4. ri=alist[-(leng/2):]
  5. ri.reverse()
  6. if le!=ri:
  7. alist.reverse()
  8. return alist
  9. else:
  10. return None

其他的都一样，我们在昨天的基础上修改一下就好了：

  1. def light(n):
  2. PosSol = [nastr.array(bstr(x).zfill(n), itemsize=1).eval().tolist() for x in xrange(2**n)]
  3. solution=zeros((n, n))#解
  4. tmpArray=zeros((2, n+2))#用来存放每一行的开关状态
  5. try:
  6. for i in range(len(PosSol)):
  7. i=PosSol[i][:]
  8. solution[0:1]=i
  9. tmpArray[0, :]=0
  10. tmpArray[1,1:-1]=i
  11. for line in range(n-1):#取n-1是因为第一行是生成的，不需要计算
  12. solution[line+1:line+2, :]=ones((1, n))-lightstats(tmpArray, n)
  13. tmpArray[:,1:-1]=solution[line:line+2, :]
  14. if sum(lightstats(tmpArray, n))==n:
  15. steps=sum(sum(solution))
  16. print solution
  17. print "Total steps:%d" % steps
  18. rev=symmetric(i)
  19. if rev!=None:
  20. print solution[:,::-1]
  21. print "Total steps:%d" % steps
  22. PosSol.remove(rev)
  23. except:
  24. pass

注意for i in range(len(PosSol))这句，这个是很多初学python的人在循环上犯的错。但是我们这里这么作是有原因的。在如果直接写for i in PosSol，那么在循环体中间对PosSol的操作不会得到你想要的结果，所以我们这样避免了这样的问题。i=PosSol[i][:]是产生一个拷 贝。免得对PosSol里面产生影响。
下面就是代码：

  1. #!/usr/bin/python
  2. # -*- coding: utf8 -*-
  3. #Filename:third2.py

  5. from numarray import *
  6. import numarray.strings as nastr
  7. from bin import bstr

  9. def lightstats(switchstats, n):
  10. TxT = [take(switchstats, [x, x+1, x+2], axis=1) for x in range(n)]
  11. [putmask(item, [1,0,1,0,0,0], [0]) for item in TxT]#去掉不相关的格子
  12. return [(sum(sum(item)))%2 for item in TxT]

  14. def symmetric(alist):#判断list是否对称
  15. leng=len(alist)
  16. le=alist[:(leng/2)]
  17. ri=alist[-(leng/2):]
  18. ri.reverse()
  19. if le!=ri:
  20. alist.reverse()
  21. return alist
  22. else:
  23. return None

  25. def light(n):
  26. PosSol = [nastr.array(bstr(x).zfill(n), itemsize=1).eval().tolist() for x in xrange(2**n)]
  27. solution=zeros((n, n))#解
  28. tmpArray=zeros((2, n+2))#用来存放每一行的开关状态
  29. try:
  30. for i in range(len(PosSol)):
  31. i=PosSol[i][:]
  32. solution[0:1]=i
  33. tmpArray[0, :]=0
  34. tmpArray[1,1:-1]=i
  35. for line in range(n-1):#取n-1是因为第一行是生成的，不需要计算
  36. solution[line+1:line+2, :]=ones((1, n))-lightstats(tmpArray, n)
  37. tmpArray[:,1:-1]=solution[line:line+2, :]
  38. if sum(lightstats(tmpArray, n))==n:
  39. steps=sum(sum(solution))
  40. print solution
  41. print "Total steps:%d" % steps
  42. rev=symmetric(i)
  43. if rev!=None:
  44. print solution[:,::-1]
  45. print "Total steps:%d" % steps
  46. PosSol.remove(rev)
  47. except:
  48. pass

  50. if __name__ == "__main__":
  51. tests = [2,3,4,5,6,7,8,9,10]
  52. for xx in tests:
  53. print "solution for %d*%d" % (xx,xx)
  54. light(xx)

既然可以用对称得到解，那么也可以用对称排除不是解的组合：

  1. def light(n):
  2. PosSol = [nastr.array(bstr(x).zfill(n), itemsize=1).eval().tolist() for x in xrange(2**n)]
  3. solution=zeros((n, n))#解
  4. tmpArray=zeros((2, n+2))#用来存放每一行的开关状态
  5. try:
  6. for i in range(len(PosSol)):
  7. i=PosSol[i][:]
  8. solution[0:1]=i
  9. tmpArray[0, :]=0
  10. tmpArray[1,1:-1]=i
  11. for line in range(n-1):#取n-1是因为第一行是生成的，不需要计算
  12. solution[line+1:line+2, :]=ones((1, n))-lightstats(tmpArray, n)
  13. tmpArray[:,1:-1]=solution[line:line+2, :]
  14. rev=symmetric(i)
  15. if sum(lightstats(tmpArray, n))==n:
  16. steps=sum(sum(solution))
  17. print solution
  18. print "Total steps:%d" % steps
  19. if rev!=None:
  20. print solution[:,::-1]
  21. print "Total steps:%d" % steps
  22. PosSol.remove(rev)
  23. else:
  24. if rev!=None:
  25. PosSol.remove(rev)
  26. except:
  27. pass

这是新的light函数。不过我们想想，我们可以把解进行旋转，得到的就是其他的解，但是不是解的组合不能旋转排除哦，原因嘛，想想就明白了。我们写一个旋转的函数：

  1. def rotatearray(array):
  2. o=zeros(shape(transpose(a)))
  3. for i in range(len(a)):
  4. b[:,i]=a[i,::-1]
  5. return o

那么就是修改以后的light函数：

  1. def light(n):
  2. allSolutions=[]
  3. PosSol = [nastr.array(bstr(x).zfill(n), itemsize=1).eval().tolist() for x in xrange(2**n)]
  4. solution=zeros((n, n))#解
  5. tmpArray=zeros((2, n+2))#用来存放每一行的开关状态
  6. try:
  7. for i in range(len(PosSol)):
  8. i=PosSol[i][:]
  9. solution[0:1]=i
  10. tmpArray[0, :]=0
  11. tmpArray[1,1:-1]=i
  12. for line in range(n-1):#取n-1是因为第一行是生成的，不需要计算
  13. solution[line+1:line+2, :]=ones((1, n))-lightstats(tmpArray, n)
  14. tmpArray[:,1:-1]=solution[line:line+2, :]
  15. if sum(lightstats(tmpArray, n))==n:
  16. steps=sum(sum(solution))
  17. temp=solution
  18. for j in range(2):
  19. for k in range(4):
  20. temp=rotateArray(temp)
  21. if temp.tolist() not in allSolutions:
  22. allSolutions.append(temp.tolist())
  23. print temp
  24. print "Total steps:%d" % steps
  25. try:
  26. PosSol.remove(temp[0, :].tolist())
  27. except:
  28. pass
  29. temp=transpose(temp)
  30. else:
  31. try:
  32. PosSol.remove(rev)
  33. except:
  34. pass
  35. except:
  36. pass

我们去掉了判断对称的函数，直接使用remove，跳过错误信息。定义了allSolutions来避免重复。
现在来总测试一下我们的成果吧：
程序 n 时间

first.py 2~4 real 3m16.271s

second.py 2~10 real 2m32.655s

second2.py 2~10 real 2m38.275s
third.py 2~10 real 2m28.386s

third2.py 2~10 real 1m32.934s
third3.py 2~10 real 1m17.786s

posted by LuluKen on May 1, 2007 8:59 PM | 0 comments
Tags: ,

  • No ratings
  • No ratings
  • No ratings
  • No ratings
  • No ratings
  • 0 ratings

Leave a comment


Already have a login?

»

» Next Space