数字拼图中确保完整性的实现方法

将空位移动到与目标矩阵形式相同的位置，计算该序列的逆奇偶性是否与目标矩阵形式对应的序列的逆奇偶性相同。

一旦它们相同，就可以互换。

两个不同的不能互换。

在设计数字拼图游戏时，只需要相同的输出。

此外，还可以使用随机函数从目标矩阵形式出发，打乱目标矩阵形式。

之后，你可以得到一个新的矩阵形式，然后输出这个新的矩阵形式。

注:以下是这种方法的证明过程，在百度搜索一下就知道“逆数”了。

定理:交换改变排列的奇偶性。

证明:有一个数的排列a={s(1)，s(2)，...，s(k-2)，s(k-1)，s(k+1)，...，s(。

排列产生一个数字排列b={s(1)，s(2)，...，s(k-2)，s(k-1)，s(k+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+65438)。

所以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，即相邻两个元素互换时，数排列的奇偶性发生变化。

推论1:一个序列相邻排列的奇数会改变它的奇偶性。

推论二:即使序列互换几次，序列的奇偶性也不变。

假设A中的两个元素s(m)和s(k)任意互换，其中(m)

评论

加载更多