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

[0x4F5DA2]

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

背景：

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

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

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

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

问题：

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

[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]

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