题目:
有十个开关等间距排成一线,每个开关对应其上方的一盏灯(十盏灯也排成一线)。每按动一下开关,可以使对应的灯改变状态(原来亮着的将熄灭,原来熄灭的将被点亮)。
但是,由于开关之间的距离很小,每次按动开关时,相邻的一个开关也将被按动。例如:按动第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.