回 帖 发 新 帖 刷新版面

主题:[原创]点灯问题集锦

问题背景描述;有n盏灯排成一行(可以扩展到多行),每次对一个灯进行操作,可以改变其本身和周围的灯的状态,即原来亮着的将熄灭,原来熄灭的将被点亮。
例如:操作第5盏灯,则第4、5、6盏灯的状态都发生变化;而操作靠边的第1个开关盏灯时,第1、2盏灯的状态都发生变化。
逻辑变量约定:用0和1表示灯的”暗亮“情况和”是否操作“信息;0表示灯暗,1表示灯亮;0表示不对灯进行操作,1表示对灯进行操作。
      由此模型可以引发出多种问题,我仅选几个具有代表性的问题和大家探讨,
如有错误和不严谨之处,欢迎批评指正,并热烈欢迎有心之士补充新的题目!

问题一:已知初始时每盏灯都处于熄灭状态,现在依次对编号为i(0 <= i < n)的灯操作i次,求最后所有灯的”暗亮“情况。
函数接口: void Solve(const int start[], int end[], int n);
其中:start[]表示了初始状态,它的每个元素均为0,表示初始时每盏灯都处于熄灭状态;end[]表示了目标状态,需要返回目标状态,即最后所有灯的”暗亮“情况。
n表示有n盏灯。

问题二:已知初始时每盏灯都处于熄灭状态,现在从第一盏灯开始,每隔i(0 <= i <= n/2)盏灯操作一次,求最后所有灯的”暗亮“情况。例如:当i=2时,需要操作的灯为第1,3,6,。。。盏灯。
      函数接口: void Solve(const int start[], int end[], int n, int distance);
其中:start[]表示了初始状态,它的每个元素均为0,表示初始时每盏灯都处于熄灭状态;end[]表示了目标状态,需要返回目标状态,即最后所有灯的”暗亮“情况。
n表示有n盏灯,distance表示每隔distance盏灯操作一次。

问题三:已知初始时每盏灯都处于熄灭状态,请问如何操作可以使得所有的灯都被点亮,并返回所需的操作次数。如果没有解则如果没有解则返回-1,多个解则只输出一个即可。
      函数接口: int Solve(int operation[], int n);
其中:operation[]存储每盏灯的”是否操作“信息,需要返回。0表示不对灯进行操作,1表示对灯进行操作。n表示有n盏灯。
返回所需的操作次数。

问题四:问题三的扩展,已知初始时每盏灯都处于熄灭状态,请问如何操作可以使得所有的灯都被点亮,并返回所需的最少操作次数,如果没有解则返回-1。
      函数接口: int MinSolve(int operation[], int n);
其中:operation[]存储每盏灯的”是否操作“信息,需要返回。0表示不对灯进行操作,1表示对灯进行操作。n表示有n盏灯。
返回所需的最少操作次数。

问题五:问题四的扩展,现在给出n盏灯的初始的状态和目标状态,
要求计算:从初始状态改变到目标状态所需要的最少操作次数。如果没有解则如果没有解则返回-1。
      函数接口: int MinChange(const int Start[],const int End[], int n);
其中:start[]表示了初始状态,end[]表示了目标状态。n表示有n盏灯。
返回所需的最少操作次数。
如果增大难度,还可以要求返回操作情况,即把函数接口改为:
      函数接口: int MinChange(const int Start[],const int End[], int operation[], int n);
其中:start[]表示了初始状态,end[]表示了目标状态。n表示有n盏灯。operation[]存储每盏灯的”是否操作“信息,需要返回。
返回所需的最少操作次数。

问题六:问题三的扩展,由一行扩展到多行。
有m*n盏灯,排成m行n列( 1<= n <= 30).对一个灯进行操作,可以改变其本身和周围的灯的状态,这里的周围指的是上下左右。根据灯的位置分布我们可以知道,角点影响3个灯,边4个,中间5个。
例如:操作坐标位置为(0, 0)的灯,则改变状态的灯有三盏,它们分别是坐标位置为(0, 0),(0, 1)和(1, 0)的灯;而操作操作坐标位置为(0, 1)的灯,则改变状态的灯有四盏,它们分别是坐标位置为(0, 0),(0, 1),(0, 2)和(1, 1)的灯;
而操作操作坐标位置为(2, 1)的灯,则改变状态的灯有五盏,它们分别是坐标位置为(2, 0),(2, 1),(2, 2),(1, 1)和(3, 1)的灯。
     已知初始时每盏灯都处于熄灭状态,请问如何操作可以使得所有的灯都被点亮。
返回所需的操作次数,如果没有解则如果没有解则返回-1,多个解则只输出一个即可。
(当然也可以求所需操作次数最少的一个,但当n较大时(超过10)运算量很大)
      函数接口: int Solve(int operation[][MAX], int m, int n);
其中:operation[]存储每盏灯的”是否操作“信息,需要返回。0表示不对灯进行操作,1表示对灯进行操作。m表示有m行,n表示有n列。
返回所需的操作次数。
      一些例子:
当m = n = 1时, 返回1, operation[1][1] = {1};
当m = n = 2时, 返回4, operation[2][2] = {{1,1},
                                          {1,1}};
当m = n = 3时, 返回5, operation[3][3] = {{1,0,1},
                                          {0,1,0}
                                          {1,0,1}};

回复列表 (共14个回复)

11 楼

连载完.
请各位网友批评指正.

12 楼

大哥强!小弟佩服的六体投地

13 楼

mark

14 楼

mark

我来回复

您尚未登录,请登录后再回复。点此登录或注册