Question

数字拼图游戏中，保证完成的实现方法？？？？

Answer 1

判断两数字拼图矩阵形式是否可以互换的方法：
将空位移动到与目标矩阵形式相同的位置，计算数列的逆序数奇偶性是否与目标矩阵形式对应数列的逆序数奇偶性相同
一相同的就可以互换
二不同的就不能互换
在设计数字拼图游戏时，只需要相同的输出就可以了
除此之外，还可以用随机函数，从目标矩阵形式开始运行，打乱目标矩阵形式
后就可以得到一个新的矩阵形式，再输出这个新的矩阵形式即可
注：以下是该方法的证明过程，关于“逆序数”，百度里搜一下，你就知道了。
定理：对换改变排列的奇偶性。
证明：设有一数字排列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=1-0
所以Ea±1=Eb，即对换相邻两元素，数字排列的奇偶性改变
推论一：数列进行奇数次相邻对换，数列的奇偶性会改变
推论二：数列进行偶数次相邻对换，数列的奇偶性不改变
假设任意对换a中两元素s(m)和s(k)，其中（m
评论
0
0
加载更多