Towers of Hanoi

Discussion in 'OT Technology' started by CanadianCrazy, Feb 16, 2006.

Joined:
Jan 19, 2006
Messages:
562
0
I'm trying to do an assignment and I have NO CLUE how to do this problem. The question is:

Give a nonrecursive algorithm for the Towers of Hanoi problem that uses a Stack ADT to store pending subproblems to be solved. If your solution is over 10 lines long, it is incorrect.

I can write an iterative solution that's longer than 10 lines, I can write one that doesn't use a stack, but I can't get all of the requirements together. Any insights?

Joined:
Jan 19, 2006
Messages:
562
0
Please, I don't want to fail...

Joined:
Jan 19, 2006
Messages:
562
0
not even a pity response?

4. StainMeNowNew Member

Joined:
Jan 19, 2006
Messages:
59
0
There's about a thousand websites on the internet with many different algorithms for this exact problem. Try to google it.

5. StainMeNowNew Member

Joined:
Jan 19, 2006
Messages:
59
0
Oh, and don't wait until the last second to ask for help with you CS projects.

6. FrequencyActive Member

Joined:
Dec 30, 2004
Messages:
7,503
0
Location:
PA
i loved this project, i was assinged it to keep me busy in one of my first year classes

7. MrManNew Member

Joined:
Jul 13, 2004
Messages:
308
0
The towers of hanoi is best solved using a recursive function. But what is a recursive function? It's a function that calls itself, which is just a stack.

| |
| |
| | <-- function calls the same function add to stack
------
STACK

| |
| | <-- function call again, add to stack
|1st |
------
STACK

| |
|2nd| <-- function call again, add to stack
|1st |
------
STACK

|base| <-- base case of function, pop off stack and do something with 2nd call
|2nd|
|1st |
------

| |
|2nd| <-- pop again, do something with 1st.
|1st |
------
STACK

| |
| |
|1st | <-- finish doing something with first, pop off stack. Stop when stack is empty.
------
STACK

Joined:
Nov 13, 2001
Messages:
11,861