-2

算法谜语

你得到一个数字 x，你必须在一个大小为 2x 的数组中设置从 1 到 x twic 的所有值。规则是数字必须放在与其值不同的单元格中。例如，如果您像这样设置数字 2：| 2 | | | | | bex 必须是这样的：|2| | 2 | | |

假设 x=4，那么我们有一个 8 个单元格的数组，我们可以这样设置数字：1 2 3 4 5 6 7 8 |4|2|3|2|4|3|1|1|

您可以通过各种方式放置号码。

你可以对数字10（数组大小 20）、12（数组大小 24）做同样的事情吗？如果是，请说明如何，如果不是，请说明每个数字的原因。

4

2 回答 2

0

10 是不可能的。12 是可能的。我尝试了所有不超过 13 的整数，并且有一个明确的模式，我确信可以证明（但我现在不知道如何证明）：

1  yes
2  no
3  no
4  yes
5  yes
6  no
7  no
8  yes
9  yes
10 no
11 no
12 yes
13 yes

它可以通过递归函数来解决，该函数尝试所有可能性，如果找不到匹配项，则使用回溯。

于 2012-08-19T08:58:24.250 回答
0

这个问题是NP-Complete，你必须尝试所有可能性来确定可行性并获得一组可能的解决方案。

如果您想要由函数定义的是否可以完成它的是/否答案1/2(4n + (-1)^n - 1)，插入从 1...infinity 开始的 n 值将为您提供是答案的数字序列。不包括证明:)

为了澄清，解决方案集的发现是 NP-Complete 并且可以使用上述公式完成给定 N 的是/否答案。（我希望我没有捏造那个数学，它是一个生成函数）

于 2012-08-19T09:01:38.883 回答