熄灯问题的线性方程组解法

熄灯问题 ：

在郭炜老师的《程序设计及算法（二）》的1.4及1.5节以及刘家瑛老师的北京大学 算法基础第四节中作为枚举法的例子进行讲解。

枚举法

一般来看，每个开关有两种状态，只需要枚举\(2^{30}=1，073，741，824\)次，过于繁琐，会超时。

于是，则考虑当第一行的某种开关样式确定之后，如果想让第一行的灯全部熄灭，则只能对第二行对应第一行亮灯位置的开关进行操作，即第二行操作方式确定。同理，如果想让第二行全部熄灭，且在前两行开关不再操作的前提下，只能操作第三行对应第二行亮灯位置的开关，以此类推，当操作完最后一行的开关后，此时无法再操作任何一个开关，如果此时最后一行的灯是全部熄灭的状态，则完成全部熄灭的操作。

所以，看似没有关联的各开关状态，转化成了由第一行的开关状态觉得全体开关状态的问题，问题的状态数变成了\(2^6=64\)，执行的次数为\(64*5*6\)，同理，如果按列分析的情况，问题的状态数为\(2^5=32\)，执行的次数为\(32*6*5\)。

接下来就是编程阶段，第一次看MOOC时，郭炜老师巧妙的用一个二进制数来表示每行的开关状态，并将其存储在一个char数组中，通过对第一行的二进制数+1改变初始的排列状态，然后通过来对每行的开关操作的结果进行表示。

当时

我看不懂，但我大受震撼。

琢磨了好几遍才理解郭老师的操作，太妙了。

消元法

第一次接触这个问题时，没有过多的思考，就进入到“枚举”的思想，并且从局部考虑问题，减少整体的运算的方法。但是在问题解决的过程中，我总有一种感觉，对于“每按下一个开关，其自身及上下左右的灯都会相应的产生作用”似乎是在传递着每个开关之间的关系，只是，这种关系看起来不是很容易描述。

我发现，可以将某个所研究的位置处的开状态或者关状态考虑成，其他各个位置的操作对其共同作用的结果，即，某些位置1次操作会对当前所研究位置的开|关状态产生依次影响，而某些位置的操作，对当前所研究位置的开|关状态是没有影响的。

将每行每列开关依次排开，将每个位置的操作数作为未知变量\(x_n\)，将上述的影响关系作为每个位置数的系数，来反映此位置的操作对当前所研究位置结果的影响，每一项加起来反映的是最终状态，列等号，右边为0或者1，表示开或者关的状态。

在这个问题，奇数次的操作等于操作1次，偶数次的操作等于0次，操作对应的影响也是只能通过0或者1来反映，所以我们约定，对每一项未知数的系数以及最终的状态结果，均只用0或1表示。

对每个位置都做这样的处理，则的到了一组线性方程组，形如\(Ax=B\)。

对于线性方程组的解法有直接法，如高斯消元法、LU分解等；也有迭代法，如J迭代、G-S迭代、共轭迭代等。

对于这个问题，由于增广矩阵需要进行根据奇数偶数转化为0或1的操作，看起来不是很适合迭代法。我选择了高斯消元法的列主元素消去法。主要步骤为消去和回代，依次对列操作，选取当前列的绝对值最大元素作为主元素，交换主元素所在行到当前列编号行，然后有当前列对应的行对下面各行进行消元，形成主元素以下各值均为0，依次操作，将系数矩阵的主对角线的下方元素全部消为0，然后从第\(n\)个元素往上依次回代求解各变量。

与一般的消元法不同，在每次进行增广矩阵的行操作后，都要将其转化为只有0和1的状态，因为在这个问题中，只有0和1是有效的数字，回代的过程亦然。

Talk is cheap, show me your code.

代码如下：

#include
#include
using namespace std;
//----------将奇数转化为1，将偶数转化为0------------
int oneorzero(int i){
	if (i%2!=0) {
		i=1;
	}else{
		i=0;
	}
	return i;
} 
//------------------------------------------------
int main()
{
//----------声明变量及初始化-----------------------
	int R=5,C=6;
	int A[R*C][R*C],b[R*C],x[R*C];
	
	for(int i=0;i>b[i]; 
//----------构建系数矩阵---------------------------
	for(int m=1;m<=R;m++)
		for(int n=1;n<=C;n++)
			for(int i=1;i<=R;i++)
				for(int j=1;j<=C;j++)
					if ( i == m-1 && j==n){
						A[(m-1)*C+n-1][(i-1)*C+j-1]=1;
					}else if((i== m) && (j==n-1||j==n||j==n+1)){
							A[(m-1)*C+n-1][(i-1)*C+j-1]=1;
					}else if((i== m+1)&&(j==n)){
							A[(m-1)*C+n-1][(i-1)*C+j-1]=1;
					}
//----------高斯消元法-----------------------------
	int temp=0;
	int index=0;
	for(int i=0;i0 ){
				temp=A[j][i];
				index=j;
			}
		}
//----------交换列主元素行到当前列第一行------------
		if(index!=i){
			for(int j=0;j=0;i--){
		int sum=0;
		for (int j=R*C-1;j>i;j--){
			sum+=x[j]*A[i][j];
		}
		x[i]=(b[i]-sum)/A[i][i];
//----------将结果进行奇偶数转化-------------------
		x[i]=oneorzero(x[i]);
	}
//----------输出结果------------------------------
	for(int i=0;i

0 1 1 0 1 0
1 0 0 1 1 1
0 0 1 0 0 1
1 0 0 1 0 1
0 1 1 1 0 0

1 0 1 0 0 1
1 1 0 1 0 1
0 0 1 0 1 1
1 0 0 1 0 0
0 1 0 0 0 0