数组递归

Question

我有一个我无法弄清楚的作业，任何指示都会非常感激，它是这样的：

有一系列灯泡表示为真/假数组，每个灯泡都有一个开关，通过单击对于任何灯泡，您都可以切换它以及 2 个相邻的灯泡（左侧 1 个，右侧 1 个；如果单击边缘上的开关灯泡 - 当然只有 1 个相邻的切换）。

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

该方法的签名如下：

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

如果数组 init 可以转换为 ，则返回 true >目标，否则为 false。 方法必须是静态的并且不能使用循环 &任何其他静态和全局变量，仅限本地变量。

示例：

boolean[] init = {true, false, true, false, true, false};
boolean[] target = {false, true, false, true, false, true};

对于上述 2 个数组，disco(init, target) 将返回 true，因为切换第一个和第四个灯泡将产生目标状态（记住相邻灯泡也会被切换）。

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。剩下的唯一移动是对灯泡进行两次更改（因为我们可以忽略对位置 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);
}

Answer 2

因此，用文字来说，这就是我的做法：

如果剩下的灯泡少于或等于 3 个，则很容易检查它们是否可以切换以确保其正确。

如果有超过三个灯泡，请执行以下操作：

检查第一个灯泡是否正确。如果是这样，则从第二个灯泡开始递归地处理子数组。

如果第一个灯泡不正确，请切换第二个灯泡（切换第一个灯泡不起作用，因为之前的灯泡会切换回来）。现在，第一个灯泡是正确的。继续从第二个灯泡开始的子阵列。

Answer 3

提示：设 a1, a2, ..., ak, ..., an 为输入，b1, b2, ..., bk, ..., bn 为所需输出。

您可以递归测试左侧和右侧，然后合并结果。棘手的部分是合并结果。

从左侧开始。

1. 测试 a1, a2, ..., ak, true 与 b1, b2, ..., bk, true。
   1. 如果为真，则测试 a1, a2, ..., ak 到 b1, b2, ..., bk。
      1. 如果为 true，则从 a1, a2, ..., ak 到 b1, b2, ..., bk 的解决方案不能包括切换第 k 个开关
      2. 如果为 false，则从 a1, a2, ..., ak 到 b1, b2, ..., !bk 的解决方案必须包括切换第 k 个开关
   2. 如果为 false，则测试 a1, a2,...,ak 到 b1, b2,...,bk
      1. 如果为 true，则从 a1,a2, ..., ak 到 b1, b2 ,.., bk 的解决方案必须包括切换第 k 个开关
      2. 如果为 false，则从 a1,a2,...,ak 到 b1, b2,...,!bk 的解决方案不能包含切换第 k 个开关

在左侧进行两次测试后，您可以在右侧执行类似的测试。您将能够组合测试的值，因为您将知道第 k 个开关是否被切换。

Answer 4

感谢大家的帮助，这就是我的想法：

public static boolean disco(boolean[] init, boolean[] target)
{
    if (java.util.Arrays.equals(init, target)) {
        return true;
    } else {
        return disco(init, target, 0);
    }
}

private static boolean disco(boolean[] init, boolean[] target, int i)
{
    if (i > init.length-1) {
        return false;
    }

    disco(init, target, i+1);
    boolean t = false;

    if (init[i] != target[i]) {
        switchBulb(init, target, i);
    }

    if (java.util.Arrays.equals(init, target)) {
        t = true;
    }

    return t;
}

private static void switchBulb(boolean[] init, boolean[] target, int i)
{
    if ( (i > 1) && (init[i-1] != target[i-1]) && (init[i-2] != target[i-2]) ) {
        // If there's a series of 3 opposite-to-target bulbs, switch the middle one & from both sides
        init[i-1] = !init[i-1];
        init[i] = !init[i];
        init[i-2] = !init[i-2];
    } else if (i > 0 && i < init.length-1) {
        // There's only 1 bulb or 2 adjacent bulbs that are opposite of target.
        if (i == 1 && (init[0] != target[0]) ) {
            // First 2 bulbs are opposite of target's, so switch the 1st one.
            init[i-1] = !init[i-1];
            init[i] = !init[i];
        } else if ( (i == init.length-2) && (init[i+1] != target[i+1]) ) {
            init[i+1] = !init[i+1];
            init[i] = !init[i];
        } else {
            init[i] = !init[i];
            init[i-1] = !init[i-1];
            init[i+1] = !init[i+1];
        }
    } else {
        // First bulb or last bulb.
        init[i] = !init[i];
        if (i == 0) {
            init[i+1] = !init[i+1];
        } else {
            init[i-1] = !init[i-1];
        }
    }
}

我觉得我在这里使用的递归很少，如果正确使用递归，可能会干净得多。 有什么想法吗？
我说的是 switchBulb 函数，它可以用更复杂的递归逻辑进行交换，还是我错了？

例如，如果您只是一个接一个地迭代灯泡并与目标数组进行比较，则无需对所有灯泡组合都正确（请参见示例），那么如何通过递归来模拟随机灯泡切换呢？或者有一个模式吗？一定有，如果没有，它怎么知道什么时候停止？

我想我已经找到了解决方案，如果有人感兴趣的话稍后会发布......