分享另一道巨硬家面试题（中等难度，非编程）

[0x4F5DA2]

看到有人分享巨硬家面试题，我也来分享一个

背景：

这是一个两个人进行的游戏，后面称两人为 A 和 B 。

有四枚硬币，摆成一个正方形，初始状态正反面随机。A 看不到硬币的状态，B 能看到硬币状态并进行操作。A 能向 B 发出四种操作指令和一种查询指令：

操作指令： 1. 将一行硬币翻转 180 度（翻转哪一行由 B 决定） 2. 将一列硬币翻转 180 度（翻转哪一列由 B 决定） 3. 将一个对角线的硬币翻转 180 度（翻转哪一对角线由 B 决定） 3. 将所有硬币翻转 180 度

查询指令： 1. 所有硬币是否处于全是正面的状态（ B 回答是或者否）

问题：

假如你是 A，给出一个长度小于 20 的指令序列，使得所有硬币均为正面。

[undeflife]

有点像在文曲星上玩的猜数字.

[Raven316]

我是不是理解错了，假如一开始 1 个正面，3 个反面，那么无论怎么翻不都是 1 个或者 3 个正面吗？

[0x4F5DA2]

@undeflife 有点像吧，但是那个没有这个难（

[gccdchen]

@Raven316 我也是这么想,反面数量是单数的话,每次指令都是双数..应该是做不了.
但是如果要考虑题目是双数的情况呢?

[0x4F5DA2]

@Raven316 啊，抱歉，老早之前去面巨硬的时候的题，记忆出了点偏差。还有一个操作是翻转一个硬币（翻转哪一个由 B 决定）

[0x4F5DA2]

@gccdchen 抱歉记忆出了偏差，漏了一个操作。具体见五楼

[hejw19970413]

应该三种情况 如果 得一种情况走完需要 还原 最初始状态，然后进行回溯。也可以理解成深度优先遍历

[widewing]

四种情况：a.全正，b.全反，c.两正两反，d.一正三反。
1.首先查询，验证 a
2.全翻转，查询，验证 b
3.从左上分别按行，列，对角翻转并查询，验证 c
4.随机翻转后重复 3 验证 d

[Raven316]

目前只能一个 31 步的，首先 B 是随机翻转，而翻转 1 行等于翻转 2 行+全翻转，所以翻转行后必须：确认+全翻转+确认。列和对角线类似。

而必须先确定是单数还是双数。所以先假定为双数。

如果为双数：

分为 4 种情况：（ 1 ）全翻转或者不翻就行（ 2 ）翻行（ 3 ）翻列（ 4 ）翻对角线

第一步确认（ 1 ）：
执行步骤：1 确认 2 全翻转 3 确认
然后确认（ 2 ）：
4 翻行 5 确认 6 全翻转 7 确认
然后确认（ 3 ）：
因为已经翻了行，所以这时一开始的对角线变成了列，列变成了对角线
8 翻列 9 确认 10 全翻转 11 确认
这时如果是双数，那么肯定是对角线
12 翻对角线 13 确认 14 全翻转 15 确认

这是已经确定是单数正面
16 翻单个
接下来必定是双数，所以套用上面 15 步，总共 31 步一定是全正面。。。

能力所限

[widewing]

@widewing 修正：
d.一正三反或三正一反
4. 随机翻转后重复 123 验证 d

[Raven316]

@Raven316 所以如果在 20 步以内，双数翻转到全正必须在 9 步或者 9 步以内

[threebr]

硬币有 2^4=16 种状态，而 A 只能确认是否处于 1 种状态，所以 A 只能枚举各种不同的状态并一一确认，转换不同的状态至少需要 1 个操作指令，如果查询指令也算 1 个长度的话，考虑最坏情况至少需要 31 个指令（ 16 次查询和 15 次操作）。

不知道我的思路有什么问题

[alan0liang]

@Raven316 和 #9 思路一样，能优化到 24 步：删掉 #9 中 567，最后一步不用确认一定是全正面，一共删掉 7 步，31-7=24

[threebr]

@Raven316 哈哈哈哈哈你找出了一个 31 步的方法，我推断指令应该大于等于 31，那答案不就是 31 了吗

[alan0liang]

@threebr 参考 #13 的优化，不一定需要挨个枚举所有状态，可以想办法合并之后一次确认两种情况甚至多种情况。

[Raven316]

@threebr 思路很牛，我也觉得好像做不到

[CrazyEight]

如果是全反或全正就赢那还好想一些，全正的情况太多了

[alan0liang]

不对😂，#13 我说的是错的，只有最后一步可以删掉

[Raven316]

@Raven316 错了 12 步改成翻行

[threebr]

@alan0liang 没懂为什么可以删掉 #9 567，不过最后一步的确不用确认，30 步就可以