您当前的位置:首页 > 学习 > 阅览室

趣题:用最少的块移动实现逆序操作

时间:12-04来源:作者:点击数:

题目:

对数列的一次“块移动”是指把一段数取出来插入到数列中的另一个地方(说穿了就是一次选择剪切粘贴的操作)。例如,数列1,4,5,6,2,3,7可以通过一次块移动完成排序(把456挪到3后面)。那么,想要让一个1到n的逆序排列n, n-1, …, 3, 2, 1变为顺序排列,最少需要多少次块移动?给出你的算法,并证明这个移动数目不能再少了。

需要指出的是,答案并不是n-1那么简单。当n=5时,只需要三步就可以搞定了:

 5  4 [3  2] 1
 3  2  5 [4  1]
[3  4] 1  2  5
 1  2  3  4  5

事实上,给出1到n的逆序排列,最少需要Ceil[(n+1)/2]次块移动就可以完成排序(除了n=1或n=2,Ceil表示取上整)。当n为奇数时,一个满足要求的算法是:每一次把数字n后面那一段的正中间两个元素拿出来,插入到数字n前面那一段数的正中间。当数字n后面的数被移动完了后,把它前面n-1个数左右两半对换一下就行了。例如,当n=7时:

 7  6  5 [4  3] 2  1
 4  3  7  6 [5  2] 1
 4  5  2  3  7 [6  1]
[4  5  6] 1  2  3  7
 1  2  3  4  5  6  7

算法的移动步数显然为(n+1)/2,其正确性可以用数学归纳法说明,这里不再详细叙述了。

当n为偶数时,只需要用n/2次操作把前面n-1个元素排好序,再花一次操作把末一个元素移动到最前面,加起来正好Ceil[(n+1)/2]次操作。下面我们证明,移动次数不可能比Ceil[(n+1)/2]更少。

对于数列中相邻的两个数,如果前面那个数比后面的大,我们就把它们俩称作一组“逆序相邻数”。初始时,数列中有n-1个这样的逆序相邻数,我们的目标就是通过块移动把这个数目减少到0。整个证明过程的关键就在于,一次块移动操作最多只能消除两个逆序相邻数。

原数列: **aA–Bb***CD****

新数列: **ab***CA–BD****

假如我们把块A–B插入到CD中间。注意到,相邻数发生变动的地方只有三处。要想同时消除三个逆序相邻数,只有一种可能:原数列中a>A, B>b, C>D,同时新数列中的a<b, C<A, B<D。这将导出一个很荒谬的结论:A < a < b < B < D < C < A。这告诉我们,一次块移动同时消除三个逆序相邻数是不可能的,它最多只能消除两个逆序相邻数。另外,容易看出,第一次移动只能消除一个逆序的相邻数,因为初始时原数列完全逆序,即有a > A > B > b > C > D,在新数列中只有C<A成立。对称地,最后一次移动也只可能消除一个逆序相邻数,因为新数列中a < b < C < A < B < D,只有B>b是成立的。

于是我们得知,k次块移动最多消除1+2*(k-2)+1个逆序相邻数。为了消除n-1个逆序相邻数,我们有1+2*(k-2)+1 >= n-1,整理得k>=(n+1)/2。

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门