-2

アルゴリズムのなぞなぞ

数値 x を取得し、1 から x までのすべてをサイズ 2x の配列に設定する必要があります。ルールは、数値をその値との差であるセルに配置する必要があるということです。たとえば、次のように数値 2 を設定するとします。2 | | | | | | | | | bex one は次のようにする必要があります: |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 であり、実現可能性を判断し、可能な解決策の結果セットを取得するためにすべての可能性を試す必要があります。

function で定義されていることを実行できるかどうかについて、yes/no の回答が必要な場合は1/2(4n + (-1)^n - 1)、1 から始まる n の値をプラグインします...無限大は、yes の回答である一連の数字を提供します。証拠は含まれていません:)

明確にするために、解集合の発見はNP完全であり、与えられたNに対するイエス/ノーの答えは上記の式を使用して行うことができます。（私はその数学をごまかしていないことを願っています、それは生成関数です）

于 2012-08-19T09:01:38.883 に答える