• Advertisement
Sign in to follow this  

Towers of Hanoi iterativly

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement