1.2《中国象棋将帅问题》解法一和最后一个代码使用位段的方法，有一些投机取巧的成分。因为题目要求是使用1个变量，而不是一个字节，使用位段和定义结构体从思想上并没有什么分别。显然根据使用1个变量的要求，倒数第二段代码是最符合题意的，其实是利用了9进制的思想，将一个两位的九进制变量每一位分别处理，值得借鉴和学习。
1.3《一摞烙饼的排序》刚开始提供了动态规划的思路，但是DP却不能提供最优的解法，假设我们把烙饼大小局部有序作为子问题，我们不能把子问题的最优解作为整个问题的最优解。为什么不能用动态规划？某个子问题的最优解不一定是整体的最优解，所以我们在处理整个问题的时候，需要遍历所有可能的子问题，并计算它到整体问题所消耗的代价，才能最终作出有利于整体问题的选择。
这里参考可能是作者之一的博客：点击打开链接
言归正传，一摞烙饼问题其实是一个很有意思的问题，它的描述是让一摞随机顺序的烙饼通过单手翻转的方式进行排序，以达到这摞烙饼由小到大顺序放置在盘子上的目的，其特点是每次翻转都会导致第一个烙饼到所要反转的那个烙饼之间的顺序变为逆序。我们的目的是求出次数最少的翻转方案以及翻转次数，很显然这是一个最优化问题，我们本能想到的是动态规划、贪心以及分支限界三种方法。
书中给出的递归算法或称之为分支限界法（即遍历+剪枝=分支限界）秉承了递归算法传统的简单、明了，但效率偏低的特点。这个问题的实质，我们在每一次反转之前其实是需要做出一种选择，这种选择必须能够导致全局最优解。递归算法就是递归的构建所有解（实际是一颗搜索树），并在遍历过程中不断刷新LowerBound和UpperBound，以及当前的最优解（剪枝），并最终找到一个最整体优解。在这种策略下，提高算法的效率只能寄希望于剪枝方法的改进。但是这种方法显然不是多项式时间的，有没有多项式时间的算法呢？
书中P22页提到动态规划，但最后却给出了解决最优化问题普遍适用但效率可能是最差的递归方法。这不禁让人疑惑：这也不美啊！？如果我们能证明该问题满足动态规划或贪心算法的使用条件，解决问题的时间复杂度将会降到多项式时间甚至N^2。但书中提到动态规划却最终没有使用，又没有讲明原因，我觉得是一种疏失（应该不算错误）。那我们就来想一下为什么没有动态规划或贪心算法的原因。
我们知道动态规划方法是一种自底向上的获取问题最优解的方法，它采用子问题的最优解来构造全局最优解。利用动态规划求解的问题需要满足两个条件：即（1）最优子结构 （2）子结构具有重叠性。条件（1）使我们可以利用子问题的最优解来构造全局最优解，而条件（2）是我们在计算过程中可以利用子结构的重叠性来减少运算次数。此外，《算法导论》上还以有向图的无权最短路径和无权最长路径为例提出条件（3）子问题必须独立。
理解了作者的思路，参考代码，写出实现并不难。可以视为从顶上的第一个烙饼开始，不断尝试去翻，遇到边界条件则返回，如果不成功则撤销上一步翻饼的操作，继续尝试翻下一个烙饼。上C代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static int nCakeNum;
static int nMaxSwap;
int *TempCakeArray; /* current cake sort */
int *LeastReverseArray; /* store the reverse step */
int *TempReverseArray; /* store the temp reverse step */
/* max swap count for current sort
* to minimize the swap count
*/
int FindUpperBound(int nCakeCnt)
{
return 2*(nCakeCnt - 1);
}
/* least swap count for current sort
* to minimize the swap count
*/
int FindLowerBound(int *pCakeArray, int nCakeCnt)
{
int i, temp;
int ret = 0;
for(i = 1; i < nCakeCnt; i++)
{
temp = pCakeArray[i] - pCakeArray[i-1];
if((temp != 1) && (temp != -1))
{
ret++;
}
}
return ret;
}
/* check if the cakes are sorted */
#define CAKE_NOT_SORTED 0
#define CAKE_SORTED 1
int IsSorted(int *pCakeArray, int nCakeCnt)
{
int i;
for(i = 1; i < nCakeCnt; i++)
{
if(pCakeArray[i] < pCakeArray[i - 1])
return CAKE_NOT_SORTED;
}
return CAKE_SORTED;
}
/* swap cake */
void Reverse(int nBegin, int nEnd)
{
int i, j;
int temp;
/* ASSERT(nBegin < nEnd); remember to check the value all the time */
for(i = nBegin, j = nEnd; i < j; i++, j--)
{
temp = TempCakeArray[i];
TempCakeArray[i] = TempCakeArray[j];
TempCakeArray[j] = temp;
}
}
void Search(int step)
{
int i;
int nEstimate;
nEstimate = FindLowerBound(TempCakeArray, nCakeNum);
if(nEstimate + step > nMaxSwap)
return;
if(IsSorted(TempCakeArray, nCakeNum) == CAKE_SORTED)
{
if(step < nMaxSwap)
{
nMaxSwap = step; /* minimize the upper bound */
for(i = 0; i < nMaxSwap; i++)
LeastReverseArray[i] = TempReverseArray[i];
}
return;
}
for(i = 0; i < nCakeNum; i++)
{
Reverse(0, i);
TempReverseArray[step] = i;
Search(step + 1);
Reverse(0, i);
}
}
/* print the result */
void PrintSortSteps()
{
int i;
printf("The least swap steps is %d.\nThe details:\n", nMaxSwap);
for(i = 0; i < nMaxSwap; i++)
printf("%d\t", LeastReverseArray[i]);
printf("\n");
return;
}
int main()
{
int i;
int CakeArray[] = {3, 2, 1, 6, 5, 4, 9, 8, 7, 0};
nCakeNum = sizeof(CakeArray)/sizeof(int);
TempCakeArray = malloc(nCakeNum * sizeof(int));
if(TempCakeArray == NULL)
return -1;
for(i = 0; i < nCakeNum; i++)
TempCakeArray[i] = CakeArray[i];
nMaxSwap = FindUpperBound(nCakeNum);
TempReverseArray = malloc(nMaxSwap * sizeof(int));
if(TempReverseArray == NULL)
return -1;
memset(TempReverseArray, 0, nMaxSwap * sizeof(int));
LeastReverseArray = malloc(nMaxSwap * sizeof(int));
if(LeastReverseArray == NULL)
return -1;
memset(LeastReverseArray, 0, nMaxSwap * sizeof(int));
Search(0);
PrintSortSteps();
return 0;
}