0

そのように定義されたフィボナッチコードがあります：

C(0) = 0
C(1) = 1
C(2) = 01
C(3) = 101
C(4) = 01101
C(5) = 10101101
.
.
.

このコーディングシステムを使用したゲームがあり、ボードがあります（例：1101101）。このゲームでは、プレイヤーはボードから順番に（右から左に）Fibonecciのコードを削除しています。何も削除できなくなった場合、プレーヤーは負けます（ボードが空になり、プレーヤーの番になります）。

プレーヤー（最初の動きをしている）が常に（常に他のプレーヤーの動きから独立して）勝つことができるかどうかを決定するアルゴリズムを作成する方法はありますか？

例：

ボード：1101101

Player1-1番目の動き（01）//可能な動き（01、1、101、01101）

ボード：11011

Player2-2番目の動き（1）//可能な動き（1）

ボード：1101

Player1-3番目の動き（01）//可能な動き（1、01、101）

ボード：11

Player2-4番目の動き（1）//可能な動き（1）

ボード：1

Player1-5番目の動き（1）//可能な動き（1）

ボード：

Player2-6番目の動き（-）//可能な動き（なし）

4

2 に答える 2

1

あなたのシリーズの長さを見ると、私はそれをブルートフォースと言うでしょう....

書くのが難しくなく、すべての動きを追跡する必要があります。

于 2012-11-04T13:17:46.847 に答える
1

最初のボードnの長さ、最初のボードboard[i]のi-番目の記号（左から1から始まるインデックス）、およびインデックスとそれを含むboard[i..j]最初のボードのセグメントとします。ij

左のターンのプレーヤーが勝つことを強制できるi場合は勝ちの長さを呼び、それぞれの可能な移動が他のプレーヤーに勝ちの長さを残す場合は負けの長さを呼びましょう。board[1..i]board[1..i]

0は負けた長さ（移動はまったく不可能）であり、1は勝った長さです（残りのシンボルだけを削除するとすぐに勝ちます）。

それぞれの長さは勝つか負けるかのどちらかです。可能な動きが他のプレーヤーに負けた長さを残す場合、その動きを選択することで勝ちを強制することができます。そうでない場合、定義上、負けた長さです。

勝つことができるかどうか、勝つ戦略と一緒に、負けている-1かどうか（としてマーク）、または勝ちを強制する動きがどうなるかk（C[k]残りのボードの端から取り除くと、対戦相手の長さが失われます。そのようなakは一般的にユニークではなく、誰でも可能です）。

擬似コード（C-ish）：

int moves[n+1];
// initialise all lengths to losing
for(i = 0; i <= n; ++i) {
    moves[i] = -1;
}
moves[1] = board[i]; // win by removing the last symbol
for(i = 2; i <= n; ++i) {
    if (board[i] == 0) {
        // no choice, the only code ending with a 0 is C[0]
        moves[i] = moves[i-1] < 0 ? 0 : -1;
    } else {
        k = 1;
        while(C[k] is_suffix_of board[1..i]) {
            if (moves[i - fib(k)] < 0) {
                // found a winning move
                moves[i] = k;
                break;
             }
             ++k;
        }
        // we either found a winning move and noted it, or leave the position as losing
    }
}

moves[n]最初のプレイヤーが勝利を強制できるかどうか、もしそうなら、その方法を教えてくれます。

純粋なブルートフォースに対する利点は、最初のいくつかの州を除くすべての州が多くの方法で到達可能であるため、多くの再計算を節約できることです。

C[k] is_suffix_of board[1..i]チェックは最もコストのかかる操作です。これがの連結であり、この順序であることに注意することで多少改善できます。C[k+1]したがってC[k-1]、それがのサフィックスであるC[k]ことがわかっている場合は、がのサフィックスであるかどうかをチェックするだけで済みます。C[k]board[1..i]C[k-1]board[1..(i-fib(k))]

于 2012-11-04T15:53:38.837 に答える