数学研发论坛

 找回密码
 欢迎注册
楼主: aimisiyou

[讨论] 最少取反几次

[复制链接]
 楼主| 发表于 2020-9-12 07:41:12 | 显示全部楼层
本帖最后由 aimisiyou 于 2020-9-12 07:48 编辑
.·.·. 发表于 2020-9-11 00:45
考虑1x2只有一盏灯亮的情形,你的“是否先要判断初始状态能否满足达到全部熄灭的要求”这一问题是不证自 ...


简单看成递归,即把第一行全部转为熄灭状态(即在原第一行亮灯的下方按钮按一下,可保证第一行灯全熄灭),这样递归下去就剩最后两行有亮有熄情况。
784.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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}
089.png
809.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-9-12 17:03:41 | 显示全部楼层
本帖最后由 aimisiyou 于 2020-9-12 18:33 编辑

这取模的方程怎么求?人工分析好繁琐啊,能否编程求解?
808.png
678.png

点评

看不懂C代码。算法原理就是高斯消元法求解所有解,是吗?  发表于 2020-9-13 09:17
https://bbs.emath.ac.cn/forum.php?mod=redirect&goto=findpost&ptid=5422&pid=52669&fromuid=20 有C代码  发表于 2020-9-13 08:22
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-9-12 18:43:34 | 显示全部楼层
4*4初始全亮,结果如图,最少是4步。看来右边的解(10步)不是最少步数。
123.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-9-12 21:41:08 | 显示全部楼层
n*m情况下复杂度为O(2^min{n,m})
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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 意义下的方程组
跟上面的算法差不多
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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
33.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-9-12 23:11:54 | 显示全部楼层
aimisiyou 发表于 2020-9-12 22:41
1、与其说是解方程组,还不如说是给定初始值,得出推理结果,然后复核推理结果是否正确。
2、我考虑的是 ...

类似问题,如果只是求解,那么解方程组是最优算法(能确保在多项式时间判断题目是否有解)
但如果要求记录边数,只能给定初始值,得出推理结果
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-9-12 23:15:02 | 显示全部楼层
本帖最后由 aimisiyou 于 2020-9-12 23:26 编辑
.·.·. 发表于 2020-9-12 23:11
类似问题,如果只是求解,那么解方程组是最优算法(能确保在多项式时间判断题目是否有解)
但如果要求记 ...


解不唯一就很麻烦了。为了省去麻烦的奇偶判定,我直接枚举顶边按下次数的所有状态(2^min{n,m}),得出最后一行的推理结果,然后复核最后一行的推理结果是否正确。若推理结果正确,则顶边的状态即为其中一个解。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2020-10-19 23:48 , Processed in 0.068660 second(s), 21 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表