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

[0x4F5DA2]

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

背景：

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

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

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

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

问题：

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

大抱歉，这题老早之前去面巨硬时候的题，记忆出了点偏差。还有一个操作是翻转一个硬币（翻转哪一个由 B 决定）。另外上面手滑打了两个三。

再次大抱歉，关于题目中的 20 步，我不太记得具体包不包含查询指令了，给大家填堵了。刚才又做了一下，包含查询的话 20 步以内我现在也做不出来。

具体的思路的是把能够通过旋转和全部翻转的得到相同图案的看作一类，所以一共有四个状态：

1：全正或者全反
2：一正三反或者一反三正
3：两正两反，对角线朝向相同
4：两正两反，对角线朝向不同

当时现场我并没有做出来，回家之后画状态转移图，用的 NFA 转 DFA 的方法硬做出来的。

现在想了一下可以分情况进行讨论：

状态（ 2 ）和（ 4 ）对翻对角是鲁棒的，所以先考虑状态（ 3 ）：翻对角，到状态（ 1 ），解决问题

状态（ 2 ）对于翻行、列和对角是鲁棒的，所以随后考虑状态（ 4 ）：翻一行，到状态（ 1 ）或（ 3 ）

最后解决状态（ 2 ）：翻一个，到状态（ 1 ）或（ 2 ）或（ 3 ）

再再次大抱歉

上一条

最后解决状态（ 2 ）：翻一个，到状态（ 1 ）或（ 2 ）或（ 3 ）

改成

最后解决状态（ 2 ）：翻一个，到状态（ 1 ）或（ 3 ）或（ 4 ）

[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 步就可以

[Raven316]

@0x4F5DA2 楼主快粗来公布答案了

[ryd994]

看来国内微软很难进啊😂
我老板当年就问了一个怎么在 C 里判断 endianess😑

[ziwiwiz]

查询 反转 查询
行 查询 反转 查询
列 查询 反转 查询
行 查询 反转 查询
单转
重复以上
（ 3+4*3 ）* 2 +1-1 = 30

[wshhfy]

我这种水平只能坐等答案了🤣

[cassyfar]

这是图论吧。按照四种状态，全正，全反，一正三反，三正一反，二正二反，二正二反（对角）有 6 个点。然后全正是终点。根据操作连边，是 bi-direction 。求一种解法，10 步内，从任何点开始都能走到全正这个终点。没走一步，可以查询一次。

[alan0liang]

似乎能分类讨论证 #12 的结论，即至少 30 个指令，大概思路是这样：把所有状态分成 front, back, horizontal, vertical, diagonal, odd 这几种状态，front 和 back 统称 all
0. 显然任何指令重复两遍没意义
1. 查询指令如果不与 4 相邻则没意义
2. 4 之后除非直接结束否则只要不跟着查询就没意义
3. 所以「查询 4 查询」必然作为一个整体出现(除了最后)，把它叫 A
4. 1/2 之后如果不跟着 A 则没意义
5. odd 状态和其他没什么关系，只能通过 5 转化成 ahvd 之一，而 ahvd 转换成 odd 就更没意义了
6. 所以 #9 就是最优解
中间有好多跳步，但是写出来太长了……
期待打脸

[freelancher]

这个是一个算法题。

四个硬币是 0.5 机率有正面或者反面。全正是 1/8 。全反是 1/8.

每进行翻转一次。查询一次。

第一步，先查询全状态。运气好就直接 OK 了。

然后用排除法的思路。翻一个对角线。查询，这个应该让数学的来答会好点。应该是有解法的。

[tsaohai]

哎哟卧槽 这题我还真被面过🤣🤣