分享
 
 
 

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

王朝other·作者佚名  2008-06-01
窄屏简体版  字體: |||超大  

题目:

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

但是,由于开关之间的距离很小,每次按动开关时,相邻的一个开关也将被按动。例如:按动第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)与未知数的个数相等,所以无论是任何的输入和输出变换都能找到唯一解。

本人程序如下:

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次。

测试验证结果正确:)

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

更多内容请看网络游戏攻略 游戏开发专题,或

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有