预计阅读时间:5 分钟
烧饼排序是个很有意思的实际问题:假设盘子上有n块面积大小不一的烧饼,你如何用一把锅铲进行若干次翻转,让这些烧饼的大小有序(小的在上,大的在下)?...设想一下用锅铲翻转一堆烧饼的情景,其实是有一点限制的,我们每次只能将最上面的若干块饼子同时翻转:
我们的问题是,如何使用算法得到一个翻转序列,使得烧饼堆变得有序?...base case:n == 1时,排序 1 个饼时不需要翻转。
那么,最后剩下个问题,如何设法将某块烧饼翻到最后呢?
其实很简单,比如第 3 块饼是最大的,我们想把它换到最后,也就是换到第n块。...显然,这个结果不是最优的(最短的),比如说一堆煎饼 [3,2,4,1],我们的算法得到的翻转序列是 [3,4,2,3,1,2],但是最快捷的翻转方法应该是 [2,3,4]:
初始状态 :[3,2,4,1...]
翻前 2 个:[2,3,4,1]
翻前 3 个:[4,3,2,1]
翻前 4 个:[1,2,3,4]
如果要求你的算法计算排序烧饼的最短操作序列,你该如何计算呢?