有一系列的灯泡表示为真/假的数组,每个灯泡都有一个开关,通过点击任何灯泡,你可以切换它和2个相邻的灯泡(左边1个,右边1个) ;如果点击开关的灯泡在边缘 – 当然只有1个相邻切换).
需要完成的是一种方法,它接受一系列打开/关闭灯泡的阵列,另一个方法表示在点击某些开关之后所谓的第一阵列的另一种状态.
因此必须使用递归来确定是否存在将数组1转换为数组2的切换点击组合.
这是方法的签名：
public static boolean disco(boolean[] init,boolean[] target)
如果array init可以转换为target,则返回true,否则返回false.
方法必须是静态的,不要使用循环和放大器.任何其他静态和全局变量,只有本地变量.
例：
boolean[] init = {true,false,true,false};
boolean[] target = {false,true};
对于2个以上的数组,disco(init,target)将返回true,因为切换第1个和第4个灯泡会产生目标状态(请记住相邻的灯泡也会被切换).
解决方法
public static boolean disco(boolean[] init,boolean[] target)
{
return recurse(init,boolean,0);
}
public static boolean recurse(boolean[] init,boolean[] target,int min)
{
if (min == init.length)
if (init == target)
return true;
else
return false;
boolean[] temp = "init with a change at min";
boolean a = recurse(init,target,min+1);
boolean b = recurse(temp,min+1);
return a||b;
}
新版本
我把它分解为三种情况：
案例1：长度％3 = 0
通过更改第一个灯泡和第二个灯泡,您可以仅在第3个灯泡上影响更改.
然后更改为4和5将使第6个唯一更改.我们看到我们可以改变每个灯泡,其指数可被3整除.
向后工作(从结束开始)我们可以做同样的事情,但这次它告诉我们我们可以改变指数(i 1)被3整除的灯泡.
结合这两者,我们看到如果我们想要改变索引0,1 mod 3,我们就可以.但是要改变2,我们只需要改变一个相邻的0,1对然后在中间做一个改变.所以在所有情况下这些都是可以解决的.
案例2：长度％3 = 1
就像第一种情况一样,但我们可以影响0,2 mod 3的单个变化,从而挤压1 mod 3的情况.
案例3：长度％3 = 2
向前和向后工作仅产生0 mod 3的情况.我们对灯泡进行了两次更改(因为我们可以忽略对位置0的任何更改).更改1或2将反转由两个0包围的位置,而更改0将在1,2的相邻块中交换奇偶校验,它们之间有0(如果绘制它会更容易).但到目前为止我所展示的是0都可以被纠正,并且在任何相邻的1,2中你可以修复两者,如果它们是错的而不改变其他任何东西.如果有错误,则将更改传播到相邻的1,2对.如有必要,可以移动此更改.这意味着1,2个位置的任何偶数个错误都可以修复,但奇数不能.位置0的所有错误都可以修复.
public static boolean disco(boolean[] init,boolean[] target)
{
if (init.length%3 == 0 || init.length%3 == 1)
return true;
return recurse(init,true);
}
public static boolean recurse(boolean[] init,int index,boolean even)
{
if (index = init.length)
return even;
if (init[index] != target[index] && index%3 != 0)
even = !even;
return recurse(init,index+1,even);
}
