相邻交换:逆序对给出最少次数
用逆序对变化与六种排列穷举证明321变123至少需要3次相邻交换。
视频暂时无法加载。请检查网络后重试,或直接下载视频。
下载视频
展开视频文字稿
- 数卡排成三、二、一,每次只能交换相邻两张。目标是排成一、二、三。
- 三二一里有三对顺序颠倒:三和二、三和一、二和一,所以至少需要消掉三个逆序。
- 第一次交换前两张,三二一变成二三一,只消掉三和二这一对。
- 第二次交换后两张,二三一变成二一三;第三次再交换前两张,得到一二三。
- 一次相邻交换最多减少一个逆序对,所以不可能少于三次;这条路线正好用了三次。
- 最少次数就是三。每次只交换相邻两张,并把交换前后的顺序写下来,就不容易漏步。
讲解依据
逻辑思维
逆序数下界与构造,并用反向检查确认。
看一个例子
数卡排成3、2、1,每次只能交换相邻两张。最少几次能变成1、2、3?
3次。列出三张卡的6种排列及相邻交换边,最短路径长度为3。
马上试一题
只有一个逆序对,交换前两张一次即可。