Towers of Hanoi Question
Author |
Message |
whoareyou
![](http://compsci.ca/v3/uploads/user_avatars/21417075244da4bbb33b0ad.png)
|
Posted: 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? |
|
|
|
|
![](images/spacer.gif) |
Sponsor Sponsor
![Sponsor Sponsor](templates/subSilver/images/ranks/stars_rank5.gif)
|
|
![](images/spacer.gif) |
jbking
|
Posted: 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. |
|
|
|
|
![](images/spacer.gif) |
whoareyou
![](http://compsci.ca/v3/uploads/user_avatars/21417075244da4bbb33b0ad.png)
|
Posted: Fri Mar 22, 2013 5:27 pm Post subject: RE:Towers of Hanoi Question |
|
|
I still don't get it . Can you explain in more detail? |
|
|
|
|
![](images/spacer.gif) |
Panphobia
![](http://compsci.ca/v3/uploads/user_avatars/62033050050c6b61548706.png)
|
Posted: 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 |
|
|
|
|
![](images/spacer.gif) |
whoareyou
![](http://compsci.ca/v3/uploads/user_avatars/21417075244da4bbb33b0ad.png)
|
Posted: 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. |
|
|
|
|
![](images/spacer.gif) |
Panphobia
![](http://compsci.ca/v3/uploads/user_avatars/62033050050c6b61548706.png)
|
Posted: 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) |
|
|
|
|
|
![](images/spacer.gif) |
whoareyou
![](http://compsci.ca/v3/uploads/user_avatars/21417075244da4bbb33b0ad.png)
|
Posted: 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? |
|
|
|
|
![](images/spacer.gif) |
Panphobia
![](http://compsci.ca/v3/uploads/user_avatars/62033050050c6b61548706.png)
|
Posted: 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 |
|
|
|
|
|
![](images/spacer.gif) |
Sponsor Sponsor
![Sponsor Sponsor](templates/subSilver/images/ranks/stars_rank5.gif)
|
|
![](images/spacer.gif) |
|
|