题目：
有十个开关等间距排成一线，每个开关对应其上方的一盏灯（十盏灯也排成一线）。每按动一下开关，可以使对应的灯改变状态（原来亮着的将熄灭，原来熄灭的将被点亮）。
但是，由于开关之间的距离很小，每次按动开关时，相邻的一个开关也将被按动。例如：按动第5个开关，则实际上第4、5、6个开关都被按动。而按动靠边的第1个开关时，第1、2个开关都被按动。并且，无法只按动最靠边的一个开关。
现在给出十盏灯的初始的状态和目标状态，要求计算：从初始状态改变到目标状态所需要的最少操作次数。
函数接口：
int MinChange(const int Start[],const int End[]);
其中：Start表示了初始状态，End表示了目标状态。表示状态的数组（Start和End）中，若某元素为0表示对应的灯亮着，否则表示对应的灯没有亮。调用函数时保证Start和End数组长度均为10，并保证有解。
【解答1】http://www.programfan.com/club/showbbs.asp?id=140389
#include<cstdio>
int fnd(int *p,int &n)
{
do{
if(p[n]) return 1;
}while(++n < 10);
return 0;
}
void presskey(int *q,int &t)
{
t = t%10;
if(t == 0)
{
q[0] = !q[0];
q[1] = !q[1];
return;
}
if(t == 9)
{
q[8] = !q[8];
q[9] = !q[9];
return;
}
q[t-1] = !q[t-1];
q[t] = !q[t];
q[t+1] = !q[t+1];
return;
}
int MinChange(const int Start[],const int End[])
{
int flag[10] = {0};
int c[10] = {0};
int count = 0;
int i = 0;
for(;i < 10;i++)
if(!Start[i] != !End[i])
flag[i] = 1;
i = 0;
while(fnd(flag,i))
{
presskey(flag,++i);
c[i]++;
}
for(i = 0;i < 10;i++)
count += c[i]%2;
return count;
}
int main()
{
int start[10] = {1,1,0,1,0,1,0,0,1,1};
int end[10] = {0,1,1,1,1,0,0,1,0,0};
int i = MinChange(start,end);
printf("%d\n",i);
return 0;
}
【解答2】
#include <cstdio>
#include <cassert>
#define POW(c) (1<<(c))
#define MASK(c) (((unsigned long)-1) / (POW(POW(c)) + 1))
#define ROUND(n, c) (((n) & MASK(c)) + ((n) >> POW(c) & MASK(c)))
int bit_count(unsigned int n)
{
n = ROUND(n, 0);
n = ROUND(n, 1);
n = ROUND(n, 2);
n = ROUND(n, 3);
n = ROUND(n, 4);
return n;
}
int MinChange(const int Start[],const int End[])
{
int i, j, count;
unsigned short bits = 0;
unsigned short s[10] =
{
0x003, 0x007, 0x00e, 0x01c, 0x038,
0x070, 0x0e0, 0x1c0, 0x380, 0x300,
};
for (i = 0; i < 10; i++)
bits = (bits << 1) | (!Start[i] != !End[i]);
#ifdef _DEBUG
int round = 0;
#endif
for (count = j = 0; bits; j = (j+1)%10)
{
#ifdef _DEBUG
if (j == 0)
round ++; // 这里统计round的次数
#endif
if (bits & (1<<j))
bits ^= s[(j+1)%10], count ^= 1<<j;
}
assert(round < 3); // 可以肯定上面的循环不超过20次。这样计算量也就逼近楼主的方法了。不过由于有循环，速度应该还是比不上楼主的。
return bit_count(count);
}
/*
void test(int i)
{
int a[10];
int b[10] = {0};
for (int j = 0; j < 10;j++)
a[j] = i & (1<<j) ? 1:0;
if (MinChange2(a,b) != MinChange(a,b))
{
for (int j = 0; j < 10;j++)
printf("%d", a[j]);
printf("\n");
}
}
int main()
{
int i;
for (i = 0; i < 1<<10; i++)
{
test(i);
}
return 0;
}
*/
【解答3】
约定：以下所用的‘＋’号都是‘异或’的运算。
先简化一下，假设有四个灯，初始状态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次。
测试验证结果正确：）
评论