CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 3 of 3
  1. #1
    Join Date
    Apr 2009
    Posts
    16

    Optimal Algorithm (Puzzle 2)

    At a restaurant there is a chef and his job is to cook pancakes. The problem is that he is not a good cook and as a result all the pancakes he creates are of different sizes. Now when the waiter is delivering these to the customers, he rearranges them in such a way so that the smallest one ends up at the top and the largest one at the bottom (smallest to biggest). He uses a spatula to do that. Currently the only thing that he can do to achieve that, is to grab several pancakes from the top and then flip them over so that the top pancake arrives at the bottom of the stack. The waiter can do this as many times as he wants.

    The problem is to come up with an algorithm that will solve this problem i.e. after doing all that flipping, the pancakes should be sorted (smallest at the top of the stack and largest at the bottom of the stack).

    I am not sure if there is a O (n^2) algorithm for this.

    Thanks.

  2. #2
    Join Date
    Sep 2013
    Posts
    13

    Re: Optimal Algorithm (Puzzle 2)

    Quote Originally Posted by vsha041 View Post
    I am not sure if there is a O (n^2) algorithm for this.
    I don't know if I've misunderstood something but isn't this quite easily done in O(N)?

    You can move a pancake to wherever you want it with just two flips. You insert the spatel underneath the pancake you want to move and flip over. This pancake is now at the top. Then you insert the spatel to where you want to move the top pancake and flip over and it's in the wanted place. Lets call this a 2-flip.

    Now to achieve the wanted order you start with the biggest pancake and 2-flip it to the bottom (if it's not already there). Then you continue with the second biggest pancake and 2-flip it to above the biggest pancake. Etcetera.

    If N is the number of pancakes they can be given any order with N 2-flips at the most and that's O(N).
    Last edited by dazzle; September 19th, 2013 at 01:14 AM.

  3. #3
    Join Date
    Apr 2009
    Posts
    16

    Re: Optimal Algorithm (Puzzle 2)

    Thanks for the assistance dazzle.

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured