转贴一个答案：

这个问题其实就是一个数据结构中的排序问题 
最少当然是0次（烙饼本来就是从大到小排好的） 
最多应该是插入排序最坏情况下的次数 好像是N平方次  

最优的话 应该用快速排序算法 算是最好的了 

不知道对不对  

Maximum : 2*(n-2) + 1 

O(n)

本书3月中旬上市。

潘爱民倾力推荐《编程之美——微软技术面试心得》
 
　　 我很早知道邹欣计划要写这样一本书，也能够预计到这本书定会广受欢迎，因为它符合当前大量求职人员的需求，毕竟于他们而言，谁不想知道微软亚洲研究院在招人时候问些什么问题呢。另一方面，把考察软件技术人员专业知识和相应技能的各种手段加以归纳和整理，这本身也是对业界的贡献，所以，我相信，一旦这本书如计划般完成，其对业界的影响将是深远的。 

在我的面试经历中，通过一些具体的程序问题来考察人，往往是最有效的，即使是一些人所皆知的问题，也往往能够挖掘出被面试者的亮点或弱点，原因在于，每个问题都有不同层次的解答之辞，面试者总是可以刨根究底地问下去。我们在看一段程序的时候，思路固然重要，细节也是不可忽视的，比如整数是否越界、指针是否为空，等等。这些细节可以用于考察基本功，毫无疑问，基本功不扎实的人通常很难得到面试者的青睐。 

当拿到这本书的样稿时，我迫不及待地放下手头工作，阅读起来。有些题目的内容会引起强烈的共鸣，尤其是那些自己非常熟悉并且又深知解答的题目；也有一些题目让我异常惊诧，原来除了我所知道的解答思路之外，还有更好的解答以及更深层次的原因。还有一些题目是从来没想到过的。阅读过程是一次愉快的享受，也是脑细胞持续活跃的过程。 

充满好奇心的人们总是能从生活的点点滴滴中想到或找到各种优化的余地，比如说，楼宇中的电梯常常显得很“傻”(微软研究院所在的希格玛大厦的电梯是一个典型的例子)，更智能或更有效的调度策略完全有可能；近距离内的交通灯联动可以有效地提高行车效率。程序员在玩电脑游戏的时候常常会想着怎么自动完成一些过程，比如说，本书中提到的俄罗斯方块游戏中如何有效地旋转和移动可快速地消除积木块、24点游戏如何自动求解、推箱子游戏如何自动求解，扫地雷游戏如何自动完成，等等。实际上，这些自然的疑问正是训练程序能力的好来源，本书采录了不少此类题目。因此，阅读本书可以满足很多人的好奇心，这也正是我自己的体会。 

尽管作者在前言中声称“虽经过几轮审核，不少解法仍可能有漏洞或错误”，但事实上，在绝大多数题目的讲解中，作者已经由浅入深地把问题分析透了，而且，作者也为读者指出了进一步思考这些题目的方向。不同背景的人在看到这些题目的时候，可能会有不同的解法，甚至完全不同的思路。举例而言，邹欣曾经问过我如何控制CPU占用率曲线的问题，我当时的直觉是，直接截取Taskmgr调用的相关API函数，从而达到随意控制CPU占用率曲线的目的。显然这不是规范的做法，本书的分析揭示了这个问题背后的本质道理以及考问要点。另一种情况，即使有的问题你深知其理，但看过本书仍然很有收获。例如，在斐波那契数列问题中，我知道直接递归法的缺陷，也知道如何简化成迭代法来改进效率，还会推导通项公式，但是，书中的细致讲解仍然让我对这个问题有了更进一步的认识。这是本书的深度所在，如果读者更加在意所选题目背后的深层次道理，相信书中的讲解不会让你失望。 

除了趣味性以外，本书中的题目讲解之中也融入了大量专业知识。这使得本书可以作为计算机数据结构课程或算法课程的辅助参考书。比如，有些问题的解答涉及到贪心算法或动态规划方法，算法的复杂度分析更是无处不在。数据结构教科书中介绍的链表(list)、队列、hash表和二叉树等常用数据结构也多有提及。因此，对于正在学习数据结构或算法课程的学生来说，本书中的问题正是对课程中所学知识的一次检阅，通过本书他们可以看到这些知识是如何用于解决实际问题的。从我自己的教学经验来看，这样的题解分析有助于提高学生的学习兴趣。另一方面，阅读本书也需要有必要的计算机算法和程序设计知识作为基础，否则阅读的效果会大打折扣。 

我大致了解本书的成书过程，从策划阶段到题目收集，再到成稿和改稿，我能体会到邹欣和他的写作团队倾注了大量的精力来写作这本书。他们尽了最大的努力来编写这本书，无论是原创的题目，还是传统的题目，他们都努力把题目分析透彻并提供扩展思考的余地。邹欣在发送样稿给我的信中说道：“Our goal is to ship a top quality book. I can't say "world class", but definitely "best in China" level.”以我阅读这本书的体会来讲，他们做到了这一点。我相信，这本书的出版会符合我当初的预期，它会影响到很多人。 



潘爱民 

2008年2月 

 

看看～～