您当前的位置:首页 > 网络编程 > Net编程 > 正文

数学与程序 一道游戏题目的快速解法

【字体大小: 2009-04-14 16:08 来源: 作者: 

  题目:

  有十个开关等间距排成一线,每个开关对应其上方的一盏灯(十盏灯也排成一线)。每按动一下开关,可以使对应的灯改变状态(原来亮着的将熄灭,原来熄灭的将被点亮)。

  但是,由于开关之间的距离很小,每次按动开关时,相邻的一个开关也将被按动。例如:按动第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;

  和上面一样,m(n)为开始状态与目标状态的每位异或。至于是否存在解,本人已将次系数矩阵化简为对角矩阵,可以看到系数矩阵的秩(Rank)与未知数的个数相等,所以无论是任何的输入和输出变换都能找到唯一解。

  本人程序如下:

  1. int MinChange(const int Start[],const int End[]){  
  2.  
  3.   int m[10];  
  4.  
  5.   int k[10];  
  6.  
  7.   int res=0;  
  8.  
  9.   int i,j,n;  
  10.  
  11.   for(i=0;i<10;i++){  
  12.  
  13.   m[i]=Start[i]^End[i]; /* m[]=Start[] XOR End[] */ 
  14.  
  15.   }  
  16.  
  17.   /* calculate roots */ 
  18.  
  19.   k[0]=m[0]^m[2]^m[3]^m[5]^m[6]^m[8]^m[9];  
  20.  
  21.   k[1]=m[2]^m[3]^m[5]^m[6]^m[8]^m[9];  
  22.  
  23.   k[2]=m[0]^m[1];  
  24.  
  25.   k[3]=m[3]^m[0]^m[1]^m[5]^m[6]^m[8]^m[9];  
  26.  
  27.   k[4]=m[5]^m[6]^m[8]^m[9];  
  28.  
  29.   k[5]=m[4]^m[3]^m[0]^m[1];  
  30.  
  31.   k[6]=m[6]^m[4]^m[3]^m[0]^m[1]^m[8]^m[9];  
  32.  
  33.   k[7]=m[8]^m[9];  
  34.  
  35.   k[8]=m[7]^m[6]^m[4]^m[3]^m[0]^m[1];  
  36.  
  37.   k[9]=m[9]^m[7]^m[6]^m[4]^m[3]^m[0]^m[1];  
  38.  
  39.   /* count for switch times */ 
  40.  
  41.   for(j=0;j<10;j++){  
  42.  
  43.   if(k[j]) res++;  
  44.  
  45.   }  
  46.  
  47.   /* display k(n); */ 
  48.  
  49.   for(n=0;n<10;n++) printf("%d,",k[n]);  
  50.  
  51.   return res;  
  52.  
  53.   } 

  测试主程序:

  1. main(){  
  2.  
  3.   int A[10]={1,1,1,0,0,1,0,1,1,0};  
  4.  
  5.   int B[10]={0,0,1,1,0,0,1,1,1,1};  
  6.  
  7.   int C;  
  8.  
  9.   C=MinChange(A,B);  
  10.  
  11.   printf("**%d**",C);  
  12.  
  13.   } 

  显示结果为:

  1,0,0,0,1,1,1,1,0,1,**6**

  就是如果要把状态A转为状态B,需要把第0,4,5,6,7,9号开关翻动一次,共6次。

  测试验证结果正确:)

  当然,此做法也有一个缺点,就是当灯的个数改变时,就要重新设定线形方程组的特解形式。

  文章来源[世纪预言站长网Http://www.4jyy.cn] 转载请注明出处。

    顶一下
    (0)
    0%
    踩一下
    (0)
    0%
    【责任编辑:绝口不提】 标签:
    最新评论 查看所有评论
    发表评论 查看所有评论
    请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
    评价:
    表情:
    用户名:密码:验证码: