3

这个任务实际上是作为作业交给我们的，但是作业中的要求是编写一个递归方法，如果我们对数组 A 执行了几个步骤后数组 A 可以匹配数组 B，则该方法可以返回 true 或 false，我已经以递归方式回答了这个问题，我有兴趣找到是否有更智能的方法，可以用来解决这种类型分配的某种模式或方程式，话虽如此，我不确定是否作业标签仍然相关，但我添加它以防万一。

以下是详细信息： 给定两个长度相同的布尔数组。如果给定数组“init”可以匹配目标数组“target”，则返回 true，问题是：每当我们将一个索引的值从 true “翻转”为 false 时，反之亦然，索引中的值在右侧和左侧当前索引的值，也翻转它们的值（如果这样的索引当然在数组范围内），例如：

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

在这种情况下，答案是正确的，因为我们可以翻转 init 数组的第一个点 [0]，结果是：

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

然后翻转 init 数组中的第 4 个点 [3]，导致 init 和目标数组之间匹配：

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

递归地，它只是测试“翻转状态”或没有“翻转状态”的两个选项，并在每个测试的数组索引中前进，这将递归检查所有选项，如果找到匹配项，最终返回 true。

现在回到我的问题上，有没有更好的方法来解决这类问题而不必检查这么多选项？它不必是递归的……事实上，最好不是递归的：）所以请随时分享您的想法和建议。

谢谢！

4

3 回答 3

1

好的，我不打算写实现，但这里是基本逻辑。找出需要更改的值，例如。{true ,false ,false,true} 与 { true, true,false,false} = {true != true,false != true, false != false, true != false} = {false,true,false,true }

现在，我们将尝试翻转这个新数组，直到从 0 到 (size-2) 的所有值都等于 false。我们知道我们可以线性地做到这一点。如果 a[0] == true，则在 a[1] 处翻转，如果 a[1] == true，则在 a[2] 处翻转。只需遍历每个值，大小为 - 2。

最终，整个数组将为假，除了最后一个值为真或假的值。现在的问题是，如果只有最后一个值为真，是否可以转换数组以使所有值都为假？

于 2012-06-09T09:41:21.373 回答
1

评论

对于 n 位，可以有 n 次操作用于不同的更改。

  • 操作顺序无关紧要！_ （交换的，联想的）
  • 执行两次操作会恢复相同的状态。（反光的）

因此，每个解决方案都是 n 个操作的子集，可以按任意顺序执行。

  • 与算法无关：如果有 k > 4 个连续不变的位，则可以排除中间位在 [i+2] 到 [k-1-2] 的操作。
  • 最多 3 个操作会影响一个特定的位。因此，对于所有不同的位，您可以收集要从中选择的操作。
  • 在针对一位的3 次操作中，必须选择1 或 3次操作（2 次操作将恢复它）。
于 2012-06-09T11:03:44.417 回答
1

如何加快实现速度（对是否可以使用给定规则转换数组的问题回答是/否）：

  • 将所有内容表示为位而不是真假值数组。那么位翻转模式为：1100...00, 1110...00, 0111...00, ..., 0000...11。我们将搜索位翻转模式通过执行 BFS（或 DFS）来转换数组的所有可能方式。

  • 存储是否可以使用位集进行转换（如果语言允许此类低级实现或提供此类库）或 char/boolean 数组。这将减少转换使用的空间。数组/位集的大小为 2 ^ n。

  • 当你得到所有可能的变换后，你可以通过对输入和目标进行异或来回答O(1)中元素个数固定的问题，然后检查这种变换是否存在。好吧，如果元素的数量不同，那么没有太大的优势。

它应该能够达到 20-23 位，同时仍将时间保持在 1-3 秒以下（假设 C++ 代码）。对于 Java，它可能会慢一点，但应该在 30 秒以下。

不过，时间复杂度并不比您当前的方法好。

您也可以搜索变换模式 0000...01（提前终止，而不是搜索可能变换的整个空间），然后使用 Darcy Rayner 建议的方法。最坏情况的复杂性并不比您当前的方法好。

我不知道这个问题是否有任何数学解决方案。目前，这都是蛮力。

编辑

在数学上，可以证明我们可以用 Darcy Rayner 建议的方法（通过分析最后 2 位）贪婪地将差异减少到 1。

也可以证明，我们可以随时否定整个模式，即长度为3k，平凡，长度3k + 1，两端翻转，中间所有3组，长度3k + 2，翻转在一端，所有 3 组在中间。

所以如果我们有最后一位 = 1，我们可以翻转整个模式。如果原始长度是 3k + 1，我们最终会得到 3k 的差异（真），可以简单地翻转。如果原始长度是 3k，我们最终会得到 3k - 1 的差异，我们可以在一端翻转，并翻转每组 3。在这两种情况下（长度 3k + 1 和长度 3k），变换总是可能的。

我目前对案例 3k + 2 没有任何证据。

于 2012-06-09T10:02:52.590 回答