【13.7】煎饼问题( Pancake Problem)
今天在浏览 Grishin Lab的时候，发现有个人的研究内容是pancake problem，抱着好奇的心态查阅了一下相关内容。
问题背景：
麦兜最喜欢的食物是煎饼，每次在街上看到煎饼摊的时候都会在那里停留几分钟。最吸引麦兜还是煎饼师傅那一手熟练的翻煎饼的技术，一堆煎饼在那里，师傅只需要用铲子翻几下，就让煎饼整齐的叠在了一起。 这天，为了庆祝麦兜被保送上研究生，他从煎饼师傅那里买回来一些煎饼请客。但是麦兜买回的煎饼大小不一，麦兜太想吃煎饼了，他想吃这些煎饼中最大的那个。麦兜还知道同学们也很喜欢煎饼，为了表示他的诚意，他想让同学们先吃，麦兜最后吃，因此，麦兜想把煎饼按照从小到大的顺序叠放在一起，大的在最下面。这样麦兜就可以在最后拿到最大的那一块煎饼了。 现在请你帮助麦兜用煎饼师傅翻煎饼的方法把麦兜买的煎饼从小到大的叠在一起。煎饼师傅的方法是用铲子插入两块煎饼之间，然后将铲子上的煎饼翻一转，这样铲子上第一个煎饼就被翻到了顶上，而原来顶上的煎饼则被翻到了刚才插入铲子的地方（铲子插入的位置以上的煎饼，会一起反转顺序）。麦兜希望这样翻煎饼的次数最少。
例子如下：
最开始饼的顺序为 5，2，3，4，1 （数值越大，代表饼越大），经过4次翻转以后，顺序变成1，2，3，4，5
这是《编程之美》的第三个问题。属于离散数学的问题，可以先看一下这个图形并茂的 讲义了解一下
书中的初步解析大体思路自然是没有一点问题，只是得出的上界结论有点不正确，这个直接影响了书中递归退出条件：“我们至多需要 2（n-1）次翻转就可以把所有烙饼排好序”。这个数值应该是2n-3，如下推理：我们知道将最大尺寸的放在最下边最多需要2次，此时取这n个中的n-2个（剩下那个最小的和次最小的），将这个n-2个煎饼按由小到大放置好最多需要2(n-2)次，此时还有两个，最多只需要1次就可以完成整个煎饼的排序。所以，上限次数为2(n-2)+1=2n-3。
Pancake Sorting
假设堆叠了n个编号的煎饼，并且可以使用刮刀将前k个薄煎饼的顺序颠倒（2 ≤ k ≤ n）。 然后煎饼排序问题询问有多少这样的“前缀反转”（prefix reversals）足以对任意堆栈（stack）进行排序（Skiena 1990，p.48）。
排序n = 1,2,3，…煎饼的随机堆栈所需的最大翻转次数a_n为0,1,3,4,5,7,8,9,10,11,13 …… 。，n = 2,3的最大堆栈数，……为1,1,3,20,2,35,455，….
下表给出了需要k翻转的n个煎饼的堆叠数。
例如，需要最多四次翻转的三个四个煎饼堆栈是（2,4,1,3），（3,1,4,2）和（4,2,3,1），它们可以是 分别使用翻转序列（2,4,3,2），（2,3,4,2）和（2,3,2,4）排序（如上所示，这里括号的每个数字代表在什么位置反转）。 同样，需要最多七次翻转的两个煎饼堆叠是（4,6,2,5,1,3）和（5,3,6,1,4,2），可以分别使用翻顺序 （2,3,4,2,6,3,2）和（2,3,6,2,4,3,2）。
讨论
- 这个算法在DNA或蛋白序列有什么应用呢？遗传进化，还是突变次数呢？
参考资料
