題目：

　　有十個開關等間距排成一線，每個開關對應其上方的一盞燈(十盞燈也排成一線)。每按動一下開關，可以使對應的燈改變狀態(原來亮著的將熄滅，原來熄滅的將被點亮)。

　　但是，由于開關之間的距離很小，每次按動開關時，相鄰的一個開關也將被按動。例如：按動第5個開關，則實際上第4、5、6個開關都被按動。而按動靠邊的第1個開關時，第1、2個開關都被按動。并且，無法只按動靠邊的一個開關。

　　現在給出十盞燈的初始的狀態和目標狀態，要求計算：從初始狀態改變到目標狀態所需要的少操作次數。

　　函數接口：

　　int MinChange(const int Start[],const int End[]);

　　其中：Start表示了初始狀態，End表示了目標狀態。表示狀態的數組(Start和End)中，若某元素為0表示對應的燈亮著，否則表示對應的燈沒有亮。調用函數時保證Start和End數組長度均為10，并保證有解。

　　看了很多人的解法都是用循環遍歷來判斷是否達到要求，但是如果和線形代數結合的話，就有一種很快速的解法。

　　約定：以下所用的‘+’號都是‘異或’的運算。

　　先簡化一下，假設有四個燈，初始狀態s0～s3，目標狀態是e0～e3，轉換一次狀態就是和1進行異或運算一次，所以狀態轉移矩陣為：

　　(s0,s1,s2,s3)+k0*(1,1,0,0)+k1*(1,1,1,0)+k2*(0,1,1,1)+k3*(0,0,1,1)=(e0,e1,e2,e3);

　　其中k(n)表示第n個開關所翻動的次數。并且，注意異或運算中a+b+b=a，所以，某個開關翻動偶數次的效果相當于沒有翻動，翻動奇數次的效果相當于翻動一次;又由于異或運算滿足交換律，所以翻動的順序沒有影響。綜上每個開關翻動的次數只有1次或0次就足夠了。

　　設m(n)=s(n)+e(n)，注意異或運算中的'-'也就是'+'，所以解線性方程組：

　　k0+k1 =m1;

　　k0+k1+k2 =m2;

　　k1+k2+k3=m3;

　　k2+k3=m4;

　　假設解存在，就可以算出通解(k0,k1,k2,k3)，再統計出通解中1的個數，就是所需要翻動的次數了。并且還可以知道哪些開關需要撥動，比如算出解是(1,0,1,0)就是第0和2個開關需要撥動一次。

　　因此針對本題目的10個燈泡，本人已算出這10元線性方程組的通解：

　　k0=m0+m2+m3+m5+m6+m8+m9;

　　k1=m2+m3+m5+m6+m8+m9;

　　k2=m0+m1;

　　k3=m3+m0+m1+m5+m6+m8+m9;

　　k4=m5+m6+m8+m9;

　　k5=m4+m3+m0+m1;

　　k6=m6+m4+m3+m0+m1+m8+m9;

　　k7=m8+m9;

　　k8=m7+m6+m4+m3+m0+m1;

　　k9=m9+m7+m6+m4+m3+m0+m1;

　　和上面一樣，m(n)為開始狀態與目標狀態的每位異或。至于是否存在解，本人已將次系數矩陣化簡為對角矩陣，可以看到系數矩陣的秩(Rank)與未知數的個數相等，所以無論是任何的輸入和輸出變換都能找到解。

　　本人程序如下：

　　int MinChange(const int Start[],const int End[]){

　　int m[10];

　　int k[10];

　　int res=0;

　　int i,j,n;

　　for(i=0;i<10;i++){

　　m[i]=Start[i]^End[i]; /* m[]=Start[] XOR End[] */

　　}

　　/* calculate roots */

　　k[0]=m[0]^m[2]^m[3]^m[5]^m[6]^m[8]^m[9];

　　k[1]=m[2]^m[3]^m[5]^m[6]^m[8]^m[9];

　　k[2]=m[0]^m[1];

　　k[3]=m[3]^m[0]^m[1]^m[5]^m[6]^m[8]^m[9];

　　k[4]=m[5]^m[6]^m[8]^m[9];

　　k[5]=m[4]^m[3]^m[0]^m[1];

　　k[6]=m[6]^m[4]^m[3]^m[0]^m[1]^m[8]^m[9];

　　k[7]=m[8]^m[9];

　　k[8]=m[7]^m[6]^m[4]^m[3]^m[0]^m[1];

　　k[9]=m[9]^m[7]^m[6]^m[4]^m[3]^m[0]^m[1];

　　/* count for switch times */

　　for(j=0;j<10;j++){

　　if(k[j]) res++;

　　}

　　/* display k(n); */

　　for(n=0;n<10;n++) printf("%d,",k[n]);

　　return res;

　　}

　　測試主程序：

　　main(){

　　int A[10]={1,1,1,0,0,1,0,1,1,0};

　　int B[10]={0,0,1,1,0,0,1,1,1,1};

　　int C;

　　C=MinChange(A,B);

　　printf("**%d**",C);

　　}

　　顯示結果為：

　　1，0，0，0，1，1，1，1，0，1，**6**

　　就是如果要把狀態A轉為狀態B，需要把第0，4，5，6，7，9號開關翻動一次，共6次。

　　測試驗證結果正確：)

　　當然，此做法也有一個缺點，就是當燈的個數改變時，就要重新設定線形方程組的特解形式。