java - 数组递归

Question

我有一个作业我想不通，任何指点将不胜感激，它是这样的:

有一系列灯泡表示为 true/false 数组，每个灯泡都有一个开关，通过点击任何灯泡，您可以切换它以及 2 个相邻的灯泡(左边 1 个和另一个 1 个)从右边；如果点击开关的灯泡在边缘——当然只有 1 个相邻的切换)。

需要完成的是一种方法，该方法接受一系列打开/关闭的灯泡和另一个代表另一种状态的方法，应该是单击某些开关后的第一个数组。 .! 因此必须使用递归来找出是否存在将数组 1 转换为数组 2 的开关点击组合。

这是方法的签名:

public static boolean disco(boolean[] init, boolean[] target)

如果数组 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
通过更换第一个灯泡和第二个灯泡，您可以仅影响第三个灯泡的变化。 然后更改为 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。剩下的唯一 Action 我们对灯泡进行了两次更改(因为我们可以忽略位置 0 的任何更改)。更改 1 或 2 将反转两个 0 包围的位置，而更改 0 将交换 1,2 的相邻 block 中的奇偶校验，它们之间有一个 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);
}