Java教程

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

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

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

(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,需要明确上述步骤中其它的指令选择不会有更优的情形即可。严格证明难度不大,比较琐碎,这里略过了。

 

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