Thread: Towers of Hanoi are ........ing me off

  1. #1
    Registered User
    Join Date
    Dec 2009
    Posts
    6

    Towers of Hanoi are ........ing me off

    Hi, I made the recursive solution for the ToH problem, but I can't wrap my head around the iterative version.
    I can't use vectors etc, just integer arrays or structs. Teacher gave me some clues though:

    1. Always move the smallest disc first in a “clockwise” manner.
    2. Then, move the smaller remaining disc onto the the other (which is the only legal move left).
    3. Keep repeating this process.

    I've been busy with the recursive one for almost 2 days, and now this again.. sigh.
    Last edited by bananaHUNT; 12-13-2009 at 01:47 PM.

  2. #2
    Registered User
    Join Date
    Dec 2009
    Posts
    6
    50 views and none is answering..
    Last edited by bananaHUNT; 12-13-2009 at 02:08 PM.

  3. #3
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    First: no one guaranteed any answer!

    I think you had code up earlier, but it was long. This sometimes deters people from helping (as it did when I looked earlier). I would suggest you post code, though minimal code to show what youve done. Its probably a good idea to not put all of your code if its long (as it was earlier)--just post enough to explain what youve got or enough to reproduce an error/warning/other problem. If you dont post any code or pseudocode/english description of what youve attempted, then your even less likely to get help.

    Any recursive function can be implemented as an iterative function, and vice versa. This has been proven. So dont give up as there is a solution!

    The hints given are pretty good. Start with a completely new file and try and understand then implement the hints. Dont try and implement anything if you dont understand it--it will only bring more confusion.

  4. #4
    Registered User
    Join Date
    Dec 2009
    Posts
    6
    ----
    Last edited by bananaHUNT; 12-13-2009 at 06:44 PM.

  5. #5
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    Quote Originally Posted by nadroj
    I think you had code up earlier, but it was long. This sometimes deters people from helping (as it did when I looked earlier)
    Quote Originally Posted by nadroj
    The hints given are pretty good. Start with a completely new file and try and understand then implement the hints.
    It seems youve ignored both of my suggestions. If your confused, its because your trying to convert your existing recursive solution to an iterative one, which is probably hard to do. You arent working on a recursive approach anymore, your re-doing the solution using an iterative approach. Start over. Ignore what youve done for the recursive one, look at the hints which I think are pretty good, and give it a shot. Post your attempt at the iterative approach and let us know when your stuck.

    EDIT: Also, the code youve given and suggested we look at call functions that you havent included, so we dont know what it does. I wouldnt look at it even if you did post it. Though maybe others would, of course. Dont take anything personal if Im sounding harsh, because Im not trying to. Hopefully you understand, given that Ive already attempted to help and youve apparently completely ignored it. Should I spend more time "helping"?
    Last edited by nadroj; 12-13-2009 at 05:46 PM.

  6. #6
    Registered User
    Join Date
    Dec 2009
    Posts
    6
    I'm sorry for ignoring your advice, I just don't know where to begin, so starting from my recursive code seems logical.

    Ok, I would guess you would have to transfer first the smallest disc, and then make the only move that is possible. And keep switching this. But you also have to switch the rotation of the transfer in the process. And stop the program when all discs are in order. Would it be good to use structs or integer arrays?

  7. #7
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    If you are using, say, n discs and t towers, then have t arrays, each of length n. So say theres 5 discs and 3 towers, create 3 int arrays, each of length 5. Initialize one of the towers to have values that are decreasing, say 5 down to 1 or 4 down to 0 (which might make understanding things easier, since the arrays are 0 based and go from 0 to 4). If a disc is on a tower, its position in the tower is the same as its index, any other values are, say, -1 or whatever. If you need to keep track of how many discs are on each tower you could even use the 1st element (index [0]) to store how many discs are there. This way you dont have to work with the discs being 0-based, just worry about indices 1-5, and 0 is, again how many on that tower (if you need this).

    And keep with the given hints:
    1. Always move the smallest disc first in a “clockwise” manner.
    2. Then, move the smaller remaining disc onto the the other (which is the only legal move left).
    3. Keep repeating this process.
    So the very first iteration has no choice but to move tower1[5] (last disc which is the smallest because its on top) to, say, tower2[1] (if doing 1-based, as described above). Then, again your only option is to move tower1[4] to tower3[1].

    Dont overcomplicate things with tons of functions, variables, structs (dont really need any structs, I dont think), and tons of arguments to any functions. Since this is an iterative approach, you shouldnt need many functions.
    Last edited by nadroj; 12-13-2009 at 06:23 PM.

  8. #8
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    I think the best thing to do is to ignore programming (or at least that specific to any language, say C++). Grab a piece of paper, or better yet, the TOH puzzle itself! And try and work on the mechanical details that you as a person would do to solve this. Try and formalize what your doing. Then take this and transfer it to C++. The programming part is the easiest part of any problem.

  9. #9
    Registered User
    Join Date
    Dec 2009
    Posts
    6
    Code:
        int y ( 1 );
        int x = 2^discs;
        for ( int i = 1 ; i < x ; i++ )
        {
            if ( i & 1 )
            {
                if ( y == 3 )
                {
                    gold_discs--;
                    copper_discs++;
                    copper_rod [ copper_discs ] = 1;
                    y = 2;
                }
                else
                {
                    if ( y == 1 )
                    {
                        copper_discs--;
                        silver_discs++;
                        silver_rod [ silver_discs ] = 1;
                        y = 3;
                    }
                    else
                    {
                        silver_discs--;
                        gold_discs++;
                        gold_rod [ gold_discs ] = 1;
                        y = 1;
                    }
                }
            }
            else
            {
                make only legal move left;
            }
        }
    I think I've got the algorithm in my head, is this about right?
    On odd moves you set the lowest disc to A -> B -> C -> A -> .. and on the even moves you make the only legal move possible. But how could I check for that?
    Last edited by bananaHUNT; 12-13-2009 at 06:37 PM.

  10. #10
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    Hmm.. interesting. I dont have time to really think about it, Ive only been giving you some high-level hints. I must do my work now and hopefully someone can give you their time. Good luck (this isnt a reply to scare you off). You seem to be getting somewhere without my help anyway.

  11. #11
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    int x = 2^discs;
    No time to dive into the logic of your program, but please note that ^ in C-style languages is bitwise xor, not exponentiation. To get "2 to the power of" you can use bit shifts.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  12. #12
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    This has been addressed quite a few times on these forums. I am sure something below should strike your fancy!

    C Board - Search Results

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Iterative Towers of Hanoi
    By Mister C in forum C++ Programming
    Replies: 10
    Last Post: 04-11-2009, 01:11 AM
  2. towers of hanoi - what is wrong with this code?
    By kanesoban in forum C Programming
    Replies: 4
    Last Post: 09-17-2007, 01:20 PM
  3. Towers of Hanoi (need help)
    By Loudan in forum C++ Programming
    Replies: 3
    Last Post: 01-30-2006, 10:17 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