|
題目：
有十個開關等間距排成一線，每個開關對應其上方的一盞燈（十盞燈也排成一線）。每按動一下開關，可以使對應的燈改變狀態(tài)（原來亮著的將熄滅，原來熄滅的將被點亮）。
但是，由于開關之間的距離很小，每次按動開關時，相鄰的一個開關也將被按動。例如：按動第5個開關，則實際上第4、5、6個開關都被按動。而按動靠邊的第1個開關時，第1、2個開關都被按動。并且，無法只按動最靠邊的一個開關。
現(xiàn)在給出十盞燈的初始的狀態(tài)和目標狀態(tài)，要求計算：從初始狀態(tài)改變到目標狀態(tài)所需要的最少操作次數(shù)。
函數(shù)接口：
int MinChange(const int Start[],const int End[]);
其中：Start表示了初始狀態(tài)，End表示了目標狀態(tài)。表示狀態(tài)的數(shù)組（Start和End）中，若某元素為0表示對應的燈亮著，否則表示對應的燈沒有亮。調用函數(shù)時保證Start和End數(shù)組長度均為10，并保證有解。
看了很多人的解法都是用循環(huán)遍歷來判斷是否達到最后要求，但是如果和線形代數(shù)結合的話，就有一種很快速的解法。
約定：以下所用的‘＋’號都是‘異或’的運算。
先簡化一下，假設有四個燈，初始狀態(tài)s0～s3，目標狀態(tài)是e0～e3，轉換一次狀態(tài)就是和1進行異或運算一次，所以狀態(tài)轉移矩陣為：
(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個開關所翻動的次數(shù)。并且，注意異或運算中a＋b＋b＝a，所以，某個開關翻動偶數(shù)次的效果相當于沒有翻動，翻動奇數(shù)次的效果相當于翻動一次；又由于異或運算滿足交換律，所以翻動的順序沒有影響。綜上每個開關翻動的次數(shù)只有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)，再統(tǒng)計出通解中1的個數(shù)，就是所需要翻動的次數(shù)了。并且還可以知道哪些開關需要撥動，比如算出解是(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)為開始狀態(tài)與目標狀態(tài)的每位異或。至于是否存在解，本人已將次系數(shù)矩陣化簡為對角矩陣，可以看到系數(shù)矩陣的秩（Rank）與未知數(shù)的個數(shù)相等，所以無論是任何的輸入和輸出變換都能找到唯一解。
本人程序如下：
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**
就是如果要把狀態(tài)A轉為狀態(tài)B，需要把第0，4，5，6，7，9號開關翻動一次，共6次。
測試驗證結果正確：）
當然，此做法也有一個缺點，就是當燈的個數(shù)改變時，就要重新設定線形方程組的特解形式。
|
