#84 - Pancake Sorting

[NickWarm]

英文

There are n pancakes, all of different sizes, that are stacked on top of each other. You are allowed to slip a spatula under one of the pancakes and flip over the whole stack above the spatula. The objective is to arrange the pancakes according to their size with the biggest at the bottom. Figure 2.20 shows an instance of the puzzle for n = 7. Design an algorithm for solving this puzzle and determine the number of flips made by the algorithm in the worst case.

中文

存在n個大小各異的煎餅，他們彼此重疊在一起。允許你用一個平底鏟，將平底鏟塞到其中一個煎餅底下，並把鏟子上面所有的煎餅都翻轉過來。我們的目標是把煎餅按大小順序排列ㄝ使得最大的在最下面，最小的在最上面。圖2.20顯示在n = 7 時該問題的一個例子。請設計一個演算法解決這個謎題，並且得出該演算法在最糟糕的情況下需要的翻轉次數。