开发者社区> 衣舞晨风> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

拼图游戏的数学原理

简介: 一、线性代数基础知识 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;

小结:

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

定理一的叙述及证明

定理二的叙述及证明

定理三的叙述及证明

 

 


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Flink 1.14.0 消费 kafka 数据自定义反序列化类
在最近发布的 Flink 1.14.0 版本中对 Source 接口进行了重构,细节可以参考 FLIP-27: Refactor Source Interface 重构之后 API 层面的改动还是非常大的,那在使用新的 API 消费 kafka 数据的时候如何自定义序列化类呢?
214 0
哈迷福利!这个小哥租下一座城堡,用AR和GPS做了张“活点地图”,实时追踪入侵者
哈迷福利!这个小哥租下一座城堡,用AR和GPS做了张“活点地图”,实时追踪入侵者
56 0
数据结构实例参考——“查找”的原理
1、对于A[0..10]有序表{12,18,24,35,47,50,62,83,90,115,134} 采用二分查找法对应的判定树: 成功和不成功时的平均查找长度。 2、现给出一个分块有序的数据表,每块中元素的个数s=8,其中的数据有: 22,4,23,11,20,2,15,13,30,45,26,34,29,35,26,36,55,98,56,74,61,90,8
958 0
Spark修炼之道(基础篇)——Linux大数据开发基础:第十三节:Shell编程入门(五)
本节主要内容 while循环控制结构 if条件判断 until循环控制结构 1. while循环控制结构 本节例子来源:http://blog.chinaunix.net/uid-25880122-id-2901409.html 语法格式: while expression do command command done (1)计数器格式 适用于循环次
2327 0
Spark修炼之道(基础篇)——Linux大数据开发基础:第十一节:Shell编程入门(三)
本节主要内容 shell数组 shell命令别名 时间操作 1. Shell数组 同C、C++等语言一样,shell脚本也提供了数组这样一个重要的数据结构,shell中的数组有两种,一种为普通数组,另外的一种称为关联数组。普通数据的存取通过整数进行,关联数组的存取通过字符串进行。具体如下: //用()定义一个数组,注意数组元素间不能用,否则达不到预期目的 roo
2538 0
纸上谈兵: 数学归纳法, 递归, 栈
作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢!    数学归纳法 数学归纳法(mathematical induction)是一种数学证明方法,常用于证明命题(命题是对某个现象的描述)在自然数范围内成立。
878 0
+关注
衣舞晨风
http://blog.csdn.net/jiankunking
701
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载