最少取反几次

aimisiyou · 发表于 2020-9-10 23:07:14

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

本帖最后由 aimisiyou 于 2020-9-10 23:08 编辑

题目如图。若矩阵为
1011010
0110101
0010111
1010011
最少几次操作使得都变成0?

aimisiyou · 发表于 2020-9-10 23:16:56

是否先要判断初始状态能否满足达到全部熄灭的要求？还是说对于任意初始状态，经过有限次操作，都能使得所有灯都能熄灭？

.·.·. · 发表于 2020-9-11 00:45:29

aimisiyou 发表于 2020-9-10 23:16
是否先要判断初始状态能否满足达到全部熄灭的要求？还是说对于任意初始状态，经过有限次操作，都能使得所有 ...

考虑1x2只有一盏灯亮的情形，你的“是否先要判断初始状态能否满足达到全部熄灭的要求”这一问题是不证自明的。
这题最难的地方就是遍历第一行的全部可能状态然后对其余行解方程组
解方程组的意思是，如果我们知道顶部所在行不需要进行任何操作，那么顶部亮灯的列就是我们需要操作的下一行开关所在列。
这样搜起来，在n<16的情况下最多搜65536种可能（或许还可以化简但我懒得化了，反正够快）

aimisiyou · 发表于 2020-9-11 00:54:36

本帖最后由 aimisiyou 于 2020-9-11 01:10 编辑

.·.·. 发表于 2020-9-11 00:45
考虑1x2只有一盏灯亮的情形，你的“是否先要判断初始状态能否满足达到全部熄灭的要求”这一问题是不证自 ...

1*2的情况太明显了，复杂一点怎么判断呢？如3*3只有左上角一灯是亮的初始状态，好像也是不能满足的。有没有通用的判断法则？先来简单的，m*n只有左上角一灯是亮的，m、n满足什么条件使得初始状态经变换可以全部为0。（至少1*1、1*3、2*2是满足的。）

mathe · 发表于 2020-9-11 19:22:12

这是关灯问题，可转化为解方程https://blog.emath.ac.cn/guandengyouxihesaoleiwenti/

mathe · 发表于 2020-9-11 20:29:40

根据 https://oeis.org/A159257
3×3总是有解的

aimisiyou · 发表于 2020-9-11 21:46:10

本帖最后由 aimisiyou 于 2020-9-11 22:17 编辑

mathe 发表于 2020-9-11 20:29
根据 https://oeis.org/A159257
3×3总是有解的

那你能给出3*3，初始状态只有左上角一灯为亮，如何达到所有灯都灭么？

aimisiyou · 发表于 2020-9-11 22:17:29

3*3,第一行第1、2灯亮，可以到达目标状态（全熄）。

aimisiyou · 发表于 2020-9-11 22:29:27

本帖最后由 aimisiyou 于 2020-9-11 22:45 编辑

aimisiyou 发表于 2020-9-11 21:46
那你能给出3*3，初始状态只有左上角一灯为亮，如何达到所有灯都灭么？

确实是可以的。如图，最后一图可以看成332图顺时针旋转90度的状态。

最少5步操作。

aimisiyou · 发表于 2020-9-11 22:46:48

只要找出任意一个解，就能得到最少步数。

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 最少取反几次

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

点评

点评