拼图游戏的数学原理

简介: 一、线性代数基础知识 1、逆序的定义:         逆序是一个与排列相关的概念。         由自然数1,2…,n组成的不重复的每一种有确定次序的排列,称为一个n级排列(简称为排列);或者一般的,n个互不同元素排成一列称为“一个n级排列”。例如,1234和4312都是4级排列,而24315是一个5级排列。         在一个n级排列中,如果一对数的前后位置与大小顺序相反

一、线性代数基础知识

1、逆序的定义:

        逆序是一个与排列相关的概念。
        由自然数1,2…,n组成的不重复的每一种有确定次序的排列,称为一个n级排列(简称为排列);或者一般的,n个互不同元素排成一列称为“一个n级排列”。例如,1234和4312都是4级排列,而24315是一个5级排列。
        在一个n级排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个“逆序”。

        一个排列中逆序的总数就称为这个排列的逆序数

        逆序数为偶数的排列称为偶排列;逆序数为奇数的排列称为奇排列

        如2431中,21,43,41,31是逆序,逆序数是4,为偶排列

         再来一个定理:交换一个排列中的两个数,则排列的奇偶性发生改变

二、拼图的数学定义

       在m*n*p(m,n>2,p>=1)的方块区域里,所有的方格两两不同,其中有一个特殊的方格,称为空穴,任何与之有邻面(二维时只须有邻边)的方块均可与之互换位置(一次这样的位置互换称为一次操作,也称为空穴的一次移动)。刚开始时随机产生杂乱的排列顺序,要求经过一系列操作后形成要求的排列顺序(目标排列)。

       其实,拼图问题可以转化为这么一个问题:“任意给一个数字矩阵,能否证明:经过无限次的交换,一定能到达目标矩阵或者经过无限的交换也不能实现目标矩阵?”。

三、定理

定理一:

         图形A与图形B等价的充要条件图形A的排列的逆序数加上0元素行号和列号的奇偶性等于图形B的排列的逆序数加上0元素行号和列号的奇偶性。为方便表述,把图形排列的逆序数加上0元素行号和列号的奇偶性称为图形的奇偶性。

定理二:

        对于任意 m* n 的情况,任意两个空穴在同一个位置且奇偶性相同的排列可以通过空穴移动相互转化。

定理三、

        对源状态A与目标状态B进行规范化,使得两矩阵的元素0(此处的元素0就是空穴)的位置相同;记为新的源状态A'与目标状态B';

        若A'与B'的逆序对的奇偶性相同(即A'与B1的逆序对的奇偶性相同),则A'必定可能转化为B',即A可以转化到B;

        若A'与B'的逆序对的奇偶性不同(即A'与B2的逆序对的奇偶性相同),则A'必定不可能转化为B',即A不可以转化到B;

小结:

        其实:以上三个定理或者说是结论,说的都是一个事,只是角度不同,三个定理的证明与叙述见下面的链接。

定理一的叙述及证明

定理二的叙述及证明

定理三的叙述及证明

 

 


目录
相关文章
|
网络协议 安全 网络安全
WireGuard 系列文章(六):Netmaker 安装
WireGuard 系列文章(六):Netmaker 安装
|
算法
10分钟小白都可以看懂的光度立体法以及运用到项目
10分钟小白都可以看懂的光度立体法以及运用到项目
1108 0
10分钟小白都可以看懂的光度立体法以及运用到项目
|
6月前
|
JavaScript 前端开发 程序员
甚至用不了五分钟就能学会vscode插件开发
本文介绍了VSCode插件的开发流程,从创建项目到最终发布。首先通过安装`yo`和`generator-code`脚手架工具初始化项目,选择JavaScript语言配置基础信息。接着,在`extension.js`中实现业务逻辑,例如将中文“变量”替换为“var”。通过F5进入调试模式验证功能。完成后使用`vsce`工具进行打包,解决可能遇到的版本不兼容或README文档问题。最后生成`.vsix`文件,可通过VSCode的“从VSIX安装”加载插件,实现开发闭环。进一步可将插件发布至官方市场供更多开发者使用。
|
运维 监控 关系型数据库
运维实战:Windows服务挂掉了怎么办,通过Bat脚本实现自动重启
本文介绍了如何使用Bat脚本自动监控并重启Windows服务器上的挂掉服务,例如MySQL,以避免在假期等情况下需要紧急处理问题。首先,创建一个Bat脚本,设定每小时检查一次服务状态,如果服务停止则自动重启。脚本内容包括检查服务是否运行并根据状态执行相应操作。同时,脚本中包含了确保以管理员权限运行的代码。 脚本需设置为ANSI编码以防止乱码。推荐将Bat脚本封装为Windows服务以保证稳定运行,提供了使用NSSM工具、Windows服务程序和开源的Java工具winsw将批处理脚本转化为服务的方法。这些方法可以确保服务在后台可靠运行,即使在服务意外停止时也能自动恢复。
|
12月前
|
安全 网络协议 数据安全/隐私保护
访问控制(ACL)原理详解
访问控制(ACL)原理详解
616 0
访问控制(ACL)原理详解
|
网络协议 Linux iOS开发
《熬夜整理》保姆级系列教程-玩转Wireshark抓包神器教程(2)-Wireshark在Windows系统上安装部署
【2月更文挑战第2天】《熬夜整理》保姆级系列教程-玩转Wireshark抓包神器教程(2)-Wireshark在Windows系统上安装部署
336 4
|
机器学习/深度学习 并行计算 计算机视觉
CUDA:王者之巅——探究CUDA为何能成为并行计算的佼佼者
本文探讨了CUDA在并行计算领域的崛起及其成为佼佼者的原因,详细介绍了CUDA的技术背景、架构原理及在深度学习、图像处理等领域的应用案例,展示了其显著的性能优势与优化方法,并展望了CUDA在未来计算技术发展中的潜力与方向。
|
12月前
|
移动开发 前端开发 JavaScript
vue-router学习一:什么是路由,路由分类,路由安装,路由使用,路由默认路径,history模式,默认的linkActiveClass属性,路由代码跳转
这篇文章是关于Vue.js官方路由管理器vue-router的详细介绍,包括路由的基本概念、分类、安装、使用以及在单页面应用中的路由模式和跳转方法。
790 0
vue-router学习一:什么是路由,路由分类,路由安装,路由使用,路由默认路径,history模式,默认的linkActiveClass属性,路由代码跳转
|
调度 开发者 UED
Kotlin 中的协程是什么?
【8月更文挑战第31天】
1253 0
|
人工智能 API C#
动手学Avalonia:基于SemanticKernel与硅基流动构建AI聊天与翻译工具
动手学Avalonia:基于SemanticKernel与硅基流动构建AI聊天与翻译工具
313 2