数字拼图游戏中，保证完成的实现方法？？？？
发布网友
发布时间：2022-04-21 19:56
共2个回答
热心网友
时间：2023-09-27 04:55
热心网友
时间：2023-09-27 04:55
将空位移动到与目标矩阵形式相同的位置，计算数列的逆序数奇偶性是否与目标矩阵形式对应数列的逆序数奇偶性相同
一相同的就可以互换
二不同的就不能互换
在设计数字拼图游戏时，只需要相同的输出就可以了
除此之外，还可以用随机函数，从目标矩阵形式开始运行，打乱目标矩阵形式
后就可以得到一个新的矩阵形式，再输出这个新的矩阵形式即可
注：以下是该方法的证明过程，关于“逆序数”，百度里搜一下，你就知道了。
定理：对换改变排列的奇偶性。
证明：设有一数字排列a={s(1)，s(2)，...，s(k-2)，s(k-1)，s(k)，s(k+1)，...，s(n-1)，s(n)}，任意对换a中相邻两元素s(k-1)和s(k)，则
对换产生一个数字排列b={s(1)，s(2)，...，s(k-2)，s(k)，s(k-1)，s(k+1)，...，s(n-1)，s(n)}
相邻两元素构成的排列c={s(k-1)，s(k)}
相邻两元素构成的排列d={s(k)，s(k-1)}
设fx(k)为数字排列x的第k个元素与其后的所有元素的逆序之和，Ex为数字排列x的每一个元素与其后所有元素的逆序之和，简称“逆序数”，
逆序数为奇数的称之为奇排列，逆序数为偶数的称之为偶排列，则
Ea=fa(1)+fa(2)+...+fa(k-2)+fa(k-1)+fa(k)+fa(k+1)+...+fa(n-1)+fa(n)
Eb=fb(1)+fb(2)+...+fb(k-2)+fb(k-1)+fb(k)+fb(k+1)+...+fb(n-1)+fb(n)
因为fa(1)=fb(1)，fa(2)=fb(2)，...，fa(k-2)=fb(k-2)，fa(k+1)=fb(k+1)，...，fa(n-1)=fb(n-1)，fa(n)=fb(n)
所以Ea-Eb=[fa(k-1)+fa(k)]-[fb(k-1)+fb(k)]
因为数字排列a和数字排列b中的s(k-1)、s(k)与s(k+1)及其后的所有元素的逆序之和相等
所以Ea-Eb=Ec-Ed
当s(k-1)<s(k)时，Ea-Eb=0-1
当s(k-1)>s(k)时，Ea-Eb=1-0
所以Ea±1=Eb，即对换相邻两元素，数字排列的奇偶性改变
推论一：数列进行奇数次相邻对换，数列的奇偶性会改变
推论二：数列进行偶数次相邻对换，数列的奇偶性不改变
假设任意对换a中两元素s(m)和s(k)，其中（m<k），则
可以先把s(m)进行k-m次相邻对换，移动到s(k)的位置
s(1)，s(2)，...，s(m)，s(m+1)，...，s(k-2)，s(k-1)，s(k)，...，s(n-1)，s(n)
s(1)，s(2)，...，s(m+1)，s(m)，...，s(k-2)，s(k-1)，s(k)，...，s(n-1)，s(n)
...
s(1)，s(2)，...，s(m+1)，s(m+2)，...，s(k-1)，s(k)，s(m)，...，s(n-1)，s(n)
再把s(k)进行k-m-1次相邻对换，移动到s(m-1)的位置
s(1)，s(2)，...，s(m+1)，s(m+2)，...，s(k-1)，s(k)，s(m)，...，s(n-1)，s(n)
s(1)，s(2)，...，s(m+1)，s(m+2)，...，s(k)，s(k-1)，s(m)，...，s(n-1)，s(n)
...
s(1)，s(2)，...，s(k)，s(m+1)，...，s(k-2)，s(k-1)，s(m)，...，s(n-1)，s(n)
所以总共要进行2(k-m)-1次相邻对换，才可以把s(m)移动到s(k)的位置
因为2(k-m)-1是奇数，所以数字排列的奇偶性改变
综上所述，对换改变排列的奇偶性
在N*N的数字拼图中，
①当空位左或右移动时，
因为数列不变，所以数列奇偶性不变
②当空位上或下移动时，
相当于与空位交换的数字向右或向左相邻对换N-1次
当数字拼图中空位在某位置时，移动空位使其成为任意其他的矩阵形式，最后再将空位回到原位置，则
因为空位要想回到原位置，就必须进行若干次相等的左、右移动和上、下移动（例如，空位向左移动了1次，向右也要移动1次，才能回到原位置）
因为若干次相等的左、右移动不改变数列的奇偶性，若干次相等的上、下移动相当于进行若干个N-1次数字向右相邻对换和若干个N-1次数字向左相邻对换
当N-1为偶数时，数列的奇偶性在数字向右和向左对换时都不改变，最终保持不变
当N-1为奇数时，数列的奇偶性在数字向右和向左对换时都会改变，最终保持不变
所以当空位的位置相同时，可互换的矩阵形式对应的数列奇偶性相同
