一个田字格转盘游戏的问题分析

本文主要是介绍一个田字格转盘游戏的问题分析，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

甲乙两人玩一个田字格转盘游戏，规则如下：

(1). 游戏开局时，由甲在转盘的四个格子里各填上一个数字（仅限 0 或 1）；

(2). 乙背对转盘发出对转盘中的数字进行更改的指令，允许的指令有：

a. 对指定的一格或两格独立填值；

b. 对指定的一格或两格里的数字做翻转操作，即 0 变 1，1 变 0。

(3). 甲每执行完一次乙的指令，检查四个格里数字是否为全 0 或全 1，是，则游戏结束；否则，甲对转盘做若干次 90 度旋转后等待乙的下一个指令。

问：乙有没有可行的方案来确保 k 次指令内结束游戏？若有，k 的最小值是多少？

分析与解：这个问题等价于 2x2 方阵变换问题。由于乙看不到转盘中的数字，四格的数字情况可表示为

xx
xx

这里 x 表示不确定是 0 还是 1 的情形。为了可以掌控数字分布情况，易知一开始一定要采用 a 类指令，且还有旋转带来的干扰，对两个数字置值会比对一个数字置值效果更好。比如：

指令一：把对角的两个数字置为 1

即初始方阵变换为

1x  或  x1
x1       1x

两处 x 若全为1，则游戏结束。否则，经若干次旋转后，也还是这两种情形。

指令二：把同一行（或列）的两个数字置为 1

以第一行为例，方阵会变换为

11  或  11
x1        1x

此时，只有一格为 x，若 x = 1，游戏结束。若 x = 0，经旋转干扰后，方阵会是以下四种情形之一：

11  或  01  或  10  或  11
01       11        11        10

不难发现，上述两次指令可以交换顺序，效果是一样的，即若不出现全 1，则必然是三个 1 和 一个 0 的情形。

指令三：对任一格的数字做翻转操作

以左上角的数字为例，翻转后方阵会变换为以下四种情形之一：

01  或  11  或  00  或  01
01        11       11        10

其中第二种为全 1，游戏结束。其余三种再经旋转后，方阵会是以下六种情形之一：

01  或  00  或  10  或  11  或  01  或  10
01        11       10        00       10        01

这六种都是 0 和 1 各两个的情形。其中，前四种可归为 A 类（相同的数字相邻），后两种可归为 B 类（相同的数字互为对角）。

指令四：把对角的两个数字做翻转操作

以翻转左上和右下两个数字为例，翻转后方阵会变换为以下六种情形之一：

11  或  10  或  00  或  01  或  11  或  00
00       10        11        01        11       00

后两种已经是全 1 或全 0，游戏结束。前四种经旋转后，还是这四种，即

11  或  10  或  00  或  01
00       10        11        01

指令五：把同一行（或列）的两个数字做翻转操作

以第一行为例，翻转后方阵会变换为以下四种情形之一：

00  或  01  或  11  或  10
00       10         11       01

第一种和第三种已经是全 0 或全 1，游戏结束。剩余两种即为上述的 B 类情形，经旋转后还是 B 类，即：

01  或  10
10        01

指令六：把对角的两个数字做翻转操作

翻转后方阵会变换为全 1 或全 0 方阵，游戏结束。

以上便是一个可行方案，且有 k ≤ 6。为进一步说明 k = 6，需要明确上述步骤中其它的指令选择不会有更优的情形即可。严格证明难度不大，比较琐碎，这里略过了。

这篇关于一个田字格转盘游戏的问题分析的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！