据说是比尔盖茨唯一发表过的论文就是研究这个（其实我觉得没什么可以研究的），也是三星问题，讲的是如何用一只手排序多个大小不一的烙饼，一次抓住最上面的几块饼，把它们颠倒（翻转），让小的在上面大的在下面，然后就是写程序输出这个最优化过程。实际上就是排序问题：“写一个函数按照烙饼算法升序排序数值。”
这个问题书上的分析写得很让人费解，代码也写得很麻烦，所以我决定不看了自己来写。
首先分析下，最简单的思路就是先找到最大那个翻到最上面，然后把所有的整个翻转，最大的就在最下面了。然后最底下是的不管了（因为是最大的），按照以上方法对除去最大的饼进行翻转，找到第二大的饼把它翻到剩余的饼的最下面（也就是最大饼的上面一张，真拗口，下文最大的饼代表当前最大的饼，翻转从XXX饼到XXX饼代表对从XXX饼到XXX饼的整段进行翻转），以此类推，就能排序好了。
这个过程我的代码如下：
//交换A，B宏
#define SWAP(A, B, TEMP) (TEMP = A, A = B, B = TEMP)
//全局逆转次数。
int gCount = 0;
//模板形式。
//@param
//gOutput 排序好的输出数组。
//gInput 未排序的输入数组。
//uLength 数组的长度。
template<typename T>
void Sort(T gOutput[], T gInput[], unsigned int uLength)
{
//如果长度少于或等于1就没必要排序了。
if(uLength <= 1)
return;
//找出此时最大的饼。
unsigned int i, uMax = 0;
for(i = 0; i < uLength; i++)
if(gInput[i] > gInput[uMax])
uMax = i;
//当最大的饼在最下面时候就不用排序了
if(uMax != uLength - 1)
{
//帮输入数组复制到输出数组里
if(gOutput != gInput)
memcpy(gOutput, gInput, sizeof(gInput));
T Temp;
unsigned int uHalf;
//如果最大的饼不是在最上面时候翻转从第一个到最大的饼，把最大的饼翻到最上面（最大的饼在最上面时就不用了）。
if(uMax != 0)
{
uHalf = uMax / 2;
for(i = 0; i <= uHalf; i++)
SWAP(gOutput[i], gOutput[uMax - i], Temp);
//翻转次数加1。
gCount ++;
}
//整个翻转，把最大的饼翻到最下面。
uHalf = uLength / 2;
for(i = 0; i < uHalf; i++)
SWAP(gOutput[i], gOutput[uLength - i - 1], Temp);
//翻转次数加1
gCount ++;
}
//递归处理最大的饼之上的饼（最大的饼已经在最下面不用管了）
Sort(gOutput, gOutput, uLength - 1);
}
这个算法已经解决了排序问题，然而实在不幸题目所求的是排序的最优化，即最小次数排序。
这样我们就需要进一步考虑问题了，假设共有4个饼，它们的大小分别为4，1，2，3，0，这段程序的思路是1，3，2，0，4==〉3，1，2，0，4==〉0，2，1，3，4==〉2，0，1， 3， 4==〉1，0，2，3，4==〉0，1，2，3，4，共经过6个翻转过程，如果你试过自己手工排序，就会发现这是一个很愚蠢的方法，因为你发现这4个饼的序列中间一段连续集合{1，2，3}是有序的，翻转时候没必要把它们分开来，按照上面程序的思路先翻转所有的饼（而不是先翻转4，1，2，3——虽然对于此次饼的序列可行，但是和上面的程序脱节了），再翻转0，3，2，1，然后把1，2，3整体翻转（程序这里把1，2，3分开来翻转了），最后把成序列的3，2，1，0翻回去，就排序好了，实际上只须4步就能翻转好了。
由此得出的结论是，以上算法还不是最优解，为什么呢？从以上思路推导可以看出，这段程序并不能检测连续的序列集合进行，排序是只能把集合拆开再一个一个单独排序，假设集合的元素有N个，这样就多消耗N-1次排序。
知道了原因，就可以对代码进行改进了。
改进的目的是让程序能检测连续的序列集合，问题又来了，这个集合是哪里的集合呢？
可以先试着用人脑进行模拟，翻转是针对最大的饼进行的，那么这个集合必定跟最大的饼有关，又知道翻转时候不能从中间分开进行某段翻转，那么可以确定这个集合必定是跟最大的饼连在一起的，那到底是在最大的饼的上面还是下面呢？想象一下，如果是在最大的饼的最上面，当饼翻转过来后，这个集合就被翻到下面了，这样就不能对它进行整段排序了，所以这个也排除掉，于是得出的最终结论是这个集合是在最大的饼的下面，并且跟最大的饼是连在一起的。
下面整理一下思路：先找到最大饼，然后向下找到第一个序列集合的尾（集合里最下面的那个饼），然后翻转从最上面到序列尾，再翻转序列尾（现在是第一个饼）到最大的饼，现在最大的饼在最上面了，按照原程序的思路再整个翻回去再递归（最大饼在最下面然后反复整个步骤直到排序完成——当前需要排序的饼小于等于1个）就行了。
好，下面是最终程序：
//交换A，B宏
#define SWAP(A, B, TEMP) (TEMP = A, A = B, B = TEMP)
//全局逆转次数。
int gCount = 0;
//逆转数组函数，模板形式。
//@param
//gSource 要逆转的数组。
//uLength 数组的长度。
template<typename T>
void Inverse(T gSource[], unsigned int uLength)
{
T Temp;
for(unsigned int i = 0, uEnd = uLength / 2; i < uEnd; i++)
SWAP(gSource[i], gSource[uLength - 1 - i], Temp);
gCount++;
}
//排序函数，模板形式。
//@param
//gOutput 排序好的输出数组。
//gInput 未排序的输入数组。
//uLength 数组的长度。
template<typename T>
void Sort(T gOutput[], T gInput[], unsigned int uLength)
{
//如果长度少于或等于1就没必要排序了。
if(uLength <= 1)
return;
bool bIsDescending = false; //是否降序。
unsigned int i, uMax = 0, uEnd = 0; //尾下标。
//找出此时最大的饼及饼下面第一个连续的序列集合尾下标。
for(i = 0; i < uLength; i++)
{
if(gInput[i] > gInput[uMax])
{
uMax = uEnd = i;
//这个序列集合必定是降序，否则这个饼就不是最大饼。
bIsDescending = true;
}
else if(bIsDescending)
{
//降序结束
if(gInput[i] > gInput[i - 1])
bIsDescending = false;
else
uEnd = i;
}
}
//当最大的饼在最下面时候就不用排序了
if(uMax != uLength - 1)
{
if(gOutput != gInput)
memcpy(gOutput, gInput, sizeof(gInput));
//最大的饼在最上面时就不用了
if(uMax != 0)
{
//如果最大的饼不是在最上面时候翻转从第一个到最大的饼下面连续的序列集合尾。
Inverse<T>(gOutput, uEnd + 1);
if(uEnd != uMax)
//再翻转集合尾（现在是第一个）最大饼，把最大的饼翻到最上面。
Inverse<T>(gOutput, uEnd - uMax + 1);
}
//整个翻转回去，把最大的饼翻到最下面。
Inverse<T>(gOutput, uLength);
}
//递归处理最大的饼之上的饼（最大的饼已经在最下面不用管了）
Sort(gOutput, gOutput, uLength - 1);
}
