[Carnegie Mellon]Pancakes with a problem
The chef at our place is sloppy: when he prepares pancakes, they come out all different sizes.
When the waiter delivers them to a customer, he rearranges them (so that smallest is on top,and so on, down to the largest at the bottom)
He does this by grabbing several from the top and flipping them over, repeating this (varying the number he flips) as many times as necessary.
eg : Assume pancakes are represented through numbers as :
5 2 3 4 1
Now you have to sort it as 1 2 3 4 5 using only flip operations.How many optimal flip operations required in worst case.
When the waiter delivers them to a customer, he rearranges them (so that smallest is on top,and so on, down to the largest at the bottom)
He does this by grabbing several from the top and flipping them over, repeating this (varying the number he flips) as many times as necessary.
eg : Assume pancakes are represented through numbers as :
5 2 3 4 1
Now you have to sort it as 1 2 3 4 5 using only flip operations.How many optimal flip operations required in worst case.
maximum of 2n-3 flips are required ...In worst case let the initial arrangement of pancakes according to their size be 1,2,3,4,5 and we have to arrange them as 5,4,3,2,1 so we have to search for biggest number and flip it at the position to get largest number at top position and then one more flip to take the largest element at bottom.so maximum of 2n-3 flips are required..please read pancake sorting for more details..
ReplyDelete