最少取反几次

aimisiyou · 发表于 2020-9-12 07:41:12

本帖最后由 aimisiyou 于 2020-9-12 07:48 编辑

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

简单看成递归，即把第一行全部转为熄灭状态（即在原第一行亮灯的下方按钮按一下，可保证第一行灯全熄灭），这样递归下去就剩最后两行有亮有熄情况。

aimisiyou · 发表于 2020-9-12 16:59:41

可得
mod(n1+n2+n4，2)=1
mod(n1+n2+n3+n5，2)=0
mod(n2+n3+n6，2)=0
mod(n1+n4+n5+n7，2)=0
mod(n2+n4+n5+n6+n8，2)=0
mod(n3+n5+n6+n9，2)=0
mod(n4+n7+n8，2)=0
mod(n5+n7+n8+n9，2)=0
mod(n6+n8+n9，2)=0

其中，ni={0,1}

aimisiyou · 发表于 2020-9-12 17:03:41

本帖最后由 aimisiyou 于 2020-9-12 18:33 编辑

这取模的方程怎么求？人工分析好繁琐啊，能否编程求解？

aimisiyou · 发表于 2020-9-12 18:43:34

4*4初始全亮，结果如图，最少是4步。看来右边的解（10步）不是最少步数。

aimisiyou · 发表于 2020-9-12 21:41:08

n*m情况下复杂度为O（2^min{n,m}）

aimisiyou · 发表于 2020-9-12 21:44:51

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

如何求解方程组？

.·.·. · 发表于 2020-9-12 22:28:39

aimisiyou 发表于 2020-9-12 21:44
如何求解方程组？

先确定第一行灯的亮与灭
然后剩下的灯亮与灯灭可以直接推出

解方程组的话就是解一个mod2 意义下的方程组
跟上面的算法差不多

aimisiyou · 发表于 2020-9-12 22:41:45

本帖最后由 aimisiyou 于 2020-9-13 07:17 编辑

.·.·. 发表于 2020-9-12 22:28
先确定第一行灯的亮与灭
然后剩下的灯亮与灯灭可以直接推出

1、与其说是解方程组，还不如说是给定初始值，得出推理结果，然后复核推理结果是否正确。
2、我考虑的是以min{n,m}为顶边，这样可减少运算量。
如将矩阵
1011010
0110101
0010111
1010011
旋转90度，得到矩阵
1001
0010
1111
0001
0110
1101
1110

.·.·. · 发表于 2020-9-12 23:11:54

aimisiyou 发表于 2020-9-12 22:41
1、与其说是解方程组，还不如说是给定初始值，得出推理结果，然后复核推理结果是否正确。
2、我考虑的是 ...

类似问题，如果只是求解，那么解方程组是最优算法（能确保在多项式时间判断题目是否有解）
但如果要求记录边数，只能给定初始值，得出推理结果

aimisiyou · 发表于 2020-9-12 23:15:02

本帖最后由 aimisiyou 于 2020-9-12 23:26 编辑

.·.·. 发表于 2020-9-12 23:11
类似问题，如果只是求解，那么解方程组是最优算法（能确保在多项式时间判断题目是否有解）
但如果要求记 ...

解不唯一就很麻烦了。为了省去麻烦的奇偶判定，我直接枚举顶边按下次数的所有状态（2^min{n,m}）,得出最后一行的推理结果，然后复核最后一行的推理结果是否正确。若推理结果正确，则顶边的状态即为其中一个解。

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

[讨论] 最少取反几次

点评