A stack of n pancakes is placed in front of you. You have a spatula which you ca

Question

A stack of n pancakes is placed in front of you. You have a spatula which you can insert anywhere into the stack and flip over all the pancakes above the spatula. You want to arrange the pancakes in order of their diameter (they are perfectly round), and you want to use as few flips as possible. As an example suppose n = 6, and the pancakes are numbered 1 through 6 in order of their diameter with 1 the smallest and 6 the largest. Suppose the original order is 346215, and the left end of the sequence
represents the top of the stack. In one flip I can get 643215 (by flipping the first three pancakes: 346), then in the next flip 512346, then 432156, then 123456, so four flips are enough in this case. Let F (n) be the worst case number of
flips needed to arrange a stack of n pancakes. Find an efficient (in a worst case sense) algorithm for this problem, where efficiency is measured by the worst case number of flips.
Remember that your algorithm should work for pancakes with any order. To start you off you should easily be able to show that F (n) is at most 2n-2. Next, reduce that bound a little more if you can.

Explanation / Answer

Consider any arbitrary sequence of pancakes. We know that we can move the highest number pancake to the back of the stack in two operations. The first operation bisects the stack immediately after the highest value and moves it to the front. e.g. x ... hi x ... x --> hi ... x x ... x The second operation moves the highest value to the right most position. e.g. hi ... x x ... x --> x ... x x ... hi Once the highest value item is in position for the sequence of length n, we can do the same for the subsequence of length n-1. It is only when we reach the last element that we need to do nothing, because a single element need not be flipped. For sequences of length n, the sorting can be performed in 2n - 2 operations. 2 operations per element of the list with the exception of the last element. Reducing beyond this would be another question.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.