Public Group

# Towers of Hanoi iterativly

This topic is 4784 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Okay, so I've got this problem in my programming class. I've got to come up with a non-recursive solution to the Towers of Hanoi. I'm getting stumped, I see a vague pattern in how you move the disks, depending on whether it's an odd or an even total. But I'm just not understanding what I need to do exactly. Any help in explaining what I need to do or what direction I need to look in would be much appreciated!

##### Share on other sites
Understand how the recursive process is implemented by the compiler using the stack to store information.

Implement it yourself using a stack and a loop.

##### Share on other sites
Basically you have to do recursion in software

##### Share on other sites
There is an iterative solution which does not require a stack; it's related to the algorithm for Gray coding. Number each disk from smallest to largest, solve a short tower. Write the list of disks moved in each step. Do you see anything periodic about the 1s? What about the 2s? Extend that pattern.

EDIT: If you can use a stack, tho, do. It's a lot simpler.

##### Share on other sites
I do notice a pattern with the order that the pieces move in. it woule be easy enough to extend it indefinetly.

1,2,1,3,1,2,1,4,1,2,1,3,1,2,1 etc. etc.

I'm not sure what I'd need to write, seems like there'd need to be some if statements involved to get things to work right, but that might only be if I wanted to add user interactivity.

Here's another question though...

Can anyone help me understand the logic behind this:

int hanoi(int n, int src, int aux, int dst) {
if (n == 0) {
return 0;
}

hanoi(n-1, src, dst, aux);
cout << n << " " << src << " -> " << dst << endl;
hanoi(n-1, aux, src, dst);

return 1;
}

I put some stops in and tried to follow the logic through the debugger, but I haven't had much luck in following the logic.

I think if I can understand this more clearly I should be able to come up with a solution for the previous problem.

##### Share on other sites
Write down the binary representations of sequential integers (0001, 0010, 0011, etc) next to your list of disks. See if you can identify a correspondence.

1. 1
2. 2
3. 3
Rutin
20
4. 4
5. 5
khawk
14

• 9
• 11
• 11
• 23
• 12
• ### Forum Statistics

• Total Topics
633655
• Total Posts
3013178
×