將空位移動到與目標矩陣形式相同的位置,計算該序列的逆奇偶性是否與目標矩陣形式對應的序列的逆奇偶性相同。
壹旦它們相同,就可以互換。
兩個不同的不能互換。
在設計數字拼圖遊戲時,只需要相同的輸出。
此外,還可以使用隨機函數從目標矩陣形式出發,打亂目標矩陣形式。
之後,妳可以得到壹個新的矩陣形式,然後輸出這個新的矩陣形式。
註:以下是這種方法的證明過程,在百度搜索壹下就知道“逆數”了。
定理:交換改變排列的奇偶性。
證明:有壹個數的排列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)
評論
加載更多