文档章节

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

暗之幻影
 暗之幻影
发布于 2016/12/08 14:45
字数 955
阅读 2
收藏 0

原文

上次那篇日志发布之后,据说大家解题的热情相当高。Michael Brand告诉我说,他收到了很多来自中国的邮件,他感到非常高兴。在揭晓谜底之前,还是让我们先回顾一下题目:

    对数列的一次“块移动”是指把一段数取出来插入到数列中的另一个地方(说穿了就是一次选择剪切粘贴的操作)。例如,数列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。

本文转载自:http://depravedangel.iteye.com/blog/1183788

暗之幻影
粉丝 20
博文 377
码字总数 71245
作品 0
南京
高级程序员
私信 提问
Leetcode【435、452、738、991】

问题描述:【Greedy】435. Non-overlapping Intervals 解题思路: 这道题是给一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。 实际上,这道题和 贪心算法之活动安排问题 ...

牛奶芝麻
07/05
0
0
cache 的设计与实现

本文整理自一下两篇博客:http://my.oschina.net/ScottYang/blog/298727 http://my.oschina.net/u/866190/blog/188712 Cache简介: Cache(高速缓存), 一个在计算机中几乎随时接触的概念。C...

peiquan
2014/09/26
0
0
XYNUOJ 积木大赛

积木大赛时间限制: 1 Sec 内存限制: 128 MB 提交: 11 解决: 8 [提交][状态][讨论版] 题目描述 春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为n的大厦,大厦可以看...

dear_jia
2018/03/11
0
0
Leetcode【789、1017】

问题描述:【Math】789. Escape The Ghosts 解题思路: 这道题是在二维平面上有一个人从原点出发,每次移动一个单位(东南西北)到目标坐标 target,平面上还有一些鬼 ghosts 每次也移动一个...

牛奶芝麻
07/16
0
0
CFEDU 35 A - D 题解

传送门 A: 求最小的元素相隔的距离最小是多少. 记录最小值的位置, 扫一遍就行啦. AC Code B: n个人分两个分别被切成了a, b份的蛋糕, 每个人至少得到一份, 两个蛋糕的份数不能同时给一个人, 也...

Anxdada
2018/01/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

面试官,Java8 JVM内存结构变了,永久代到元空间

在文章《JVM之内存结构详解》中我们描述了Java7以前的JVM内存结构,但在Java8和以后版本中JVM的内存结构慢慢发生了变化。作为面试官如果你还不知道,那么面试过程中是不是有些露怯?作为面试...

程序新视界
2分钟前
0
0
读书笔记:深入理解ES6 (八)

第八章 迭代器(Iterator)与生成器(Generator) 第1节 循环语句的问题   在循环、多重循环中,通过变量来跟踪数组索引的行为容易导致程序出错。迭代器的出现旨在消除这种复杂性,并减少循...

张森ZS
3分钟前
1
0
Elasticsearch 实战(一) - 简介

官腔 Elasticsearch,分布式,高性能,高可用,可伸缩的搜索和分析系统 基本等于没说,咱们慢慢看 1 概述 百度:我们比如说想找寻任何的信息的时候,就会上百度去搜索一下,比如说找一部自己喜...

JavaEdge
7分钟前
0
0
【jQuery基础学习】11 jQuery性能简单优化

本文转载于:专业的前端网站➦【jQuery基础学习】11 jQuery性能简单优化 关于性能优化 合适的选择器 $("#id")会直接调用底层方法,所以这是最快的。如果这样不能直接找到,也可以用find方法继...

前端老手
16分钟前
3
0
重磅发布 | 全球首个云原生应用标准定义与架构模型 OAM 正式开源

导读:2019 年 10 月 17 日,阿里巴巴合伙人、阿里云智能基础产品事业部总经理蒋江伟(花名:小邪)在 Qcon 上海重磅宣布,阿里云与微软联合推出开放应用模型 Open Application Model (OAM...

阿里云官方博客
19分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部