查人人中国名人网孕妇餐后血糖正常值:著名的灯光游戏,征求数学一般性解
来源：百度文库 编辑：查人人中国名人网 时间：2024/04/24 02:47:20
一幢大楼上有很多窗户,排成N*M的方阵，有的亮有的暗。你每次可以选取其中一个窗户进行操作，每次操作使该窗户和它上、下、左、右共5个构成十字形的窗户（在角上为3个构成L形，边上为3个构成T形）均分别改变一次状态（亮的变暗，暗的变亮）。求一种方法，经过有限步操作使大楼从原始状态变成全部为暗。
如果弄不出，请帮忙给出下列一个或几个简化条件同时成立下的解或者问题的性质叙述和证明（如N，M在什么条件下有解，原始状态怎样的一定无解等）
1、N=M
2、原始状态为灯光全亮
……
显然，操作步骤的顺序与结果无关，且易证所需的最小步数Q满足：
N*M/5＜Q≤N*M（右边在N=M=4时可取等号，左边肯定不是精确下限）；此时每个窗户至多被操作1次。
或者求计算机求解算法：搜索的话效率太低[搜索算法复杂度O(N，M)=2^(N*M)]，当N=M=6时估算须30小时以上；如果哪位仁兄能提供多项式算法的话万分感谢！！！！
这个题目我以前研究过，但是没有找到过数学方法的解答，只会通过编程来解决。
复杂度为2^m 或 2^n
以5X5的格子为例。
我的思路是这样的.
1.任何一盏灯最多只需要点一次就可以了,而且跟点的顺序无关.
因为一盏灯变不变取决与它周围(包括自己)的灯被点过多少次,
如果是奇数次就变,如果是偶数次就不变.
所以一盏灯如果被点了两次,实际上对它自己以及它周围的灯没有什么贡献.
2.只要第一行的点法确定了,那么后面每一行的点法都确定了.
假设第一行点过之后,第一行还有若干盏灯亮着,
那么第二行只能点那些亮着的灯下面的那些灯,只有这样才不违背第一条原则,
而且能使第一行全灭.
因为假使点了其它的灯,就会使第一行的灯重新变亮,
那么还需要回到第一行去点才能使其变灭,而第一行本来已经完成了,这样就
违背了第一条原则.
跟据以上两条原则,那么只要第一行试遍了00000,00001,00010,....11111
(对于5x5的情况,也就是0--31),1表示点,0表示不点.
按照上面的点法去点,只要看最后一行是不是全灭就行了.
那么所有的解法都可以得到.
程序如下,用的C++
#include <iostream>
#include <vector>
using namespace std;
vector<int> dec2bin(int d)//把十进制数转化成二进制的0,1串
{
vector<int> v;
do{
v.push_back(d%2);
d/=2;
}while(d>0);
return v;
}
int n12int(int n)//把n个1组成的二进制数转化为十进制数,以便确定尝试的上界
{
unsigned int b=0;
for(int i=0;i<n;i++){
b<<=1;
b|=1;
}
return b;
}
class light
{
public:
light(int nn);
~light();
void turn(int i,int j);//点击第i行j列的灯
int test(const vector<int> &v);
//把一个二进制串作为第一行的点法,测试是不是解
void answer();//求出所有的解
void display();//显示各灯状态
void reset();//把所有灯置1
private:
int n;//n*n的灯阵,初始全部为1,要求最后全部变成0
int ** lts;
};
light::light(int nn)
{
n=nn;
lts=new int * [n+2];
//(n+2)*(n+2)的矩阵,相当于在四周各加了一层,这样就不需要单独考虑四条边了
//所要的灯的下标为从1到n
for(int i=0;i<n+2;i++)
lts[i]=new int[n+2];
for(int i=0;i<n+2;i++)
for(int j=0;j<n+2;j++)
lts[i][j]=1;
}
light::~light()
{
for(int i=0;i<n+2;i++)
delete[] lts[i];
delete[] lts;
}
void light::turn(int i,int j)
{
if(i<1||j<1||i>n||j>n){
cout<<"Error"<<endl;
exit(1);
}
lts[i][j]=abs(1-lts[i][j]);
lts[i-1][j]=abs(1-lts[i-1][j]);
lts[i][j-1]=abs(1-lts[i][j-1]);
lts[i][j+1]=abs(1-lts[i][j+1]);
lts[i+1][j]=abs(1-lts[i+1][j]);
//display();
}
void light::display()//显示各灯的状态
{
cout<<"==================="<<endl;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
cout<<lts[i][j];
cout<<endl;
}
cout<<"==================="<<endl;
}
void light::reset()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
lts[i][j]=1;
}
int light::test(const vector<int> &v)
{
if(v.size()>n)exit(0);
reset();
for(int i=0;i<v.size();i++)
if(v[i]==1)turn(1,i+1);
for(int i=2;i<=n;i++)
for(int j=1;j<=n;j++)
if(lts[i-1][j]==1)turn(i,j);
//display();
int tmp;
for(tmp=1;tmp<=n;tmp++)
if(lts[n][tmp]==1)break;//查看最后一行
if(tmp==n+1)return 1;
return 0;
}
void light::answer()
{
int up=n12int(n);//确定尝试的上界
for(int i=0;i<=up;i++){
vector<int> v=dec2bin(i);
if(test(v)){
cout<<n<<'x'<<n<<':';
for(int j=0;j<v.size();j++)
cout<<v[j];
cout<<endl;
}
}
}
main()
{
light l5(5);
l5.answer();
}
输出:
5x5:11
5x5:1011
5x5:01101
5x5:00011
好强，佩服！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
复杂度为2^m 或 2^n
以5X5的格子为例。
我的思路是这样的.
1.任何一盏灯最多只需要点一次就可以了,而且跟点的顺序无关.
因为一盏灯变不变取决与它周围(包括自己)的灯被点过多少次,
如果是奇数次就变,如果是偶数次就不变.
所以一盏灯如果被点了两次,实际上对它自己以及它周围的灯没有什么贡献.
2.只要第一行的点法确定了,那么后面每一行的点法都确定了.
假设第一行点过之后,第一行还有若干盏灯亮着,
那么第二行只能点那些亮着的灯下面的那些灯,只有这样才不违背第一条原则,
而且能使第一行全灭.
因为假使点了其它的灯,就会使第一行的灯重新变亮,
那么还需要回到第一行去点才能使其变灭,而第一行本来已经完成了,这样就
违背了第一条原则.
跟据以上两条原则,那么只要第一行试遍了00000,00001,00010,....11111
(对于5x5的情况,也就是0--31),1表示点,0表示不点.
按照上面的点法去点,只要看最后一行是不是全灭就行了.
那么所有的解法都可以得到.
程序如下,用的C++
#include <iostream>
#include <vector>
using namespace std;
vector<int> dec2bin(int d)//把十进制数转化成二进制的0,1串
{
vector<int> v;
do{
v.push_back(d%2);
d/=2;
}while(d>0);
return v;
}
int n12int(int n)//把n个1组成的二进制数转化为十进制数,以便确定尝试的上界
{
unsigned int b=0;
for(int i=0;i<n;i++){
b<<=1;
b|=1;
}
return b;
}
class light
{
public:
light(int nn);
~light();
void turn(int i,int j);//点击第i行j列的灯
int test(const vector<int> &v);
//把一个二进制串作为第一行的点法,测试是不是解
void answer();//求出所有的解
void display();//显示各灯状态
void reset();//把所有灯置1
private:
int n;//n*n的灯阵,初始全部为1,要求最后全部变成0
int ** lts;
};
light::light(int nn)
{
n=nn;
lts=new int * [n+2];
//(n+2)*(n+2)的矩阵,相当于在四周各加了一层,这样就不需要单独考虑四条边了
//所要的灯的下标为从1到n
for(int i=0;i<n+2;i++)
lts[i]=new int[n+2];
for(int i=0;i<n+2;i++)
for(int j=0;j<n+2;j++)
lts[i][j]=1;
}
light::~light()
{
for(int i=0;i<n+2;i++)
delete[] lts[i];
delete[] lts;
}
void light::turn(int i,int j)
{
if(i<1||j<1||i>n||j>n){
cout<<"Error"<<endl;
exit(1);
}
lts[i][j]=abs(1-lts[i][j]);
lts[i-1][j]=abs(1-lts[i-1][j]);
lts[i][j-1]=abs(1-lts[i][j-1]);
lts[i][j+1]=abs(1-lts[i][j+1]);
lts[i+1][j]=abs(1-lts[i+1][j]);
//display();
}
void light::display()//显示各灯的状态
{
cout<<"==================="<<endl;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
cout<<lts[i][j];
cout<<endl;
}
cout<<"==================="<<endl;
}
void light::reset()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
lts[i][j]=1;
}
int light::test(const vector<int> &v)
{
if(v.size()>n)exit(0);
reset();
for(int i=0;i<v.size();i++)
if(v[i]==1)turn(1,i+1);
for(int i=2;i<=n;i++)
for(int j=1;j<=n;j++)
if(lts[i-1][j]==1)turn(i,j);
//display();
int tmp;
for(tmp=1;tmp<=n;tmp++)
if(lts[n][tmp]==1)break;//查看最后一行
if(tmp==n+1)return 1;
return 0;
}
void light::answer
期待用数学方法的解答
设想通过解释边框的情况证明N*M于(N+2)*(M+2)的关系，可以简化问题。
我见过，应该在十年前的《科学画报》上有
佩服