 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
点灯问题的解法
下载积分：400
内容提示：点灯问题的解法
文档格式：PDF|
浏览次数：189|
上传日期： 13:30:50|
文档星级：
该用户还上传了这些文档
点灯问题的解法
官方公共微信回复：数学吧的吧友们有办法做这个游戏难题吗~速度来解决~_数学吧_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：413,236贴子：
回复：数学吧的吧友们有办法做这个游戏难题吗~速度来解决~收藏
好像洛克王国也有……（喂！）
const l=5;m=l*l;step=100;var a,b:array[0..l+1,0..l+1]空空i,j,k:空空n,r,s,p,q:int64;空空c:array[0..m]ofint64;空空f: beginwriteln(f,'##########');for i:=1 to l do空begin空for j:=1 to ldo空空if a[i,j]=0then write(f,'·') elsewrite(f,'█');空writeln(f);空writeln(f,'##########');for i:=1 to l do空begin空for j:=1 to ldo空空if b[i,j]=0then write(f,'·') elsewrite(f,'█');空writeln(f);空 beginassign(f,'c:\o.txt');rewrite(f);p:=1;for i:=1 to l do空for j:=1 to ldo空空p:=p shl 1;q:=writeln('start');repeatn:=n+1;r:=n;for i:=1 to l do空for j:=1 to ldo空空begin空空a[i,j]:=rand 1;空空r:=r shr 1;空空s:=0;for i:=1 to l do空for j:=1 to ldo空空begin空空b[i,j]:=a[i,j]xor a[i-1,j] xor a[i+1,j] xor a[i,j-1] xor a[i,j+1];{空空if j=3 thenb[i,j]:=b[i,j] xor a[i,j-1];空空空空空空空空空空空空空空}空空s:=s+b[i,j]空空c[s]:=c[s]+1;if s=2if (n mod q=0) then write(n div q:10);until n&=p;writeln();for i:=0 to m do空writeln(f,i:5,c[i]:15);close(f);readln();end.//我把源码贴上来了，你自己到Free Pascal编译器里修改编译。
ui培训哪个好，0基础+双证+实战「就业无忧」
const w=6;h=w;step=100;var a:array[1..h,1..w]
b:array[0..h+1,0..w+1]
n,r,s,p,q:int64;
c:array[0..w]of int64;
f: beginwriteln(f,'##########');for i:=1 to h do begin
forj:=1 to w do
if a[i,j]=0 then write(f,'·') else write(f,'█'); writeln(f);writeln(f,'##########');for i:=1 to h do begin
forj:=1 to w do
if b[i,j]=0 then write(f,'·') else write(f,'█'); writeln(f); beginassign(f,'c:\o.txt');rewrite(f);p:=1;for j:=1 to w do p:=p shl 1;q:=writeln('start');repeatn:=n+1;r:=n;for j:=1 to w do begin a[1,j]:=r and 1; r:=r shr 1;s:=0;for i:=1 to h do
forj:=1 to w do
b[i,j]:=0;i:=1;for j:=1 to h do
ifa[1,j]=1 then
b[i,j-1]:=b[i,j-1] xor 1;
b[i,j]:=b[i,j] xor 1;
b[i,j+1]:=b[i,j+1] xor 1;
b[i+1,j]:=b[i+1,j] xor 1;for i:=2 to h do
forj:=1 to w do
if b[i-1,j]=0 then
b[i-1,j]:=b[i-1,j] xor 1;
b[i,j-1]:=b[i,j-1] xor 1;
b[i,j]:=b[i,j] xor 1;
b[i,j+1]:=b[i,j+1] xor 1;
b[i+1,j]:=b[i+1,j] xor 1;
a[i,j]:=1;
a[i,j]:=0;i:=h;for j:=1 to w do s:=s+b[i,j];c[s]:=c[s]+1;if s=
{if (n mod q=0) then write(n div q:10);}until n&=p;writeln();for i:=0 to w do writeln(f,(h-1)*w+i:5,c[i]:15);close(f);writeln('end');readln();end.//改进了算法，之前用穷举算5*5需要2^(5*5)次即次循环，6*6的无力计算。现在只需2^5次即32次循环即可算出答案，可任意计算30*30以内的点灯游戏，缺点是不能一次输出给定初始灯泡数的解，只能给出特定初始情况（已知哪些灯泡被点亮）的解。//可以证明n*n的点灯游戏在初始全灭的情况下总有一种解法可以全部点亮。
var a:array[1..100,1..100]
b:array[0..101,0..101]
n,r,s,p:int64;
c:array[0..101]of int64;
beginwriteln(f,'#####################');for i:=1 to h do begin
forj:=1 to w do
if a[i,j]=0 then write(f,'　') else write(f,'█'); writeln(f);
{writeln(f,'#####################');for i:=1 to h do begin
forj:=1 to w do
if b[i,j]=0 then write(f,'　') else write(f,'█'); writeln(f);
} beginassign(f,'c:\o.txt');rewrite(f);for k:=1 to 20 do begin w:=k; h:=k;p:=1;for j:=1 to w do p:=p shl 1;writeln('start: ',k);n:=0;repeatn:=n+1;r:=n;for j:=1 to w do begin a[1,j]:=r and 1; r:=r shr 1;s:=0;for i:=1 to h do
forj:=1 to w do
b[i,j]:=0;i:=1;for j:=1 to h do
ifa[1,j]=1 then
b[i,j-1]:=b[i,j-1] xor 1;
b[i,j]:=b[i,j] xor 1;
b[i,j+1]:=b[i,j+1] xor 1;
b[i+1,j]:=b[i+1,j] xor 1;for i:=2 to h do
forj:=1 to w do
if b[i-1,j]=0 then
b[i-1,j]:=b[i-1,j] xor 1;
b[i,j-1]:=b[i,j-1] xor 1;
b[i,j]:=b[i,j] xor 1;
b[i,j+1]:=b[i,j+1] xor 1;
b[i+1,j]:=b[i+1,j] xor 1;
a[i,j]:=1;
a[i,j]:=0;i:=h;for j:=1 to w do s:=s+b[i,j];c[s]:=c[s]+1;if s=n:=p+1;until n&=p;writeln(f,k:5,c[k]:15);close(f);writeln('end');readln();end.//又改进了一下算法，这次稍微又快了一点。
#####################█
1#####################████
1#####################█　█　█　█　█
1#####################█　　　　　██　　███　　　
1#####################██　　　██　██　　███　███　　██　█
1#####################█　██　█　████　████████████　████　█　██　█
1#####################██　█　█████　███　██　██　█　　█　　█　██　██　███　█████　█　██
1#####################██　　　　████　██　██　　████　　　██████　　██████　　　████　　██　██　████　　　　██
1#####################　█　　　　　　　　　　███████　　█　　　　█　　　██　　██　█　　█　　█　　　　██　　███　　█　　　　█　　　██████　█　　　　　　　
1#####################█　█　　　　█　█　█　　██　　█　█　█　██　█　█　　　█　　█　　　　██　██　██　　██　██　██　　　　█　　█　　　█　█　██　█　█　█　　██　　█　█　█　　　　█　█
1#####################█　　　█　　　　　　　　█　　　█████　　　　　　█　　　███　██　██　████████　███　　█　███　　　　███　　█　　　　█　█　　█████　　███　██　　█　█　　██　　████　██　████　██　　
1#####################█　█　　　　　　█　█　█　　████　　█　█　█　█　　█　█　█　　　██████　　　　████　　████　　█　█　██　█　█　　█　█　██　█　█　　████　　████　　　　██████　　　█　█　█　　█　█　█　█　　████　　█　█　█　　　　　　█　█
1#####################██　█　███　█　█████　██　██　███　██　█　　　█　██　█　　███████　　█　████　　　████　██　█　█　█　█　███　　█　　█　　█　　███　█　█　█　█　██　████　　　████　█　　███████　　█　██　█　　　█　██　███　██　██　█████　█　███　█　██
1#####################█　　█　　　　█　　　　　　　　　　██　　　████　██　　██　　　█　　█　██　　　　　█　████　　　　█　　　　█　　　　█　　　　　███　█　　　　　██　　█　█　　　██　　██　　█　█　　　███　　　　　███　█　　　　　　　█　　　　█　　　　　██　　　　　█　████　██　　██　　　█　　█　　　　　██　　　█████　　█　　　　█　　　　　
1#####################█　██　　█　█　　██　█　███　　　█　　　███　███　　██　██　　█████　█　██　██　█　██　　　　█　　█　　█　　　　　　██　██　██　██　　█　██　██　██　██　█　█　　█　　█　　█　　█　█　██　██　██　██　█　　██　██　██　██　　　　　　█　　█　　█　　　　██　█　██　██　█　█████　　██　██　　███　███　　　█　　　███　█　██　　█　█　　██　█
1#####################　██　　█　█　　　　　　　　　██　　　█　　███████　　　　██　█　█　　　　　██　　　██　　███　　　██　　█　　　　████　█　█　　　　　　　　███　█　█████　███　　█　　　　███████　█　████　　　█　　█　　　████　█　███████　　　　█　　███　█████　█　███　　　　　　　　█　█　████　　　　█　　██　　　███　　██　　　██　　　　　█　█　██　　　　███████　　█　　　██　　　　　　　　　█　█　　██　
1#####################██　　　　█　　█　　██　　　██　██　　　　　　　██　██　　███　　██　█　　　███　███　　　███　　　███　　██　██　　████　██　█　　　　██　█　█　██　　　　█　　　　　█　　█　　██　█　　　██　█　█　█　█　██　　　　███　　　███　　　████　　███████████　　█　　█　█　　　███　　████　　　　██　█　█　██　　　　██　　　██　　█　███　　　██　██　██　██　██　██　　███　　██　█　　　███　███　　█　█　█　　███　　██　█　　　███　　██　█
1#####################██　█　███　　███　█　█████　██　█　　█　██　███　██　█　　█　　█　　█　██　█　　███　█　　█　███　　█　███████　　███████　██　███　　　　　　███　███　　　█　█　██　█　█　　　██████　　████　　█████　　　　　　██████　　　　　　　　　　　　██████　　　　　　█████　　████　　██████　　　█　█　██　█　█　　　███　███　　　　　　███　██　███████　　███████　█　　███　█　　█　███　　█　██　█　　█　　█　　█　██　███　██　█　　█　██　█████　█　███　　███　█　██
1#####################　█　　　　　　　　　　　　　　　　　　　　█████████████████　　█　　　　　　　　　　　　　　█　　　██　　　　　　　　　　　　██　█　　█　██████████　█　　　　████　　　　　　　　█████　　██　　█　　　　　　█　　██　　　　　██　　████　　██　　　██　████　█　　█　████　　█████████████████　　　█　████　█　　█　███　　███　　██　　████　　█　███　　　█　　█　　　　　　██　████　　　██　　　　　　　█　█　　　█　██████████　█　　█　████　██　　　　　███　█　　██　　　　　█　　　█　　　█　██　　█　█　█　　█　　█　█　　██　█　█　█　█　　　█　█　█　　　
1#####################█　█　　██████████　　█　█　█　　　█　　　　　　　　█　　　█　█　██　██　　　　　　██　██　█　　███　█　████　█　███　　　　　██　███　　███　██　　　███　　█　　　██　　　█　　████　███　█　████　█　███　██　　　█　　██████　　█　　　██　　██　████████　██　　██　　█　██████████　█　　██　　█　██████████　█　　██　　██　████████　██　　██　　　█　　██████　　█　　　██　███　█　████　█　███　████　　█　　　██　　　█　　███　　　██　███　　███　██　　　　　███　█　████　█　███　　█　██　██　　　　　　██　██　█　█　　　█　　　　　　　　█　　　█　█　█　　██████████　　█　█
1这是20*20以内的全亮解法，你可以复制到记事本里查看。
这个游戏现在基本玩法是把5X5的矩阵分成两块~按前面建立的坐标~X=1,2的两列构成2X5的阵，X=3，4,5的构成3X5的阵，由于游戏随机刷新的亮的灯，可能在某个时机就可以全点亮3X5的阵，由于特殊规律的存在，2X5不影响3X5,现在单独点2X5的阵，点一会可能出现只剩一盏或两盏，如果灭的灯出现在12，22，14，24这几个点，用你给的算法就没问题了，若是灭的灯出现在其他点，感觉要想办法把它移到这四个点，这样有什么算法吗
var a:array[1..100*100,1..100*101]
s: beginappend(f);writeln(f,'#####################');for i:=1 to m do begin
ifa[i,m+1]=0 then write(f,'　') else write(f,'█');
if(i mod w=0) then writeln(f);close(f); //这个函数将第x1行加到第x2行。procedure swap(x1,x2:integer);var pj:beginfor pj:=1 to m+1 do a[x2,pj]:=a[x1,pj] xor a[x2,pj]; beginassign(f,'diandeng.txt');rewrite(f);close(f);for k:=1 to 50 do begin writeln('start: ',k); w:=k; h:=k; m:=w*h;//从这里开始设置线性方程组阵。//将灯阵排成一条行，即1到25=m。//j列代表按钮，i行代表灯。//a[i,j]=1代表按动第j个按钮会打开第i个灯。//将所有按钮在这里设置（按钮也是1到25=m）。
fori:=1 to m do
for j:=1 to m+1 do
a[i,j]:=0;
fori:=1 to m do
a[i,i]:=1;
fori:=1 to m-1 do
if (i mod k&&0) then
a[i,i+1]:=1;
a[i+1,i]:=1;
fori:=1 to m-k do
a[i,i+k]:=1;
a[i+k,i]:=1;//这条语句设置矩阵的初始状态。//a[i,m+1]中的i代表第i个灯。
fori:=1 to m do
a[i,m+1]:=1;//从这里开始解线性方程组。下面的部分不用修改。 {output();
forj:=1 to m do
if a[j,j]=0 then
for i:=j+1 to m do
if a[i,j]=1 then t:=i;
swap(t,j);
for i:=j+1 to m do
if a[i,j]=1 then swap(j,i);
{ output();
forj:=m downto 1 do
for i:=j-1 downto 1 do
if a[i,j]=1 then swap(j,i); output();//线性方程组解完，下面计算矩阵的秩。 s:=0;
fori:=1 to m do if a[i,i]=0 then s:=s+1;//s=n代表方程组还有n个未知量，则方程有2^n个解。 append(f); writeln(f,k:5,s:15); close(f);writeln('end');readln();end.//现在这个算法把时间复杂度从2^n降到了n^5，空间复杂度从n^2变为了n^4。计算50内的解不在话下。
楼主的图解....BJ4
登录百度帐号推荐应用
为兴趣而生，贴吧更懂你。或点灯游戏（三）
本阶段我们重点研究各阶可解状态及其规律。首先研究一下一些规律。
等效转化主要分为两种（等效转化的定义为通过点击某一盏灯的相邻灯以实现该灯的熄灭，并且整体往特定方向进行）：1、对面相互转化（本篇采用从下往上转化）；2、顺逆时针相互转化（本篇采用逆时针转化）。
我们发现以下规律（以6阶为例）：
1、叠加原理
如图1和图2所示，状态4-6分别是状态1-3对面转化后的状态。状态2是状态1和状态3的叠加，经过对面转化后我们发现状态5是状态4和状态6的叠加。此处叠加需要说明，即负负得正原理，可以将灯的亮灭情况分别对应减加号。两灭得到灭，两亮得到灭，一亮一灭得到亮。即
因此，细化到只有底层单个的情况（以6阶为例），一共只有三种情况，根据叠加原理可以组合出任意的六阶情况，如图3和图4所示。叠加原理见上一步分析。
2、翻转原理
根据图5我们可知：1和3并不相同，即当经历两次翻转后，状态并不能复原。
3、旋转原理
根据图6我们可知：当状态1通过逆时针旋转变换得到2时，与状态2相同的状态3通过顺时针旋转变换，可以得到与状态1相同的状态4。
在上述三个原理的基础上，我们仔细研究一下从2阶开始的可解规律。
2-4阶比较简单，可以直接给出结果。5阶是我们的研究重点，6阶作为拓展进一步补充说明。
如图7所示。一个小方块表示一盏灯，有点状底纹表示初始状态为亮，有蓝色表示该方块点击一次（所有方块要么蓝色即点击一次，要么白色即不点击，之前博客中已经证明）。方块中的数字代表这个方块的状态改变次数（即包括自身和周围的点击次数）。显然，当数字为奇数时，该方块的状态改变，当数字为偶数时，该方块的状态不变。
由此可见2-3阶的所有状态都有解，解法为蓝色部分。
4阶采用穷举法，即将第一层的状态进行穷举，然后依据奇偶性原理（需要全部熄灭），逐步计算，得到每个状态的解。我们可以看到最后一层全部为偶数，即状态都不能改变，而为了达到全部熄灭的效果，初始状态就要是灭，因此采用之前博客里的归纳法，最后一层的状态均为全部熄灭，只要不是熄灭，均是无解的，而全部熄灭说明已经解出。
&&&&&二、5阶
5阶是我们的研究重点，因为从5阶开始出现部分可解状态，并且5阶的状态数也达到了19个，开始增多到需要归纳的程度。先来看一下最初的可解情况，如图8所示。一共有5种可解情况。那么如何肯定一共只有这5种可解状态呢，以及这些可解状态的解法是唯一的吗（镜面对称属于1种状态）？带着这些问题，我们还是要从另一个角度进行求解。我们将第一层的点击情况（黄色）穷举，得到最后一层的N种情况（点状底纹），如图9所示。
将同种类型的总结，得到图10。由此得到了5阶全部的解。之前我们了解到旋转可逆原理，依据这一原理，我们可知，旋转相互得到的状态的等效的。我们进一步验证这些可解状态之间的关系，如图11所示。
6阶结果除了和5阶相同的方法以外，在研究过程中还发现一种方法，我将之成为无中生有法。我们可以设想，如果初始状态就是全部熄灭的，那么我们不经意点了其中一个方块，然后随意点其他方块，根据可逆原理，最终必然可以回到全部熄灭状态，即有解。那么我们还是以归纳法加穷举法，即考虑最后一层的点击情况，然后逆推。如图12所示，状态1即初始全部熄灭状态，状态2为最后一层点击最左边的方块开始启动，往上推（方法为翻转），得到最上面一层的状态25即可解状态，解法为26（黄色方块即需要点击的方块）。同理状态3也可以用同样的方法推导，得到状态35为可解状态，解法为36。依次类推。
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。问题补充&&
本页链接：
猜你感兴趣