Tower of Hanoi Recursive?

Page 1 of 1

9 Replies - 12311 Views - Last Post: 07 September 2010 - 08:29 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=188687&amp;s=26cda66577658df11f14ac65109c786b&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#1 musiliu

Reputation: 9
• Posts: 110
• Joined: 04-December 09

Tower of Hanoi Recursive?

Posted 01 September 2010 - 06:08 PM

the professor actually said the whole point of the assignment was to familiarize with the Java language and with object oriented programming,

```Pseudocode:
main(){
char fromPeg = 'A';
char withPeg = 'B';
char toPeg = 'C';
solveHanoi(disks, fromPeg, toPeg, withPeg);
//disks= user input;
}

solveHanoi(int disks, fromPeg, toPeg, withPeg){
if (disks >= 1) {
solveHanoi(disks-1, fromPeg, withPeg, toPeg);
moveDisk(fromPeg, toPeg);
solveHanoi(disks-1, withPeg, toPeg, fromPeg);
}
}

moveDisk(fromPeg,toPeg){
System.out.println("move" + fromPeg + "to" + toPeg);
}

```

after about 2 hours of piece of paper tracing out the recursion for only 3 discs, i finally ended up with the discs on the final peg..so you can see recursion is kind of difficult for me..

This post has been edited by musiliu: 02 September 2010 - 04:20 PM

Is This A Good Question/Topic? 0

Replies To: Tower of Hanoi Recursive?

#2 pbl

• There is nothing you can't do with a JTable

Reputation: 8378
• Posts: 31,956
• Joined: 06-March 08

Re: Tower of Hanoi Recursive?

Posted 01 September 2010 - 07:05 PM

After factorial() the Towers of Hanoi is propably the mostly used example to show how recursion works.

Search this forum for Hanoi you will find a lot of examples.
will also provide you with few examples.

As far as your posted code is concerned, disk is neither defined or inputed

#3 musiliu

Reputation: 9
• Posts: 110
• Joined: 04-December 09

Re: Tower of Hanoi Recursive?

Posted 02 September 2010 - 04:18 PM

ok thanks, i think understand the recursion solution now..

but i am not sure how exactly to structure my program to emphasize object oriented programming..

most solutions i see only have one class and one method and main and that's it, but the teacher wants us to use a separate Disk class and possibly even more classes and more methods..

so does anyone have some tips or hints on what classes and methods to use to emphasize object oriented programming and how to connect these classes together for this program?

#4 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12298
• Posts: 45,399
• Joined: 27-December 08

Re: Tower of Hanoi Recursive?

Posted 02 September 2010 - 05:03 PM

Rather than just printing the move, go ahead and move Objects. Really, there isn't much to the Disk class. The Peg class could encapsulate a List<Disk>, or better yet a Stack<Disk>, and just provide access to the Stack push() and pop() methods. Then just manage the interactions of the Disks with the Pegs.

Also, Elcric has a good Towers of Hanoi tutorial in C. The syntax might be a little different, but I think you might find it helpful.

#5 musiliu

Reputation: 9
• Posts: 110
• Joined: 04-December 09

Re: Tower of Hanoi Recursive?

Posted 02 September 2010 - 07:09 PM

thanks, but the assignment also requires to print out the disks in each peg after each move.. like:
```                 A                 B                 C
initial          3 2 1
1 from A to C    3 2                                 1
```

and i am not sure how to do that..do i put some kind of constructor in Disk class to initialize the Disk's ID to a number?
and i also am not sure how to keep track of all the disks when i pop and push,,how would i know which disk i am pushing in to a peg? i've never used a data structure in Java before..

#6 musiliu

Reputation: 9
• Posts: 110
• Joined: 04-December 09

Re: Tower of Hanoi Recursive?

Posted 06 September 2010 - 05:33 PM

OK, i've programmed almost everything i think, but I am not sure on these two methods:

```static void solveHanoi(int numberDisks, Peg fromPeg, Peg toPeg, Peg withPeg){
if(numberDisks >= 1){
solveHanoi(numberDisks - 1, fromPeg, withPeg, toPeg);
move(fromPeg, toPeg);
solveHanoi(numberDisks - 1, withPeg, toPeg, fromPeg);
}
}
static void move(Peg fromPeg, Peg toPeg){
//code here
}
```

1. Why do these methods have to be "static"? I tried just "void" but it didn't work. And these methods are located in the "public class" that also includes the "static main" method. (i call these methods inside main)

2. do you recommend me to put these 2 methods into the Peg class? On the plus side, i don't have to make it static and I think this is possible and would probably emphasize object oriented programming, but it seems very unnecessary and it also eliminates the "fromPeg" parameter which makes it even more confusing.. (i would use the fromPeg object to call the methods..so it's confusing..)

This post has been edited by musiliu: 06 September 2010 - 05:37 PM

Reputation: 32
• Posts: 135
• Joined: 21-August 10

Re: Tower of Hanoi Recursive?

Posted 07 September 2010 - 08:38 AM

The two methods need to be static because you are calling them from another static method, in this case

```public static void main(String[] args)
```

To call them as instance methods instead, in main you'll want to create an instance of the object then call the methods directly. For example, if your class is TowersOfHanoi, you'd do something like this:

```public static void main(String[] args) {
TowersOfHanoi toh = new TowersOfHanoi();
// var declarations here
toh.solveHanoi(disks, fromPeg, toPeg, withPeg);
}

```

Don't forget to remove the static keyword from the method.

This post has been edited by javadork: 07 September 2010 - 08:38 AM

#8 musiliu

Reputation: 9
• Posts: 110
• Joined: 04-December 09

Re: Tower of Hanoi Recursive?

Posted 07 September 2010 - 12:59 PM

ok thanks, also

1. i figured out that i could make the solveHanoi() and move() methods static methods in the Peg class.. and then i could call them by using Peg.solveHanoi(), etc.. do you think i should do this?

2. also, on another subject, I have a stack of Disks in my Peg class and it is declared as public..
should i make this stack private instead? if i do, i can't access it outside of the class...should i make methods like getFront() and addDisk() and removeDisk() in the Peg class and keep the stack private?
since the person above said to encapsulate a stack..

#9 musiliu

Reputation: 9
• Posts: 110
• Joined: 04-December 09

Re: Tower of Hanoi Recursive?

Posted 07 September 2010 - 07:42 PM

yeeaaaaahhhhh, i finally finished this program, i can't show the code cause people in my class might cheat, but here is my output for 4 disks:

```run:
Move                   Peg Configuration
A                   B                   C
init                   4 3 2 1
1 from A to B          4 3 2               1
2 from A to C          4 3                 1                   2
1 from B to C          4 3                                     2 1
3 from A to B          4                   3                   2 1
1 from C to A          4 1                 3                   2
2 from C to B          4 1                 3 2
1 from A to B          4                   3 2 1
4 from A to C                              3 2 1               4
1 from B to C                              3 2                 4 1
2 from B to A          2                   3                   4 1
1 from C to A          2 1                 3                   4
3 from B to C          2 1                                     4 3
1 from A to B          2                   1                   4 3
2 from A to C                              1                   4 3 2
1 from B to C                                                  4 3 2 1
BUILD SUCCESSFUL (total time: 0 seconds)
```

man...it took me literally 5 hours to figure out how to format the columns and make everything neat and straight..
after 5 hours of trying to program a very complicated code, i decided to start fresh and figured it out in 10 minutes..

Reputation: 32
• Posts: 135
• Joined: 21-August 10

Re: Tower of Hanoi Recursive?

Posted 07 September 2010 - 08:29 PM

Congrats! A good sense of accomplishment, eh?