《开灯游戏.docVIP

开灯游戏: 问题重述：现有n行n列共有n^2个灯泡，每个灯泡只有两个状态：开和关。如果你点击其中一个灯泡，则这个灯泡和它上下左右的四个灯泡都会发生变化，即开着的就会关闭，关闭的就会打开，对于边界的灯泡我们只考虑存在的灯泡。对于以上定义的游戏规则, 试建立模型求解以下问题: (a) 假定n=5，所有灯泡的初始状态为开，问如何点击鼠标将灯泡全部关闭, 且点击鼠标的次数尽可能少。 ()对于任意的n，假定棋盘的初始状态为一个残局: 部分方格为开, 部分方格为关闭, , 按照以上规则操作，该残局最终变为关闭。 (a)情况实际上也就是全为开的5阶残局），这样，问题就变为： 对于任意的n，假定的初始状态为一个残局: 部分方格为开, 部分方格为关闭, 对于这个问题，我们解答如下： （1）首先要确定的是，一个灯泡在一定的点击方案之下，最终变为关闭的充分必要条件是什么。我们首先研究一开始为全开的情况。 在一开始为全开时，我们不妨假设未被点击的灯泡为0，被点击的灯泡为1，那么原题中所谓的灯泡阵列就被抽象为一个n阶方阵。事实上，在这里我们可以推导出如下引理： 当且仅当，方阵之中的某个数字及其上下左右（如果存在）数字之和为奇数时，该数字所代表的灯泡就是关闭的。 这个引理的推导是简单的：因为一扇灯泡的状态只受其上下左右（如果存在）灯泡点击的影响，且一扇灯泡重复点击实际上是没有意义的，那么显然这五扇灯泡的点击对于中间一扇来讲是等价的。这样，对于这些灯泡奇数次的点击就一定能使中间的灯泡关闭。引理证毕。 但是，在灯泡排列为残局时，这个引理的成立就受到了限制。一方面，残局之中关闭的灯泡我们并没有给它赋值；另一方面，假如给在残局之中关闭的灯泡赋值为1，那么引理的成立就收到了挑战，这是因为，赋值为1无形之中就将在残局之中关闭的灯泡与被点击的灯泡等同了，但事实上，在残局之中关闭的灯泡并不对中心的灯泡造成影响（中间的灯泡在残局之中关闭的情况除外），于是就会导致误判。 为解决这个问题，我们只能将在残局之中关闭的灯泡与被点击的灯泡区别起来，我们组的区别方案如下： 1=需要被点击的、一开始开启的灯泡； 0=不需要点击的、一开始开启灯泡； 12=需要被点击的、一开始关闭的灯泡； 11=不需要点击的、一开始关闭的灯泡。 利用这个方案，当我们甄别出一个灯泡在开始时就关闭时，我们就可以将其减去11以判定该灯泡是否遭到点击（若是需要判定的灯泡在残局之中关闭的话，在求和时不用对中间的灯泡如此做，事实上，此时该灯泡本身值的奇偶就已经对其自身造成了影响）。这样，该引理更改为： 当且仅当，方阵之中的某个数字及其上下左右（如果存在）数字之和为奇数时，该数字所代表的灯泡就是关闭的。假如，上下左右（如果存在）的数字有超过9的，那么将其减去11再求和。 有了这样一个引理之后，我们就可以利用解方程的方式，对于每一扇灯泡的关闭分别列出方程求解问题。但是这样的方法无疑是有着巨大缺点的：首先，该方法的计算量过于庞大，已达到量级；另外，当n值变化时，所对应的方程就必须重新列出。这两个缺点无疑大幅降低了该种方法的实用性，所以，我们组采用 Matlab 编程的方式解决此题。 （一）第一个程序： 我们组进行Matlab 编程的中心思想如下： 1、首先是赋值模块。由于n阶情况中每一个灯泡都有两种状态，总共就存在种方案。我们组利用算法，将1~的整数，与每种方案相对应，这样就遍历了所有可能的方案。 2、之后是检测模块。检测模块的主要原理就是前述的引理（补充后）。在本模块中，我们利用软件对每一种赋值模块产生的方案进行验证，若每扇灯泡都满足前述引理，那么这种方案就是我们所求的。 3、最后是优化模块。在本模块之中，我们计算出每种可行方案所需要的点击次数，并利用求最大值的方法进行逐个比较，找到最小值后，最小值所对应的方案即为我们的最终结果（如有多个，那么只取一种，因为事实上，所谓的多种最优方案都是经过一种方案旋转或对称得到的。）。 以下为我们按照这种思路编写的代码： j=4; min=j^2*11; for n=1:2^(j^2) x=n;B=[11 11 11 11;11 11 11 0;11 0 0 0;0 0 0 0]; for m=j:-1:1 for o=j:-1:1 if mod(x,2)==1 x=(x-1)/2; B(m,o)=B(m,o)+1; else x=x/2; B(m,o)=B(m,o)+0; end en