这是一个创建于 1554 天前的主题，其中的信息可能已经有所发展或是发生改变。
看到有人分享巨硬家面试题，我也来分享一个
背景：
这是一个两个人进行的游戏，后面称两人为 A 和 B 。
有四枚硬币，摆成一个正方形，初始状态正反面随机。A 看不到硬币的状态，B 能看到硬币状态并进行操作。A 能向 B 发出四种操作指令和一种查询指令：
操作指令： 1. 将一行硬币翻转 180 度（翻转哪一行由 B 决定） 2. 将一列硬币翻转 180 度（翻转哪一列由 B 决定） 3. 将一个对角线的硬币翻转 180 度（翻转哪一对角线由 B 决定） 3. 将所有硬币翻转 180 度
查询指令： 1. 所有硬币是否处于全是正面的状态（ B 回答是或者否）
问题：
假如你是 A，给出一个长度小于 20 的指令序列，使得所有硬币均为正面。
第 1 条附言 · 2020-08-27 17:23:38 +08:00
大抱歉，这题老早之前去面巨硬时候的题，记忆出了点偏差。还有一个操作是翻转一个硬币（翻转哪一个由 B 决定）。另外上面手滑打了两个三。
第 2 条附言 · 2020-08-27 18:21:58 +08:00
再次大抱歉，关于题目中的 20 步，我不太记得具体包不包含查询指令了，给大家填堵了。刚才又做了一下，包含查询的话 20 步以内我现在也做不出来。
具体的思路的是把能够通过旋转和全部翻转的得到相同图案的看作一类，所以一共有四个状态：
1：全正或者全反
2：一正三反或者一反三正
3：两正两反，对角线朝向相同
4：两正两反，对角线朝向不同
当时现场我并没有做出来，回家之后画状态转移图，用的 NFA 转 DFA 的方法硬做出来的。
现在想了一下可以分情况进行讨论：
状态（ 2 ）和（ 4 ）对翻对角是鲁棒的，所以先考虑状态（ 3 ）：翻对角，到状态（ 1 ），解决问题
状态（ 2 ）对于翻行、列和对角是鲁棒的，所以随后考虑状态（ 4 ）：翻一行，到状态（ 1 ）或（ 3 ）
最后解决状态（ 2 ）：翻一个，到状态（ 1 ）或（ 2 ）或（ 3 ）
具体的思路的是把能够通过旋转和全部翻转的得到相同图案的看作一类，所以一共有四个状态：
1：全正或者全反
2：一正三反或者一反三正
3：两正两反，对角线朝向相同
4：两正两反，对角线朝向不同
当时现场我并没有做出来，回家之后画状态转移图，用的 NFA 转 DFA 的方法硬做出来的。
现在想了一下可以分情况进行讨论：
状态（ 2 ）和（ 4 ）对翻对角是鲁棒的，所以先考虑状态（ 3 ）：翻对角，到状态（ 1 ），解决问题
状态（ 2 ）对于翻行、列和对角是鲁棒的，所以随后考虑状态（ 4 ）：翻一行，到状态（ 1 ）或（ 3 ）
最后解决状态（ 2 ）：翻一个，到状态（ 1 ）或（ 2 ）或（ 3 ）
第 3 条附言 · 2020-08-27 18:26:40 +08:00
再再次大抱歉
上一条
最后解决状态（ 2 ）：翻一个，到状态（ 1 ）或（ 2 ）或（ 3 ）
改成
最后解决状态（ 2 ）：翻一个，到状态（ 1 ）或（ 3 ）或（ 4 ）
上一条
最后解决状态（ 2 ）：翻一个，到状态（ 1 ）或（ 2 ）或（ 3 ）
改成
最后解决状态（ 2 ）：翻一个，到状态（ 1 ）或（ 3 ）或（ 4 ）
 |
1
undeflife 2020-08-27 16:39:15 +08:00
有点像在文曲星上玩的猜数字.
|
 |
2
Raven316 2020-08-27 16:43:07 +08:00
我是不是理解错了，假如一开始 1 个正面，3 个反面，那么无论怎么翻不都是 1 个或者 3 个正面吗？
|
 |
5
0x4F5DA2 OP @Raven316 啊，抱歉，老早之前去面巨硬的时候的题，记忆出了点偏差。还有一个操作是翻转一个硬币（翻转哪一个由 B 决定）
|
 |
7
hejw19970413 2020-08-27 16:54:19 +08:00
应该三种情况 如果 得一种情况走完需要 还原 最初始状态，然后进行回溯。也可以理解成深度优先遍历
|
 |
8
widewing 2020-08-27 17:06:31 +08:00 via Android
四种情况：a.全正，b.全反，c.两正两反，d.一正三反。
1.首先查询，验证 a 2.全翻转，查询，验证 b 3.从左上分别按行，列，对角翻转并查询，验证 c 4.随机翻转后重复 3 验证 d |
|
9
Raven316 2020-08-27 17:08:45 +08:00
目前只能一个 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 步一定是全正面。。。 能力所限 |
 |
12
threebr 2020-08-27 17:11:46 +08:00  1
硬币有 2^4=16 种状态，而 A 只能确认是否处于 1 种状态，所以 A 只能枚举各种不同的状态并一一确认，转换不同的状态至少需要 1 个操作指令，如果查询指令也算 1 个长度的话，考虑最坏情况至少需要 31 个指令（ 16 次查询和 15 次操作）。
不知道我的思路有什么问题 |
 |
13
alan0liang 2020-08-27 17:14:28 +08:00 via Android
@Raven316 和 #9 思路一样，能优化到 24 步：删掉 #9 中 567，最后一步不用确认一定是全正面，一共删掉 7 步，31-7=24
|
|
15
alan0liang 2020-08-27 17:17:21 +08:00 via Android
@threebr 参考 #13 的优化，不一定需要挨个枚举所有状态，可以想办法合并之后一次确认两种情况甚至多种情况。
|
 |
17
CrazyEight 2020-08-27 17:20:21 +08:00
如果是全反或全正就赢那还好想一些，全正的情况太多了
|
|
18
alan0liang 2020-08-27 17:20:46 +08:00 via Android
不对😂，#13 我说的是错的，只有最后一步可以删掉
|
|
20
threebr 2020-08-27 17:22:40 +08:00
@alan0liang 没懂为什么可以删掉 #9 567，不过最后一步的确不用确认，30 步就可以
|
 |
22
ryd994 2020-08-27 17:57:22 +08:00 via Android
看来国内微软很难进啊😂
我老板当年就问了一个怎么在 C 里判断 endianess😑 |
 |
23
ziwiwiz 2020-08-27 18:00:33 +08:00
查询 反转 查询
行 查询 反转 查询 列 查询 反转 查询 行 查询 反转 查询 单转 重复以上 （ 3+4*3 ）* 2 +1-1 = 30 |
 |
24
wshhfy 2020-08-27 18:12:05 +08:00
我这种水平只能坐等答案了🤣
|
 |
25
cassyfar 2020-08-27 18:45:30 +08:00
这是图论吧。按照四种状态，全正，全反，一正三反，三正一反，二正二反，二正二反（对角）有 6 个点。然后全正是终点。根据操作连边，是 bi-direction 。求一种解法，10 步内，从任何点开始都能走到全正这个终点。没走一步，可以查询一次。
|
|
26
alan0liang 2020-08-27 19:55:36 +08:00 via Android
似乎能分类讨论证 #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 就是最优解 中间有好多跳步，但是写出来太长了…… 期待打脸 |
 |
27
freelancher 2020-08-28 03:45:37 +08:00
这个是一个算法题。
四个硬币是 0.5 机率有正面或者反面。全正是 1/8 。全反是 1/8. 每进行翻转一次。查询一次。 第一步，先查询全状态。运气好就直接 OK 了。 然后用排除法的思路。翻一个对角线。查询，这个应该让数学的来答会好点。应该是有解法的。 |
 |
28
tsaohai 2020-08-28 07:45:46 +08:00 via iPhone
哎哟卧槽 这题我还真被面过🤣🤣
|
Select Language