八数码难题有无解的判断八数码难题有无解的判断
八数码难题有无解的判断 我知道什么样的情况有解,什么情况没解.
函数f(s)表示s前比s小的数字的数目.
例如:
|1 3 4|
|2 8 6|
|5 7 |
表示成:
|1 3 4|2 8 6|5 7 X| 则f(7)=6, f(5)=4,f(6)=4,f(8)=4,f(2)=1,
f(4)=2,f(3)=1,f(1)=0
当f(a8)+f(a7)+……+f(a1)为偶数时才能重排成
所以嘛,上面那个有解的.
下面我就来证明一下.
设任意一种情况:
|a1 a2 a3|
...
八数码难题有无解的判断
八数码难题有无解的判断 我知道什么样的情况有解,什么情况没解.
f(s)表示s前比s小的数字的数目.
例如:
|1 3 4|
|2 8 6|
|5 7 |
表示成:
|1 3 4|2 8 6|5 7 X| 则f(7)=6, f(5)=4,f(6)=4,f(8)=4,f(2)=1,
f(4)=2,f(3)=1,f(1)=0
当f(a8)+f(a7)+……+f(a1)为偶数时才能重排成
所以嘛,上面那个有解的.
下面我就来证明一下.
设任意一种情况:
|a1 a2 a3|
|a4 a5 a6|
|a7 a8 X | (X表示空格)
将之放在一行上: |a1 a2 a3|a4 a5 a6|a7 a8 X |
数字的上下移动可以相对于是空格的上下移动.
所以我们只要讨论X的移动了:
假设函数f(s)表示s前比s小的数字的数目.
例如:|1 3 4|2 8 6|5 7 X| 则f(7)=6, f(5)=4, f(8)=4,……
对于X在同一行中的移动,f(a8)+f(a7)+……+f(a1)大小不变(*1) 如:|a1 a2 a3|a4 a5 a6|a7 a8 X |=>|a1 a2 a3|a4 a5 a6|a7 X a8|
对于X在列中移动是,我们不妨设X与a6对换(即a6下移一格) 则数列变为|a1 a2 a3|a4 a5 X|a7 a8 a6|,可能引起变化的f(s)只有f(a6),f(a7),f(a8)
讨论:有4种情况1) a6
a8
f(a8) 不变
f(a7) 减小1
f(a6) 增大1
所以f(a8)+f(a7)+……+f(a1)奇偶性不变.
3) a6>a7, a6>a8
f(a8) 不变
f(a7) 不变
f(a6) 增大2
所以f(a8)+f(a7)+……+f(a1)奇偶性不变.
3) a6>a7, a6|a1 a2 X|a4 a5 a3|a7
a8 a6|
则同样,对可能变化的f(a3),f(a4),f(a5)讨论,情况一上面完全一样。
其它情况都如此:
如:|a1 X a3|a4 a5 a6|a7 a8 a2|=>|a1 a5 a3|a4 X a6|a7 a8 a2|
就f(a3),f(a4),f(a5)变化.
结论:因为对于|1 2 3|4 5 6| 7 8 X|, f(8)+f(7)+……+f(1)=28, 是偶数, 所以当f(a8)+f(a7)+……+f(a1)为偶数时才能重排成|1 2 3|4 5 6| 7 8 X|成功.
本文档为【八数码难题有无解的判断】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。