共有回帖数 0 个
-
如题，曾经做的那个拼图的小游戏，产生了随机排列是否一定可还原成
原图形的问题，当时无论把代码怎么处理也弄不好（线代没学好），
通过百度，以及炮姐的点拨，总算让我想明白了，炮姐的代码我没仔细看，
（不喜欢看别人的，只喜欢自己想），下面说下我的解决方法吧。
在3*3或4*4数字拼图游戏中，有的拼图拼到最后出现有1对板块是对调的，怎么都还原不到完整的顺序，这样的拼图其实是不可还原的拼图。
现在很多手机和电子词典上都有这款游戏，不知到大家在玩的时候有没有发现有的拼图怎么都还原不到完整的图片（或数字顺序），最终出现有1对板块（两个）是对调的，这个时候你可以停下来了，这不是你水平的问题，是游戏设计者的过错！很多游戏设计者都是将板块随机打乱，实际上并不是所有随机打乱之后都是可以还原的！确切的说，随机打乱后，有二分之一的概率是可以被还原的。详细证明如下：
以3*3的九格为例，如下图：
1 2 3
4 5 6
7 8
a图
1 2 3
4 5 6
8 7
b图
假设图中的a是3*3数字拼图标准的结果，则对于图b的状态是不可能变换成a的。证明起来需要用到高等代数里逆序数的概念，具体的说是用到了一个简单的定理。
定义：在一个1,2,...,n的排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。逆序数为偶数的排列称为偶排列；逆序数为奇数的排列称为奇排列。如2431中，21，43，41，31是逆序，逆序数是4，为偶排列。——这是北大《高等代数》上的定义。
定理：交换一个排列中的两个数，则排列的奇偶性发生改变。（证明见任何一本《高等代数》）
我们将空格看成数字9（数字9对应空位），按正常顺序看a图，9个数字排列是123456789，其逆序数是0，是偶排列；b图是123456879，逆序数是1，是奇排列。我们知道，我们能够移动空块相邻的块，这里的移动相当于一种特殊的对换（相邻对换），例如：对于b图，移动6就相当于9和6互换（9向上移动了），移动7就相当于9和7互换（9向左移动了）。现在假设从b图经过一系列的平移变到了a图，则空格块9必然移动（对换）了偶数次（向左一次必然要再向右一次回来，向上一次必然要向下再回来，最终才能够回到右下角的位置），根据上面的定理最终变成的排列必然是仍然是奇排列（和b相同），然而a图是偶排列，因而产生矛盾，因此b图不可能通过平移变成最终的a图。
拼图的分类：
进一步考虑，a图可以平移变成一些其他的状态，我们把所有可以由a图变换的到的状态归为一类，实际上这是一个等价关系（平移变换）决定的等价类（a图一个代表元），b图也代表一类，现在要问“拼图总共有几类？”，答案是大于等于2*2（2行2列）的拼图都有且只有这2类。这里只介绍证明思路： 1. 根据上面的定理，可以得出所有的拼图至少分两类； 2. 2*2（2行2列）的拼图只有有两类； 3. 拼图在增大之后，分类数不增。 根据这3条就可得出结论：拼图有且只有两类。并且我们可以得出一些其他有趣的结果，两类拼图图形上的差异是他们之间相差奇数次的对换（相当于把任意两块扣下来，对调），也就是说任意交换一个拼图非空板块奇数次，则它就变到另外一类里了。 对于分为两类的理解，正如上的旋转方向面上有顺时针和逆时针之分。至此，我们就知道，如果拼图的版块是随机打乱的，那么只有一半的可能是可以被还原的。
简单的考虑之后，我们就可以知道，还原一个拼图是可以逐行或逐列还原的（排好之后可以不在被动！）， 最后只剩最右下角的2*3或3*2的几块是乱序，再调好其中的2块，剩下的3块简单轮换下位置就应该完成了，如果不对，那改图就属于那种不可以被还原的一类。
下面代码：
用搜狗，度娘会吞空格和回车，蛋疼，用IE10就没问题了。
void make_random_map(int arr[][4])
{
randomize();
int sum=0;
int nixushu=0;
while (1)
{
int *p1=*arr;
for (int i=0;i16;i++) p1=0;
for (int i=0;i=3;i++)
for (int j=0;j=3;j++)
{
while (1)
{
sum=0;
arr[j]=random(16)+1;
for (int x=0;x=3;x++)
for (int y=0;y=3;y++)
{
if (arr[j]==arr[x][y])
sum++;
}
if (sum==1) break;
}
}
/////////////////////////////////修正地图///////////////////////////
nixushu=0;
int *p=*arr;
for (int i=0;i15;i++)
for (int j=i+1;j16;j++)
{
if (pp[j]) nixushu++;
}
if (nixushu%2==0) break;
} }
/*vo
楼主 2015-11-19 13:16 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
