设为首页 - 加入收藏
广告 1000x90
您的当前位置:黄大仙www78345 > 交换排列 > 正文

移动拼图的初始化有什么数学原理么?

来源:未知 编辑:admin 时间:2019-07-17

  我之前写过一个Android的移动拼图游戏。就是把图片切成3X3或者4X4,去掉右下角那一块,然后打乱。一开始打乱的算法是,随机选取两块交换位置,重复若干次。发布之后有用户反应,移动拼...

  我之前写过一个Android的移动拼图游戏。就是把图片切成3X3或者4X4,去掉右下角那一块,然后打乱。 一开始打乱的算法是,随机选取两块交换位置,重复若干次。 发布之后有用户反应,移动拼图有一半左右的可能无解。 之后改变了初始化的算法,模拟实际的打乱过程。从空白块上下左右随机选一个,和空白块交换位置,重复若干次。 之后用户反映没有出现无解的情况了。 于是 这里边有啥数学原理么? 拜托各位大神

  展开全部【定义1】一个排列,逆序总数为奇数为【奇排列】,逆序总数为偶数为【偶排列】。例如完全的顺序 1 2 3 4 5 ,一个逆序都没有,为偶排列。1 2 3 5 4 有一个逆序,为奇排列。5 4 3 2 1有10个逆序,为偶排列。【定理1】偶排列任意交换两个元素成奇排列,奇排列任意交换两个元素成偶排列。这个定理要证明不难,但有点长,说出来难免罗罗嗦嗦,这里就不用严格语言证明了,大约提一下:(1)假设排列(例如ABXCDYEF)中交换两个单元X和Y。(2)【X前面的元素和Y后面的元素】与【X、Y】的逆序对不改变,也就是如果AX为逆序,那XY交换后AX依然为逆序。(3)【XY】若为逆序,交换后为顺序,若为顺序,交换后为逆序,因此逆序数+1或-1。(4)【X和Y之间的元素】与【X】的逆序+1或-1。(4)【X和Y之间的元素】与【Y】的逆序+1或-1。(5)所以总逆序数奇偶改变。【推论1】一个排列执行任意交换排序后,奇排列执行交换总次数为奇数,偶排列执行交换总次数为偶数。这是因为完全顺序的逆序数是0,是偶排列;奇排列执行奇数次交换成偶排列,偶排列执行偶数次交换成偶排列。这个推论也提供了奇排列和偶排列的判断算法:进行任意交换排序(冒泡排序、快速排序),统计交换次数为奇数还是偶数。【定义2】给移动拼图每一块按照其基准位置从左到右,从上到下依次编上序号,空块也编号。将某一局势所有块从左到右,从上到下依次映射到一个排列S中。若S为奇排列,则当前局势为【奇局势】,否则为【偶局势】。例如,拼图原样是:123456789其中9是空块打乱成:716594238将所有块从左到右,从上到下依次写出来:716594238,经过7次交换成顺序排列,[0]716594238[1]176594238[2]126594738[3]123594768[4]123495768[5]123459768[6]123456798[7]123456789因此这是一个奇排列,因此这个局势是奇局势。【定理2】奇局势移动一次成偶局势,偶局势移动一次成奇局势。也很显然,移动一次即空块和某一块交换,根据定理1,这会导致排列的奇偶性改变。【定义3】在拼图原样中,空块所在位置为【偶位】,任意与偶位相邻的位置为【奇位】,任意与奇位相邻的位置同为【偶位】。一个3×3的拼图,原样的空块在右下角,用0和1表示偶位和奇位为:010101010【定理3】空块在偶位,移动一次必到奇位;空块在奇位,移动一次必到偶位。这个也很显然。【定义4】某一局势,如果其奇偶性和空块所在位奇偶性相同,则将本局称为【偶局】,否则称为【奇局】。很显然,偶局无论怎么移动都是偶局,奇局无论怎么移动都是奇局。而拼图原样为偶局。【结论】偶局可解,奇局无解。

本文链接:http://apkhealth.com/jiaohuanpailie/457.html

相关推荐:

网友评论:

栏目分类

现金彩票 联系QQ:24498872301 邮箱:24498872301@qq.com

Copyright © 2002-2011 DEDECMS. 现金彩票 版权所有 Power by DedeCms

Top