Bob is not very good at making pancakes: none of his pancakes turn out the same size. He makes a stack of pancakes with the sizes in random order. It is Shannon's job to order the pancakes by size, with the smallest pancakes on top. However, the only operation she can do is to select some (or all) of the pancakes from the top of the stack and flip them over. After this flip, the top pancake in the selection is now at the bottom of the selection, the bottom pancake in the selection is now on top, and all pancakes in between are in the opposite order. All pancakes below those selected remain where they were.
Write an algorithm that gives Jeff a sequence of instructions of how many pancakes to flip at a time so that, at the end, the pancakes are arranged in order with the smallest on top and the biggest at the bottom. Remember that the only thing Jeff can do is flip the top pancakes at a time, though you can vary Write your algorithm in English and explain how and why it works.
You can label pancakes by size from 1 (smallest) to (largest) to make them easier to refer to.
For example, suppose the pancakes started in this position:
3 1 4 5 9 2 6 8 7
That is, the third-smallest pancake is on top, the smallest pancake is next from the top, and so on.
If you tell Shannon to flip the top 4 pancakes, then the pancakes would be in this position:
5 4 1 3 9 2 6 8 7
Shannon's goal (for this particular example) is to get the stack to finish as:
1 2 3 4 5 6 7 8 9
Important: Your algorithm should not merely work just for this particular example. It should work for any stack of pancakes that are its input, with any number of pancakes.
To demonstrate that your algorithm works, you must also demonstrate that your algorithm solves the 9-pancake example shown above. (Hint: the sample flip that we showed you above is probably not the first step in a successful solution.)
