Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A qustion in stacks

  1. Feb 16, 2008 #1
    i have two stack S1 and S2 the total amount of objects
    in them is "n"
    in both stack all the objects are sorted in accending order

    (the biggest number is on top the smallest number is on the bottom)

    and thats the way it goes in both stacks

    the question asks me to build a method which
    puts all of the objects from stacks S1 and S2 into stack S3
    in accended order plus we have to accomplish this using 4n-4 moves ??
    (the biggest number is on top the smallest number is on the bottom)

    i tried to solve that by
    flipping the stacks using the S3 so they will be sorted from the smallest
    to the biggest
    taking two templorary variables pop each object from each stack
    into the temporary variable
    and then we compare them and the smallest goes to S3
    and the other one waits till we have an object from the other stack which is smaller than him,
    and then we have to flip S3 in order have the biggest on top
    also i tried using TOP commang but i found out that
    its implementation also has push and pop in it.
    but in that way we have more than 4n-4 moves
  2. jcsd
  3. Feb 21, 2008 #2
    This is the http://en.wikipedia.org/wiki/Tower_of_Hanoi" [Broken] Problem if I am not mistaken. This should get you started.
    Last edited by a moderator: May 3, 2017
  4. Feb 26, 2008 #3
    a. Move S1 to S3 = S1'
    b. Move S2 to S1 = S2'.
    c. Move S3 to S2 = S1.
    *the two stacks are exchanged and (their) one order reversed in 3n/2 moves.
    d. now you can continue.

    hint: repeat a.b,c to have 6n/2 moves.
    Last edited: Feb 26, 2008
  5. Feb 26, 2008 #4

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    This along requires 2n operations. Not a good start. Not only that, you will have to reverse the temporary stack at the end, costing another 2n operations. You have already exceeded the budget with this approach and you haven't even started building the temporary stack. Solution: build the temporary stack in reverse order.
    You don't have to do this to the bitter end. You can save some operations by avoiding putting all of the elements on the temporary stack. At some point you will have emptied both stacks, leaving you with two elements in the temporary variables and n-2 elements in the temporary stack. Why not put the two temporary variables directly where they belong instead?

    It helps to think of invariants, if you have been taught that concept.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook