題目：
有十個開關(guān)等間距排成一線，每個開關(guān)對應(yīng)其上方的一盞燈(十盞燈也排成一線)。每按動一下開關(guān)，可以使對應(yīng)的燈改變狀態(tài)(原來亮著的將熄滅，原來熄滅的將被點亮)。
但是，由于開關(guān)之間的距離很小，每次按動開關(guān)時，相鄰的一個開關(guān)也將被按動。例如：按動第5個開關(guān)，則實際上第4、5、6個開關(guān)都被按動。而按動靠邊的第1個開關(guān)時，第1、2個開關(guān)都被按動。并且，無法只按動最靠邊的一個開關(guān)。
現(xiàn)在給出十盞燈的初始的狀態(tài)和目標(biāo)狀態(tài)，要求計算：從初始狀態(tài)改變到目標(biāo)狀態(tài)所需要的最少操作次數(shù)。
函數(shù)接口：
int MinChange(const int Start[],const int End[]);
其中：Start表示了初始狀態(tài)，End表示了目標(biāo)狀態(tài)。表示狀態(tài)的數(shù)組(Start和End)中，若某元素為0表示對應(yīng)的燈亮著，否則表示對應(yīng)的燈沒有亮。調(diào)用函數(shù)時保證Start和End數(shù)組長度均為10，并保證有解。
看了很多人的解法都是用循環(huán)遍歷來判斷是否達(dá)到最后要求，但是如果和線形代數(shù)結(jié)合的話，就有一種很快速的解法。
約定：以下所用的‘+’號都是‘異或’的運(yùn)算。
先簡化一下，假設(shè)有四個燈，初始狀態(tài)s0～s3，目標(biāo)狀態(tài)是e0～e3，轉(zhuǎn)換一次狀態(tài)就是和1進(jìn)行異或運(yùn)算一次，所以狀態(tài)轉(zhuǎn)移矩陣為：
(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個開關(guān)所翻動的次數(shù)。并且，注意異或運(yùn)算中a+b+b=a，所以，某個開關(guān)翻動偶數(shù)次的效果相當(dāng)于沒有翻動，翻動奇數(shù)次的效果相當(dāng)于翻動一次;又由于異或運(yùn)算滿足交換律，所以翻動的順序沒有影響。綜上每個開關(guān)翻動的次數(shù)只有1次或0次就足夠了。
設(shè)m(n)=s(n)+e(n)，注意異或運(yùn)算中的'-'也就是'+'，所以解線性方程組：
k0+k1 =m1;
k0+k1+k2 =m2;
k1+k2+k3=m3;
k2+k3=m4;
假設(shè)解存在，就可以算出通解(k0,k1,k2,k3)，再統(tǒng)計出通解中1的個數(shù)，就是所需要翻動的次數(shù)了。并且還可以知道哪些開關(guān)需要撥動，比如算出解是(1,0,1,0)就是第0和2個開關(guān)需要撥動一次。
因此針對本題目的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;
有十個開關(guān)等間距排成一線，每個開關(guān)對應(yīng)其上方的一盞燈(十盞燈也排成一線)。每按動一下開關(guān)，可以使對應(yīng)的燈改變狀態(tài)(原來亮著的將熄滅，原來熄滅的將被點亮)。
但是，由于開關(guān)之間的距離很小，每次按動開關(guān)時，相鄰的一個開關(guān)也將被按動。例如：按動第5個開關(guān)，則實際上第4、5、6個開關(guān)都被按動。而按動靠邊的第1個開關(guān)時，第1、2個開關(guān)都被按動。并且，無法只按動最靠邊的一個開關(guān)。
現(xiàn)在給出十盞燈的初始的狀態(tài)和目標(biāo)狀態(tài)，要求計算：從初始狀態(tài)改變到目標(biāo)狀態(tài)所需要的最少操作次數(shù)。
函數(shù)接口：
int MinChange(const int Start[],const int End[]);
其中：Start表示了初始狀態(tài)，End表示了目標(biāo)狀態(tài)。表示狀態(tài)的數(shù)組(Start和End)中，若某元素為0表示對應(yīng)的燈亮著，否則表示對應(yīng)的燈沒有亮。調(diào)用函數(shù)時保證Start和End數(shù)組長度均為10，并保證有解。
看了很多人的解法都是用循環(huán)遍歷來判斷是否達(dá)到最后要求，但是如果和線形代數(shù)結(jié)合的話，就有一種很快速的解法。
約定：以下所用的‘+’號都是‘異或’的運(yùn)算。
先簡化一下，假設(shè)有四個燈，初始狀態(tài)s0～s3，目標(biāo)狀態(tài)是e0～e3，轉(zhuǎn)換一次狀態(tài)就是和1進(jìn)行異或運(yùn)算一次，所以狀態(tài)轉(zhuǎn)移矩陣為：
(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個開關(guān)所翻動的次數(shù)。并且，注意異或運(yùn)算中a+b+b=a，所以，某個開關(guān)翻動偶數(shù)次的效果相當(dāng)于沒有翻動，翻動奇數(shù)次的效果相當(dāng)于翻動一次;又由于異或運(yùn)算滿足交換律，所以翻動的順序沒有影響。綜上每個開關(guān)翻動的次數(shù)只有1次或0次就足夠了。
設(shè)m(n)=s(n)+e(n)，注意異或運(yùn)算中的'-'也就是'+'，所以解線性方程組：
k0+k1 =m1;
k0+k1+k2 =m2;
k1+k2+k3=m3;
k2+k3=m4;
假設(shè)解存在，就可以算出通解(k0,k1,k2,k3)，再統(tǒng)計出通解中1的個數(shù)，就是所需要翻動的次數(shù)了。并且還可以知道哪些開關(guān)需要撥動，比如算出解是(1,0,1,0)就是第0和2個開關(guān)需要撥動一次。
因此針對本題目的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;