八数码难题有无解的判断

上传人:cn****1 文档编号:489481166 上传时间:2024-02-01 格式:DOC 页数:2 大小:20KB
返回 下载 相关 举报
八数码难题有无解的判断_第1页
第1页 / 共2页
八数码难题有无解的判断_第2页
第2页 / 共2页
亲,该文档总共2页,全部预览完了,如果喜欢就下载吧!
资源描述

《八数码难题有无解的判断》由会员分享,可在线阅读,更多相关《八数码难题有无解的判断(2页珍藏版)》请在金锄头文库上搜索。

1、八数码难题有无解的判断我知道什么样的情况有解 , 什么情况没解 . 函数 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

2、 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(a

3、6),f(a7),f(a8)讨论:有 4 种情况 1) a6a7, a6a8f(a8) 减小 1f(a7) 减小 1f(a6) 不变所以f(a8)+f(a7)+f(a1)奇偶性不变.2) a6a8f(a8) 不变f(a7) 减小 1f(a6) 增大 1所以f(a8)+f(a7)+f(a1 )奇偶性不变.3) a6a7, a6a8f(a8) 不变f(a7) 不变f(a6) 增大 2所以f(a8)+f(a7)+f(a1)奇偶性不变.3) a6a7, 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| 成 功.

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 办公文档 > 活动策划

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号