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