Iterative Towers of Hanoi

This is a discussion on Iterative Towers of Hanoi within the C++ Programming forums, part of the General Programming Boards category; Allright, It is well known what the Towers of Hanoi (TOH) problem is. It is known to have a recursive ...

  1. #1
    CS Author and Instructor
    Join Date
    Sep 2002
    Posts
    511

    Talking Iterative Towers of Hanoi

    Allright,

    It is well known what the Towers of Hanoi (TOH) problem is. It is known to have a recursive solution. I have many programs to demonstrate this. However, I am trying to find a non recursive solution to TOH. I myself have solved this problem in an algorithm analysis class (years ago!) but I cant find my code. Do any of you have a quick solution for this problem.

    Thanks
    Mr. C: Author and Instructor

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >Do any of you have a quick solution for this problem.
    The most straightforward solution is to use a stack to iteratively simulate recursion.

    -Prelude
    My best code is written with the delete key.

  3. #3
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    There is an iterative non stack solution.

  4. #4
    CS Author and Instructor
    Join Date
    Sep 2002
    Posts
    511
    Stacks will work! Thanks
    Mr. C: Author and Instructor

  5. #5
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    int main()
    {
       int n, x;
       printf( "How many disks? " );
       scanf( "%d", &n );
       printf("\n");
       for (x=1; x < (1 << n); x++)
          printf( "move from tower %i to tower %i.\n",
    		 (x&x-1)%3, ((x|x-1)+1)%3 );
    return 0;
    }
    found in 30 secs with google!
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  6. #6
    CS Author and Instructor
    Join Date
    Sep 2002
    Posts
    511
    Thanks- I was trying to use a data structure to solve the problem. A stack is the ideal data structure. Also, your code was in C- doesn't matter though.
    Mr. C: Author and Instructor

  7. #7
    Registered User
    Join Date
    Jan 2002
    Posts
    552
    I wanna be like Stoned_Coder when I grow up!
    C Code. C Code Run. Run Code Run... Please!

    "Love is like a blackhole, you fall into it... then you get ripped apart"

  8. #8
    Registered User
    Join Date
    Jan 2002
    Posts
    552
    >found in 30 secs with google!
    oops, didnt notice that the first time...
    C Code. C Code Run. Run Code Run... Please!

    "Love is like a blackhole, you fall into it... then you get ripped apart"

  9. #9
    Registered User
    Join Date
    Apr 2009
    Posts
    2
    Quote Originally Posted by Stoned_Coder View Post
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    int main()
    {
       int n, x;
       printf( "How many disks? " );
       scanf( "%d", &n );
       printf("\n");
       for (x=1; x < (1 << n); x++)
          printf( "move from tower %i to tower %i.\n",
    		 (x&x-1)%3, ((x|x-1)+1)%3 );
    return 0;
    }
    found in 30 secs with google!
    Hello!
    Sry about diving out so old subject, but i need some answers about that code. Could somebody explane what that printf( "move from tower %i to tower %i.\n",
    (x&x-1)%3, ((x|x-1)+1)%3 ); exactly mean. I can understand that it writes how rings have to move one pole to another pole but i need to know more of that, how that code knows, when but rings in the second or third pole?
    And another questions is, can it works in C too, i mean not only in C++?
    I apologize for my bad English and i going to wait to get some answers .

  10. #10
    Registered User BuzzBuzz's Avatar
    Join Date
    Feb 2009
    Posts
    89
    Quote Originally Posted by tonn View Post

    And another questions is, can it works in C too, i mean not only in C++?

    That is C code.

    %i is the C code way of outputting an integer variable value, in C++ you'd write something like:
    Code:
    C version: printf( "move from tower %i to tower %i.\n"
    
    C++: cout << "move from tower" tower[i] << "to tower" << tower[i] << endl;
    Any help I give may be classified as:
    The Blind leading the Blind...
    Currently working through:
    "C++ Primer Plus"

  11. #11
    Registered User
    Join Date
    Apr 2009
    Posts
    2
    Ok thanks! I deduce that too. But still there is a question about: printf( "move from tower %i to tower %i.\n",
    (x&x-1)%3, ((x|x-1)+1)%3 ); how the rings move on the poles. I think its something to do with bit operations, like in here Tower of Hanoi - Wikipedia, the free encyclopedia Binary solutions subject. But i really cant understand that text its too complicated to me. Could somebody help?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. towers of hanoi - what is wrong with this code?
    By kanesoban in forum C Programming
    Replies: 4
    Last Post: 09-17-2007, 02:20 PM
  2. Towers of Hanoi (need help)
    By Loudan in forum C++ Programming
    Replies: 3
    Last Post: 01-30-2006, 10:17 PM
  3. towers of hanoi problem
    By aik_21 in forum C Programming
    Replies: 1
    Last Post: 10-02-2004, 02:34 PM
  4. Towers of Hanoi, special output.
    By spoon_ in forum C Programming
    Replies: 3
    Last Post: 03-15-2003, 06:08 PM
  5. Towers of Hanoi
    By janehung in forum C Programming
    Replies: 12
    Last Post: 01-07-2002, 06:40 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21