Pancake fipping A stack of n pancakes is placed in front of you. You have a spat
ID: 3671595 • Letter: P
Question
Pancake fipping
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 rst 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 algorithm for this problem, where eciency 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. Next, reduce that bound a little more if you can.
Explanation / Answer
In simple terms, the following two steps are enough to be called an algorithm to sort a stack of pancakes through flipping:
1. Find the largest out of order pancake and flip it to the bottom.
2. Repeat the step until the stack is ordered.
By following this algorithm we one by one place the largest element at the end and reduce the size by one.
Algorithm:
Let given array be arr[] and size of the array be n.
Start from the current size equal to n and reduce current size by one while it is greater than one. Let the current size be curr_size. Do following for every curr_size
a) Find index of maximum element in arr[0...curr_size-1]. Let the index be mi.
b) Call flip(arr,mi)
c) Call flip(arr, curr_size-1)
The above algorithm takes a total of O(n) flip operations.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.