Solved

# The Tower of Hanoi problem

Posted on 1998-03-10
390 Views
I need to write a shell script on a Sun system in K-shell that solves the Tower of Hanoi Problem.  It must use a recursive function.  I'm stumped.

Sorry, perhaps I should have elaborated.  I have a sample program written out for this problem.  I have the function already set up and it does call itself.  The problem lies in the fact that it doesn't move the disks in the right order.
0
Question by:KCMSzwak

LVL 3

Expert Comment

most of the recursive function can be replaced by using loops.
0

LVL 32

Expert Comment

Sounds like a homework problem.  How about a hint?

The k-shell provides for function definitions.  So in your script you can define one like:

function blah
{
# Do some stuff
}

So it follows that you can have blah call itself recursively:

function blah
{
# Do some stuff
blah

# Do some more stuff
}

Don't forget that somewhere you have to test whether blah needs to be called again.  Otherwise, you'll just keep calling blah until the computer's memory runs out.
0

Author Comment

Edited text of question
0

LVL 32

Expert Comment

Obviously you've programmed it wrong.  Program it correctly and it's likely to work.  From what you've posted, I don't see that any more definitive help is possible.
0

LVL 4

Expert Comment

Show me your code and I'll try to fix it (I know next to nothing about the ksh, so
I need your syntax first ;-) In pseudo code:

# from, to == 1, 2, 3, size >= 0
function Hanoi(from, to, size) {

if (size) {
Hanoi(from, 6-from-to, size-1);
move(from, to);
Hanoi(6-from-to, to, size-1);
}

kind regards,

Jos aka jos@and.nl

0

Expert Comment

There are also a range of non-recursive solutions to the towers
of hanoi problem. A stack should not be too hard to improvise if
the syntsx is something close to a bourne shell--just use a stack
pointer (i.e. counter) and eval to get the right number of levels
of shell expansion. This probably leaves some values around but
unset fixes that if you want the fineese. [I would be unlikely to
bother myself].
0

Accepted Solution

shivak earned 50 total points
#!/bin/ksh

# A recurssive function to perform the moves
hanoi()
{
if [ \$1 -ne 0 ]
then
hanoi `expr \$1 - 1` \$2 \$4 \$3
echo "Move disk \$1 from peg \$2 to peg \$3"
hanoi `expr \$1 - 1` \$4 \$3 \$2
fi
}

#main program
echo "Enter the number of disks :"
if [ "\$x" -ge 0 ]
then
# Call hanoi to move N disks from peg A to peg C
# using peg B
hanoi \$x A C B
else
echo Its invalid
fi 2>/dev/null

0

## Featured Post

### Suggested Solutions

Unix / Linux grid computing 5 125
sumDigits challenge 9 95
substring method in java 1 79
Hibernate methods 2 58
In this article, I'll describe -- and show pictures of -- some of the significant additions that have been made available to programmers in the MFC Feature Pack for Visual C++ 2008.  These same feature are in the MFC libraries that come with Visual …
Introduction: Database storage, where is the exe actually on the disc? Playing a game selected randomly (how to generate random numbers).  Error trapping with try..catch to help the code run even if something goes wrong. Continuing from the seve…
This video will show you how to get GIT to work in Eclipse.   It will walk you through how to install the EGit plugin in eclipse and how to checkout an existing repository.
Excel styles will make formatting consistent and let you apply and change formatting faster. In this tutorial, you'll learn how to use Excel's built-in styles, how to modify styles, and how to create your own. You'll also learn how to use your custo…