f(Program,Poet)=Programet

Update:目前发现我的证明错误在于忘记了在动态规划中强调过的局部最优和全局最优的关系……正在修正中
本文的引用材料来源暂时不公布。OMG，出题的人说我的解法中有问题……

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

我的解答(不够严谨)：

可以知道，n,n-1,…,1之间有n(n-1)/2 个逆序对。我们的目标就是要将逆序对全部消除。根据贪心原则，我们可以证明如果每一步都尽可能地消除更多的，那么我们的总步数就最少。我下面给出一个策略，然后证明他的确是最优的。

策略：第一次将n移动到最后面，消除n-1个逆序对；第二次将n-1移动到n的左边（n已经移动过了）；第三次将n-2移动到n-1的左边；……；最后将2移动到3的右边。大功告成。这样，我们一共消除了 (n-1)+(n-2)+…+1=n(n-1)/2 对逆序对，用了n-1步（没有移动1）。

下面证明每一步都尽可能地消除了最多的逆序对。
第一步显然是n-1（他和自己无法构成逆序对）。
在接下来的每一步中，我们正尝试移动的数都已经和前面若干个已经移动过的数不再形成逆序对，这样，每一步过后，我们能够达到的可消除逆序对数的上限就是还没有经过移动的数的数量——因为其他所有经过移动的数都已经不会再和其他数形成逆序对了（不然怎么能够满足尽可能消除逆序对数量的目的？）。因此，第i步能够消除的逆序对数不超过n-i个。

综上所述，证毕。

如果有人找出了错误，请速度告诉我。
看不懂，也请速度告诉我。以后我会注意不要写得像这个样子。

附原文的题面：
Consider a permutation over the numbers 1 through n. For example, with n=7, one can think of the permutation [1, 4, 5, 6, 2, 3, 7].
Let us define a Block Move as a function that makes a new permutation from an existing permutation by taking a contiguous block from it and placing it in a new position. The permutation given above, for example, can be made into the permutation [1, 2, 3, ..., 7] by a single block move. All we need to do is to take the block “4, 5, 6″ and move it to be between the “3″ and the “7″. We say that the original permuation can be sorted in 1 block move.
Not all permutations are this easy to sort. The permutation [4 3 2 1 5 13 12 11 10 9 8 7 6], for example, was shown by help from a computer to require at least 8 block moves to be sorted.
This month’s riddle is regarding sorting the inverse permutation [n, n-1, ..., 3, 2, 1]. Answer the following question:
How many block moves does it take to sort the inverse permutation (as a function of n)?
To demonstrate the correctness of your answer, prove that the number you give is a minimum bound and describe an algorithm that sorts in this number of block moves.

本文由 严酷的魔王 创作，转载或引用前请联系我们。

相关文章：

1. 问问matlab:WHY?
2. 素数有无穷多个的另类证明（二）：素数的某个求和式
3. 关于游客困境的见解
4. “块移动”问题解答
5. 推荐时间：与机器人对话

2008年9月6日 星期六