Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Towers of Hanoi Question
Index -> General Programming
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
whoareyou




PostPosted: Fri Mar 22, 2013 4:12 pm   Post subject: Towers of Hanoi Question

Hello,

I've been looking through the solution to the Towers of Hanoi problem for a long time, and even tracing the function using the call stack output on http://www.cs.cmu.edu/~cburch/survey/recurse/hanoiex.html.

I understand the first call, MoveTower(5, A, B, C), but in the second call and the calls thereafter, the destination and temporary peg switch. Why is this?
Sponsor
Sponsor
Sponsor
sponsor
jbking




PostPosted: Fri Mar 22, 2013 5:16 pm   Post subject: Re: Towers of Hanoi Question

Because to make that move requires one to make other moves first. Remember the rules of which disks can be moved and when.
whoareyou




PostPosted: Fri Mar 22, 2013 5:27 pm   Post subject: RE:Towers of Hanoi Question

I still don't get it Sad. Can you explain in more detail?
Panphobia




PostPosted: Sat Mar 23, 2013 1:13 pm   Post subject: Re: Towers of Hanoi Question

move n−1 discs from A to B. This leaves disc n alone on peg A
move disc n from A to C
move n−1 discs from B to C so they sit on disc n
whoareyou




PostPosted: Sat Mar 23, 2013 6:12 pm   Post subject: RE:Towers of Hanoi Question

I still can't see why the destination and temporary pegs keep switching.
Panphobia




PostPosted: Sat Mar 23, 2013 6:54 pm   Post subject: Re: Towers of Hanoi Question

Java:
public static void Towers(int n, int from, int to, int temp){
        if(n==0)return;
        Towers(n-1,from,temp,to);
        System.out.println("Move top disc from "+from+" to "+to);
        Towers(n-1,temp,to,from);
    }

if you passed Towers(3,1,2,3);
it would look like this through the output
code:
Move top disc from 1 to 2
Move top disc from 1 to 3
Move top disc from 2 to 3
Move top disc from 1 to 2
Move top disc from 3 to 1
Move top disc from 3 to 2
Move top disc from 1 to 2

and then like this graphically, with the actual pegs
code:
(0)  _|_         |          |
    __|__        |          |
   ___|___       |          |
  ____|____  ____|____  ____|____

(1.1) |          |          |
    __|__        |          |
   ___|___      _|_         |
  ____|____  ____|____  ____|____ (A -> B)

(1.2) |          |          |
      |          |          |
   ___|___      _|_       __|__
  ____|____  ____|____  ____|____ (A -> C)

(1.3) |          |          |
      |          |         _|_
   ___|___       |        __|__
  ____|____  ____|____  ____|____ (A -> C)



(2.1) |          |          |
      |          |         _|_
      |       ___|___     __|__
  ____|____  ____|____  ____|____ (A -> B)



(3.1) |          |          |
      |          |          |
     _|_      ___|___     __|__
  ____|____  ____|____  ____|____ (C -> A)

(3.2) |          |          |
      |        __|__        |
     _|_      ___|___       |
  ____|____  ____|____  ____|____ (C -> B)

(3.3) |         _|_         |
      |        __|__        |
      |       ___|___       |
  ____|____  ____|____  ____|____ (A -> B)
whoareyou




PostPosted: Sat Mar 23, 2013 6:58 pm   Post subject: RE:Towers of Hanoi Question

I realize that the algorithm is actually doing that and I can follow what the algorithm is doing. But my question is WHY is it necessary to switch the destination and temporary pegs. I know that it does it in the algorithm, but why does it make sense to do that?
Panphobia




PostPosted: Sat Mar 23, 2013 7:08 pm   Post subject: RE:Towers of Hanoi Question

Basically, you do not want the exact same peg to keep on having a disc being added to it, that would defeat the purpose of the towers of hanoi, just search on how the Lucas' Tower/Towers of Hanoi is played, you know there are always 2^n-1 amount of moves for the least amount of moves, and to play optimally, what needs to be done? where do the discs need to be put? see if I instead used the function
code:
public static void Towers(int n, int from, int to, int temp){
        if(n==0)return;
        Towers(n-1,from,to,temp);
        System.out.println("Move top disc from "+from+" to "+to);
        w++;
        Towers(n-1,from,to,temp);
    }

with the same values being passed I would get this
code:
Move top disc from 1 to 2
Move top disc from 1 to 2
Move top disc from 1 to 2
Move top disc from 1 to 2
Move top disc from 1 to 2
Move top disc from 1 to 2
Move top disc from 1 to 2
Sponsor
Sponsor
Sponsor
sponsor
Display posts from previous:   
   Index -> General Programming
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 8 Posts ]
Jump to:   


Style:  
Search: