第二天
我们完成了一个求解的程序，但是我们还不能高兴，注意到first.py最后的注释没？因为运算量太大，连5×5都完成不了（或者很难完成），就别说更大的了。看来我们还要作一些大的改进才行。
让我们再琢磨琢磨我们的在理论分析中得到的一些信息。嗯~既然灯泡的状态之和“影响格”有关，那么是否意味着开关开启的顺序是无关的？看来我们有了一个突破口。一行一行的求解的可能性是有的，但是我们要怎么作呢？让我们先来分析一下。
我们从上往下考虑，如果先确定了第一行的开关状态，那么能影响这一行的就只有第二行;确定了第二行以后能影响它的就只有第三行……这样类推的话，我们只要 穷举第一行可能的情况，然后从下面一行开始，保证上面一行的灯泡全亮。这样循环下去，到最后一行完成的时候如果就能确定这是否是一个解。看来我们从2** (n*n)已经化简到了2*n。好~好的很。
为了避免不停计算灯泡的状态，我们专门为灯泡状态添加一个表。有了昨天的基础，今天看来可以很快完成。：）
首先得到得到第一行的所有组合：
- PosSol = [nastr.array(bstr(x).zfill(n), itemsize=1).eval() for x in xrange(2**n)]
嗯~让我们停下来一下。当我们得到了第一行的灯泡状态以后，我们就确定了第二行的开关状态。由于能影响第一行的只剩第二行的开关，那么我们其实只要 把第一行的灯泡状态取反就得到了第二行的开关状态。对开关状态的判断也简单了，只需要对上两行的灯泡状态判断就可以了，真是比昨天的简单多了。
- PosSol = [nastr.array(bstr(x).zfill(n), itemsize=1).eval() for x in xrange(2**n)]
- lightStats=zeros((n, n))#灯泡的状态
- solution=zeros((n, n))#解
- tmpArray=zeros((2, n+2))#用来存放每一行的开关状态
- for i in PosSol:
- solution[0:1]=i.copy()
- tmpArray[0, :]=0
- tmpArray[1,1:-1]=i.copy()
- for line in range(n-1):#取n-1是因为第一行是生成的，不需要计算
- TxT = [take(tmpArray, [x, x+1, x+2], axis=1) for x in range(n)]
- [putmask(item, [1,0,1,0,0,0], [0]) for item in TxT]#我们要由上一行得到下一行的状态
- solution[line+1:line+2, :]=[(sum(sum(item))+1)%2 for item in TxT]
然后计算最后一行的灯泡状态得到是否是解：
- TxT = [take(tmpArray, [x, x+1, x+2], axis=1) for x in range(n)]
- [putmask(item, [1,0,1,0,0,0], [0]) for item in TxT]
- if sum([(sum(sum(item)))%2 for item in TxT])==n:
- print solution
- print "Total steps:%d" % sum(sum(solution))
把重复代码提取出来成一个函数：
- def lightstats(switchstats, n):
- TxT = [take(switchstats, [x, x+1, x+2], axis=1) for x in range(n)]
- [putmask(item, [1,0,1,0,0,0], [0]) for item in TxT]#去掉不相关的格子
- return [(sum(sum(item)))%2 for item in TxT]
好了，配件齐全，开始组装：
- #!/usr/bin/python
- # -*- coding: utf8 -*-
- #Filename:second2.py
- from numarray import *
- import numarray.strings as nastr
- from bin import bstr
- def lightstats(switchstats, n):
- TxT = [take(switchstats, [x, x+1, x+2], axis=1) for x in range(n)]
- [putmask(item, [1,0,1,0,0,0], [0]) for item in TxT]#去掉不相关的格子
- return [(sum(sum(item)))%2 for item in TxT]
- def light(n):
- PosSol = [nastr.array(bstr(x).zfill(n), itemsize=1).eval() for x in xrange(2**n)]
- solution=zeros((n, n))#解
- tmpArray=zeros((2, n+2))#用来存放每一行的开关状态
- for i in PosSol:
- solution[0:1]=i.copy()
- tmpArray[0, :]=0
- tmpArray[1,1:-1]=i.copy()
- for line in range(n-1):#取n-1是因为第一行是生成的，不需要计算
- solution[line+1:line+2, :]=ones((1, n))-lightstats(tmpArray, n)
- tmpArray[:,1:-1]=solution[line:line+2, :]
- if sum(lightstats(tmpArray, n))==n:
- print solution
- print "Total steps:%d" % sum(sum(solution))
- tests = [2,3,4,5,6]
- for xx in tests:
- print "solution for %d*%d" % (xx,xx)
- light(xx)
现在就算算10×10也不会很久啦，哈哈~~不过代码还有可以商量的地方，明天继续。
- 0 ratings
Leave a comment