据说是比尔盖茨唯一发表过的论文就是研究这个(其实我觉得没什么可以研究的),也是三星问题,讲的是如何用一只手排序多个大小不一的烙饼,一次抓住最上面的几块饼,把它们颠倒(翻转),让小的在上面大的在下面,然后就是写程序输出这个最优化过程。实际上就是排序问题:“写一个函数按照烙饼算法升序排序数值。”
这个问题书上的分析写得很让人费解,代码也写得很麻烦,所以我决定不看了自己来写。
首先分析下,最简单的思路就是先找到最大那个翻到最上面,然后把所有的整个翻转,最大的就在最下面了。然后最底下是的不管了(因为是最大的),按照以上方法对除去最大的饼进行翻转,找到第二大的饼把它翻到剩余的饼的最下面(也就是最大饼的上面一张,真拗口,下文最大的饼代表当前最大的饼,翻转从XXX饼到XXX饼代表对从XXX饼到XXX饼的整段进行翻转),以此类推,就能排序好了。
...
