数组递归

Question

我有一个我无法弄清楚的任务,任何指针都会非常感激,它是这样的:

有一系列灯泡表示为真/假的数组,每个灯泡都有一个开关,通过点击任何灯泡,你可以切换它和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, true, false};
boolean[] target = {false, true, false, true, false, true};

对于2个以上的数组,disco(init,target)将返回true,因为切换第1个和第4个灯泡会产​​生目标状态(请记住相邻的灯泡也会被切换).

Answer 1

新版本

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, target, min+1);  
  return a||b;
}  

新版本

我把它分解为三种情况:

情况1:长度%3 = 0
通过更改第一个灯泡和第二个灯泡,您可以仅在第3个灯泡上影响更改.然后更改为4和5将使第6个唯一更改.我们看到,我们可以改变指数3整除每个灯泡
工作向后(末尾开始),我们可以这样做,但是这一次它向我们展示了我们可以通过3改变与指数灯泡(我+ 1)整除
结合二,我们看到如果我们想改变一个指数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,target,0, true);
}

public static boolean recurse(boolean[] init, boolean[] target, int index, boolean even)
{
  if (index = init.length)
    return even;
  if (init[index] != target[index] && index%3 != 0)
    even = !even;
  return recurse(init, target, index+1, even);
}