0

有一个这样定义的斐波那契代码：

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

有一个使用这种编码系统的游戏，还有一个棋盘（例如 1101101）。在这个游戏中，玩家轮流（从右到左）将斐波内奇的代码移出棋盘。玩家输了，如果他不能再移除任何东西（棋盘变空，现在轮到玩家了）。

有没有办法制定一个算法，决定一个玩家（即做第一步）是否总是（总是意味着独立于另一个玩家的移动网络）获胜。

示例：

板：1101101

Player1 - 1st move (01) // 可能的移动 (01, 1, 101, 01101)

董事会：11011

Player2 - 2nd move (1) // 可能的移动 (1)

董事会：1101

Player1 - 3rd move (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]初始棋盘在索引i和j包含值之间的段。

i如果轮到的玩家board[1..i]可以强制获胜，我们称其为获胜长度，如果每个可能的移动都board[1..i]为其他玩家留下获胜长度，则称为失败长度。

0 是失败的长度（根本不可能移动），1 是获胜的长度（删除唯一剩余的符号立即获胜）。

每个长度要么是赢要么是输：如果任何可能的移动为其他玩家留下了一个失败的长度，我们可以通过选择该移动来强制获胜，否则根据定义它是一个失败的长度。

我们可以找出我们是否可以强制获胜，如果是这种情况，我们可以通过记录每个长度是否失败（标记为-1）或获胜策略将是什么（一个非负整数k，例如从剩余棋盘的末端移除C[k]会为对手留下损失的长度；这k通常不是唯一的，任何都可以）。

伪代码（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]告诉我们第一个玩家是否可以强制获胜，如果可以，如何。

与纯蛮力相比的优势在于它节省了大量的重新计算，因为除了前几个状态之外的所有状态都可以通过多种方式到达。

检查是最昂贵的操作，通过注意它是and的连接顺序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 回答