相鄰交換:逆序對給出最少次數
用逆序對變化與六種排列窮舉證明321變123至少需要3次相鄰交換。
影片暫時無法載入。請檢查網絡後重試,或直接下載影片。
下載影片
展開影片文字稿
- 数卡排成三、二、一,每次只能交换相邻两张。目标是排成一、二、三。
- 三二一里有三对顺序颠倒:三和二、三和一、二和一,所以至少需要消掉三个逆序。
- 第一次交换前两张,三二一变成二三一,只消掉三和二这一对。
- 第二次交换后两张,二三一变成二一三;第三次再交换前两张,得到一二三。
- 一次相邻交换最多减少一个逆序对,所以不可能少于三次;这条路线正好用了三次。
- 最少次数就是三。每次只交换相邻两张,并把交换前后的顺序写下来,就不容易漏步。
講解依據
邏輯思維
逆序數下界與構造,並用反向檢查確認。
看一個例子
數卡排成3、2、1,每次只能交換相鄰兩張。最少幾次能變成1、2、3?
3次。列出三張卡的6種排列及相鄰交換邊,最短路徑長度為3。
立即試一題
只有一個逆序對,交換前兩張一次即可。