http://book.51cto.com/art/200909/150035.htm
1.3 一摞烙饼的排序
星期五的晚上，一帮同事在希格玛大厦附近的"硬盘酒吧"多喝了几杯。程序员多喝了几杯之后谈什么呢？自然是算法问题。有个同事说：
"我以前在餐馆打工，顾客经常点非常多的烙饼。店里的饼大小不一，我习惯在到达顾客饭桌前，把一摞饼按照大小次序摆好--小的在上面，大的在下面。由于我一只手托着盘子，只好用另一只手，一次抓住最上面的几块饼，把它们上下颠倒个个儿，反复几次之后，这摞烙饼就排好序了。
我后来想，这实际上是个有趣的排序问题：假设有n块大小不一的烙饼，那最少要翻几次，才能达到最后大小有序的结果呢？
你能否写出一个程序，对于n块大小不一的烙饼，输出最优化的翻饼过程呢？
分析与解法
这个排序问题非常有意思，首先我们要弄清楚解决问题的关键操作--"单手每次抓几块饼，全部颠倒"。
具体参看图1-6：
每次我们只能选择最上方的一堆饼，一起翻转。而不能一张张地直接抽出来，然后进行插入，也不能交换任意两块饼子。这说明基本的排序办法都不太好用。那么怎么把这n个烙饼排好序呢？
由于每次操作都是针对最上面的饼，如果最底层的饼已经排序，那我们只用处理上面的n-1个烙饼。这样，我们可以再简化为n-2、n-3，直到最上面的两个饼排好序。
【解法一】
我们用图1-7演示一下，为了把最大的烙饼摆在最下面，我们先把最上面的烙饼和最大的烙饼之间的烙饼翻转（1~4之间），这样，最大的烙饼就在最上面了。接着，我们把所有烙饼翻转（4~5之间），最大的烙饼就摆在最下面了。
之后，我们对上面n-1、n-2个饼重复这个过程就可以了。
那么，我们一共需要多少次翻转才能把这些烙饼给翻转过来呢？
首先，经过两次翻转可以把最大的烙饼翻转到最下面。因此，最多需要把上面的n-1个烙饼依次翻转两次。那么，我们至多需要2（n-1）次翻转就可以把所有烙饼排好序（因为第二小的烙饼排好的时候，最小的烙饼已经在最上面了）。
这样看来，单手翻转的想法是肯定可以实现的。我们进一步想想怎么减少翻转烙饼的次数吧。
怎样才能通过程序来搜索到一个最优的方案呢？
首先，通过每次找出最大的烙饼进行翻转是一个可行的解决方案。那么，这个方案是最好的一个吗？考虑这样一种情况，假如这堆烙饼中有好几个不同的部分相对有序，凭直觉来猜想，我们可以先把小一些的烙饼进行翻转，让其有序。这样会比每次翻转最大的烙饼要更快。
既然如此，有类似的方案可以达到目的吗？比如说，考虑每次翻转的时候，把两个本来应该相邻在烙饼尽可能地换到一起。这样，当所有的烙饼都换到一起之后，实际上就是完成排序了。（从这个意义上来说，每次翻最大烙饼的方案实质上就是每次把最大的和次大的交换到一起。）
在这样的基础之上，本能的一个想法就是穷举。只要穷举出所有可能的交换方案，那么，我们一定能够找到一个最优的方案。
沿着这个思路去考虑，我们自然就会使用动态规划或者递归的方法来进行实现了。可以从不同的翻转策略开始，比如说第一次先翻最小的，然后递归把所有的可能全部翻转一遍。这样，最终肯定是可以找到一个解的。
但是，既然是递归就一定有退出的条件。在这个过程中，第一个退出的条件肯定是所有的烙饼已经排好序。那么，有其他的吗？如果大家仔细想想就会发现到，既然2（n-1）是一个最多的翻转次数。如果在算法中，需要翻转的次数多于2（n-1），那么，我们就应该放弃这个翻转算法，直接退出。这样，就能够减少翻转的次数。
从另外一个层面上来说，既然这是一个排序问题。我们也应该利用到排序的信息来进行处理。同样，在翻转的过程中，我们可以看看当前的烙饼数组的排序情况如何，然后利用这些信息来帮助减少翻转次数的判断过程
下面是在前面讨论的基础之上形成的一个粗略的搜索最优方案的程序：
代码清单1-8
class CPrefixSorting
{
public:
CPrefixSorting()
{
m_nCakeCnt = 0;
m_nMaxSwap = 0;
}
//
// 计算烙饼翻转信息
// @param
// pCakeArray 存储烙饼索引数组
// nCakeCnt 烙饼个数
//
void Run(int* pCakeArray, int nCakeCnt)
{
Init(pCakeArray, nCakeCnt);
m_nSearch = 0;
Search(0);
}
//
// 输出烙饼具体翻转的次数
//
void Output()
{
for(int i = 0; i < m_nMaxSwap; i++)
{
printf("%d ", m_arrSwap[i]);
}
printf("\n |Search Times| : %d\n", m_nSearch);
printf("Total Swap times = %d\n", m_nMaxSwap);
}
private:
//
// 初始化数组信息
// @param
// pCakeArray 存储烙饼索引数组
// nCakeCnt 烙饼个数
//
void Init(int* pCakeArray, int nCakeCnt)
{
Assert(pCakeArray != NULL);
Assert(nCakeCnt > 0);
m_nCakeCnt = n;
// 初始化烙饼数组
m_CakeArray = new int[m_nCakeCnt];
Assert(m_CakeArray != NULL);
for(int i = 0; i < m_nCakeCnt; i++)
{
m_CakeArray[i] = pCakeArray[i];
}
// 设置最多交换次数信息
m_nMaxSwap = UpBound(m_nCakeCnt);
// 初始化交换结果数组
m_SwapArray = new int[m_nMaxSwap];
Assert(m_SwapArray != NULL);
// 初始化中间交换结果信息
m_ReverseCakeArray = new int[m_nCakeCnt];
for(i = 0; i < m_nCakeCnt; i++)
{
m_ReverseCakeArray[i] = m_CakeArray[i];
}
m_ReverseCakeArraySwap = new int[m_nMaxSwap];
}
//
// 寻找当前翻转的上界
//
//
int UpBound(int nCakeCnt)
{
return nCakeCnt*2;
}
//
// 寻找当前翻转的下界
//
//
int LowerBound(int* pCakeArray, int nCakeCnt)
{
int t, ret = 0;
// 根据当前数组的排序信息情况来判断最少需要交换多少次
for(int i = 1; i < nCakeCnt; i++)
{
// 判断位置相邻的两个烙饼，是否为尺寸排序上相邻的
t = pCakeArray[i] - pCakeArray[i-1];
if((t == 1) || (t == -1))
{
}
else
{
ret++;
}
}
return ret;
}
// 排序的主函数
void Search(int step)
{
int i, nEstimate;
m_nSearch++;
// 估算这次搜索所需要的最小交换次数
nEstimate = LowerBound(m_ReverseCakeArray, m_nCakeCnt);
if(step + nEstimate > m_nMaxSwap)
return;
// 如果已经排好序，即翻转完成，输出结果
if(IsSorted(m_ReverseCakeArray, m_nCakeCnt))
{
if(step < m_nMaxSwap)
{
m_nMaxSwap = step;
for(i = 0; i < m_nMaxSwap; i++)
m_arrSwap[i] = m_ReverseCakeArraySwap[i];
}
return;
}
// 递归进行翻转
for(i = 1; i < m_nCakeCnt; i++)
{
Revert(0, i);
m_ReverseCakeArraySwap[step] = i;
Search(step + 1);
Revert(0, i);
}
}
//
// true : 已经排好序
// false : 未排序
//
bool IsSorted(int* pCakeArray, int nCakeCnt)
{
for(int i = 1; i < nCakeCnt; i++)
{
if(pCakeArray[i-1] > pCakeArray[i])
{
return false;
}
}
return true;
}
//
// 翻转烙饼信息
//
void Revert(int nBegin, int nEnd)
{
Assert(nEnd > nBegin);
int i, j, t;
// 翻转烙饼信息
for(i = nBegin, j = nEnd; i < j; i++, j--)
{
t = m_ReverseCakeArray[i];
m_ReverseCakeArray[i] = m_ReverseCakeArray[j];
m_ReverseCakeArray[j] = t;
}
}
private:
int* m_CakeArray; // 烙饼信息数组
int m_nCakeCnt; // 烙饼个数
int m_nMaxSwap; // 最多交换次数。根据前面的推断，
这里最多为m_nCakeCnt * 2
int* m_SwapArray; // 交换结果数组
int* m_ReverseCakeArray; // 当前翻转烙饼信息数组
int* m_ReverseCakeArraySwap; // 当前翻转烙饼交换结果数组
int m_nSearch; // 当前搜索次数信息
};
m_nMinSwap越小，那么这个剪枝条件就越容易满足，更多的情况就不需要再去搜索。当然，程序也就能更快地找出最优方案。
仔细分析上面的剪枝条件，在到达m_tArr状态之前，我们已经翻转了step次，nEstimate是在当前这个状态我们至少还要翻转多少次才能成功的次数。如果step+nEstimate大于m_nMinSwap，也就说明从当前状态继续下去，m_nMinSwap次我们也不能排好所有烙饼。那么，当然就没有必要再继续了。因为继续下去得到的方案不可能比我们已经找到的好。
显然，如果nEstimate越大，剪枝条件越容易被满足。而这正是我们希望的。
结合上面两点，我们希望UpperBound越小越好，而下界（LowerBound）越大越好。假设如果有神仙指点，你只要告诉神仙你当前的状态，他就能告诉你最少需要多少次翻转。这样的话，我们可以花费O（N2）的时间得到最优的方案。但是，现实中，没有这样的神仙。我们只能尽可能地减小UpperBound，增加LowerBound，从而减少需要搜索的空间。
利用上面的程序，做一个简单的比较。
对于一个输入，10个烙饼，从上到下，烙饼半径分别为3, 2, 1, 6, 5, 4, 9, 8, 7, 0。对应上面程序的输入为：
10
3 2 1 6 5 4 9 8 7 0
如果LowerBound在任何状态都为0，也就是我们太懒了，不想考虑那么多。当然任意状态下，你至少需要0次翻转才能排好序。这样，上面的程序Search函数被调用了575 225 200次。
但是如果把LowerBound稍微改进一下（如上面程序中所计算的方法估计），程序则只需要调用172 126次Search函数便可以得到最优方案：
6
4 8 6 8 4 9
程序中的下界是怎么估计出来的呢？
每一次翻转我们最多使得一个烙饼与大小跟它相邻的烙饼排到一起。如果当前状态n个烙饼中，有m对相邻的烙饼它们的半径不相邻，那么我们至少需要m次才能排好序。
从上面的例子，大家都会发现改进上界和下界，好处可不少。我想不用多说，大家肯定想继续优化上界和下界的估计吧。
除了上界和下界的改进，还有什么办法可以提高搜索效率吗？如果我们翻了若干次之后，又回到一个已经出现过的状态，我们还值得继续从这个状态开始搜索吗？我们怎样去检测一个状态是否出现过呢？
读者也许不相信，比尔盖茨在上大学的时候也研究过这个问题，并且发表过论文。你不妨跟盖茨的结果 比比吧。
扩展问题
1. 有一些服务员会把上面的一摞饼子放在自己头顶上（放心，他们都戴着洁白的帽子），然后再处理其他饼子，在这个条件下，我们的算法能有什么改进？
2. 事实上，饭店的师傅经常把烙饼烤得一面非常焦，另一面则是金黄色。这时，服务员还得考虑让烙饼大小有序，并且金黄色的一面都要向上。这样要怎么翻呢？
3. 有一次师傅烙了三个饼，一个两面都焦了，一个两面都是金黄色，一个一面是焦的，一面是金黄色，我把它们摞一起，只能看到最上面一个饼的上面，发现是焦的，问最上面这个饼的另一面是焦的概率是多少？
4. 每次翻烙饼的时候，上面的若干个烙饼会被翻转。如果我们希望在排序过程中，翻转烙饼的总个数最少，结果会如何呢？
5. 对于任意次序的n个饼的排列，我们可以研究把它们完全排序需要大致多少次翻转，目前的研究成果是：
（1） 目前找到的最大的下界是15n/14，就是说，如果有100个烙饼，那么我们至少需要15×100/14= 108次翻转才能把烙饼翻好--而且具体如何翻还不知道。
（2） 目前找到的最小的上界是（5n + 5）/3，对于100个烙饼，这个上界是169。
（3） 任意次序的n个烙饼反转排序所需的最小反转次数被称为第n个烙饼数，现在找到的烙饼数为：
N
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
Pn
|
0
|
1
|
3
|
4
|
5
|
7
|
8
|
9
|
10
|
11
|
13
|
14
|
15
|
？
|
第14个烙饼数P14还没有找到，读者朋友们，能否在吃烙饼之余考虑一下这个问题？
http://cstriker1407.info/blog/the-beauty-of-the-programming-reading-notes-pancakes-scheduling-problems/
解法1，每次翻转最大的张：
Same c code here:
http://www.acmerblog.com/pancake-sorting-6057.html
private static final int[] UnSortArr = {1,5,3,4}; |
public static int getMaxSortNum() |
LinkedList<Integer> middleList = new LinkedList<Integer>(); |
for (int item : UnSortArr) |
System.out.println("未排序：" + middleList.toString()); |
int totalNum = middleList.size(); |
int numNoSort = totalNum; |
int maxNum = Collections.max( middleList.subList(0, numNoSort)); |
int maxNumIdx = middleList.indexOf(maxNum); |
Collections.reverse( middleList.subList(0, maxNumIdx + 1) ); |
System.out.println("找到最大数["+ maxNum +"]并翻转：" + middleList.toString()); |
Collections.reverse( middleList.subList(0, numNoSort) ); |
System.out.println("将最大数翻到底部：" + middleList.toString()); |
System.out.println("总数:"+ totalNum +" 翻转次数为：" + reverseTime); |
通过枚举方法来获取最小的数目：
使用递归的方法，在上一次翻转的基础上进行二次翻转：
for (int i = 0; i < middleList.size(); i++) |
Collections.reverse( middleList.subList(0, i + 1) ); |
internalSort(middleList, times + 1); |
Collections.reverse( middleList.subList(0, i + 1) ); |
为了加速计算，减少不必要的递归，我们计算出翻转次数的上下限。（下限是估计出来的）
public static int getMinSortNum() |
for (int i = 1; i < UnSortArr.length; i++) |
if (UnSortArr[i] - UnSortArr[i-1] == 1 || UnSortArr[i] - UnSortArr[i-1] == -1) |
Java code:
http://blog.csdn.net/kabini/article/details/2276723
书中给出的递归算法或称之为分支限界法（即遍历+剪枝=分支限界）秉承了递归算法传统的简单、明了，但效率偏低的特点。这个问题的实质，我们在每一次反转之前其实是需要做出一种选择，这种选择必须能够导致全局最优解。递归算法就是递归的构建所有解（实际是一颗搜索树），并在遍历过程中不断刷新LowerBound和UpperBound，以及当前的最优解（剪枝），并最终找到一个最整体优解。在这种策略下，提高算法的效率只能寄希望于剪枝方法的改进。但是这种方法显然不是多项式时间的，有没有多项式时间的算法呢？
书中P22页提到动态规划，但最后却给出了解决最优化问题普遍适用但效率可能是最差的递归方法。这不禁让人疑惑：这也不美啊！？如果我们能证明该问题满足动态规划或贪心算法的使用条件，解决问题的时间复杂度将会降到多项式时间甚至N^2。但书中提到动态规划却最终没有使用，又没有讲明原因，我觉得是一种疏失（应该不算错误）。那我们就来想一下为什么没有动态规划或贪心算法的原因。
我们知道动态规划方法是一种自底向上的获取问题最优解的方法，它采用子问题的最优解来构造全局最优解。利用动态规划求解的问题需要满足两个条件：即（1）最优子结构 （2）子结构具有重叠性。条件（1）使我们可以利用子问题的最优解来构造全局最优解，而条件（2）是我们在计算过程中可以利用子结构的重叠性来减少运算次数。此外，《算法导论》上还以有向图的无权最短路径和无权最长路径为例提出条件（3）子问题必须独立。
首先我们假定烙饼问题存在优化子结构。假如我们有N个烙饼，把他们以其半径由小到大进行编号。优化子结构告诉我们对于i个烙饼，我们只需要先排列前(i-1)个，然后再将第i个归位；或先排列第2到i个，最后将第一个归位；又或是找到一个位置k[i<=k<j]像矩阵乘法加括号那样，使得我们先排列前k个，再排列后j-k个，最后再将二者合并，以找到一个最佳翻转策略等等...
根据动态规划算法的计算过程，我们需要一个N*N矩阵M，其中M[i][j]表示将编号i至编号j的烙饼排序所需要的翻转次数。但我们真的能从M[0][0..j-1]和M[1][j+1]，或与M[i][j]同行同列的值来计算M[i][j]吗？如果能，我们就能获得多项式时间的算法。
我们来看书中给出的例子：(顶端)3，2，1，6，5，4，9，8，7，0(底端)，我们最终的目标是计算M[0][9]。
这里我们以计算M[0][4]为例，计算的矩阵我已经在下面给出：
0 1 2 3 4 5 6 7 8 9
------------------------
0|0 1 (1){1}[？]
1| 0 1 (1){1}
2| 0 1 (1)
3| 0 0
4| 0
------------------
实际上如果我们要向将0-4号烙饼(注意：烙饼编号也等同于其半径)排为正序(中间有其他烙饼也没关系)，按照程序给出的结果， 我们需要进行3次翻转，分别为[2,5,9](即分别翻转队列中第二(从零开始)、五、九个烙饼，这里的数字不是烙饼的编号)：
[1] [2] [3] 6 5 [4] 9 8 7 [0]
[4] 5 6 [3] [2] [1] 9 8 7 [0]
[0] 7 8 9 [1] [2] [3] 6 5 [4]
我们知道，该矩阵中每一个数的背后都隐含着一个烙饼的排列，例如M[0][4]就应该对应0,7,8,9,1,2,3,6,5,4
所以，每一个M[i][j]的选取都蕴含着其子排列的顺序的变化。
在计算M[i][j]的时候，我们需要计算i-j号饼的全部划分(不包括全部为1的划分)所能构成的翻转结构，并取其翻转 次数最少的哪一个最为M[i][j]的最终值。例如，我们在计算M[0][4]的时候，需要查看：
/**先将0和1-4号分别排序，最后将二者合并为有序所需要的翻转次数*/
M[0][0],M[1][4]
/** 同上 */
M[0][1],M[2][4]
/** 同上 */
M[0][2],M[3][4]
/** 同上 */
M[0][3],M[4][4]
/* 先将0、1、2、3-4号分别排序，最后将4者合并为有序所需要的翻转次数.
* 注意这里又包含将4个分组再次进行划分的问题！
*/
M[0][0],M[1][1],M[2][2],M[3][4]
.....//中间略
M[0][3],M[4][4]
如果再加上运算过程中我们可以淘汰超过最大反转次数的方案（剪枝？），我们完成全部的运算，所经历的运算过程的时间复杂度已经不是多项式时间的，而是和先前所说的递归方法已没什么两样。
造成这种现象的原因是：某个子问题的最优解不一定是整体的最优解，所以我们在处理整个问题的时候，需要遍历所有可能的子问题，并计算它到整体问题所消耗的代价，才能最终作出有利于整体问题的选择。
所以我们一开始的假设，即烙饼问题有优化子结构的假设是错误的。因此我们不能用动态规划，同理也不能用贪心算法。
但说到每一步的“选择”问题，我记得算法导论上有一个叫做“A*”的算法，它的思想是在进行每一步选择的时候都“推算”最终可能需要的代价，并选择当前代价最小的分支进行遍历。这个“推算”的结果可能不会是最终的代价，而只是作为分支选择的依据。如果谁有兴趣就做一下吧 :-)
Java code:
http://m.blog.csdn.net/blog/Lakers_KobeBryant/8209372
public class CakeTuneProblem {
public static int max;//记录所需要翻转的最少次数
public static int estimateMin;//记录所需要翻转的最少次数
public static int minNum;//记录所需要翻转的最少次数
public static int[] cakeArray;//饼的数组序列
public static int[] resultArray;//饼的数组序列
public static int[] tempArray;//饼的数组序列
public static int count = 0;
//烙饼当前状最少翻转次数
public static int lowBound(int[] cakeArray){
int reduce = 0;
int min = 0;
for(int i = 0; i < cakeArray.length-1; i++){
reduce = cakeArray[i] - cakeArray[i+1];
if(reduce == 1 || reduce == -1){
}
else{
min++;
}
}
return min;
}
//翻转函数，将0-index翻转
public static void reverse(int[] cakeArray, int index){
int i = 0;
int j = index;
int temp;
while(i < j){
temp = cakeArray[i];
cakeArray[i] = cakeArray[j];
cakeArray[j] = temp;
i++;
j--;
}
}
//判断翻转结果是否达到要求
public static boolean isSorted(int[] cakeArray){
for(int i = 1; i < cakeArray.length; i++){
if(cakeArray[i-1] > cakeArray[i]){
return false;
}
}
return true;
}
//翻转主函数，递归求翻转过程，实际上是一棵搜索树
public static void search(int[] cakeArray, int depth){
count++;
estimateMin = lowBound(cakeArray);
//减支函数
if((depth + estimateMin) > max){
return;
}
if(isSorted(cakeArray)){
if(max > depth){
max = depth;
resultArray = tempArray;
System.out.println("当前最少翻转次数cur_min = " + max);
for(int i = 1; i <= max; i++){
System.out.print(resultArray[i]+1 + " ");
}
System.out.println();
}
return;
}
for(int i = 1; i < cakeArray.length; i++){
if(depth != 0 && tempArray[depth] == i){
continue;
}
reverse(cakeArray,i);
tempArray[depth + 1] = i;
search(cakeArray,depth+1);
reverse(cakeArray,i);
}
}
}
编程之美 烙饼问题 java实现（检测状态是否出现过）
private int [] med_cookies_states= {3,2,1,6,5,4,9,8,7,0};
* 记录状态是否搜索过
* 使用hashMap来作为state的key值，value 为该状态下所经历的step
* 如果当前状态的step值比hashmap中的小，则不需要剪掉这个分支
* @param med_cookies_states
* @param step
* @return
*/
public boolean isUnSearch(int [] med_cookies_states,int step){
String temp="";
for(int i=0;i< cookie_cnt;i++){
temp+=String.valueOf(med_cookies_states[i]);
}
if(searchStates.get(temp)==null){
searchStates.put(temp, step);
return true;
}else{
if(searchStates.get(temp) >step){
searchStates.put(temp, step);
return true;
}else{
return false;
}
}
}
。由此我们可以知道，2N的所有质因子组共有(j+1) (k+1)…组。由于当x等于2N时，y等于1，此时的连续自然数个数为1，小于2，所以满足条件的连续自然数序列个数为：(j+1) (k+1)…-1，这就回答了问题一，我们可以首先获得2N的所有质因子分解，然后组合质因子并满足x>y即可获得所有的序列。
