C Board  

Go Back   C Board > General Programming Boards > C++ Programming

Reply
 
LinkBack Thread Tools Display Modes
Old 12-13-2009, 06:47 AM   #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.
bananaHUNT is offline   Reply With Quote
Old 12-13-2009, 01:47 PM   #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.
bananaHUNT is offline   Reply With Quote
Old 12-13-2009, 05:26 PM   #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.
nadroj is offline   Reply With Quote
Old 12-13-2009, 05:37 PM   #4
Registered User
 
Join Date: Dec 2009
Posts: 6
----

Last edited by bananaHUNT; 12-13-2009 at 06:44 PM.
bananaHUNT is offline   Reply With Quote
Old 12-13-2009, 05:44 PM   #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.
nadroj is offline   Reply With Quote
Old 12-13-2009, 05:59 PM   #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?
bananaHUNT is offline   Reply With Quote
Old 12-13-2009, 06:20 PM   #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:
Quote:
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.
nadroj is offline   Reply With Quote
Old 12-13-2009, 06:26 PM   #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.
nadroj is offline   Reply With Quote
Old 12-13-2009, 06:32 PM   #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.
bananaHUNT is offline   Reply With Quote
Old 12-13-2009, 06:46 PM   #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.
nadroj is offline   Reply With Quote
Old 12-14-2009, 12:53 PM   #11
Cat without Hat
 
CornedBee's Avatar
 
Join Date: Apr 2003
Posts: 8,579
Quote:
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
CornedBee is online now   Reply With Quote
Old 12-14-2009, 01:13 PM   #12
Registered User
 
slingerland3g's Avatar
 
Join Date: Jan 2008
Location: Seattle
Posts: 586
This has been addressed quite a few times on these forums. I am sure something below should strike your fancy!

C Board - Search Results
slingerland3g is offline   Reply With Quote
Reply

Thread Tools
Display Modes

Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Iterative Towers of Hanoi Mister C C++ Programming 10 04-11-2009 01:11 AM
towers of hanoi - what is wrong with this code? kanesoban C Programming 4 09-17-2007 01:20 PM
Towers of Hanoi (need help) Loudan C++ Programming 3 01-30-2006 10:17 PM
Towers of Hanoi, special output. spoon_ C Programming 3 03-15-2003 06:08 PM
Towers of Hanoi janehung C Programming 12 01-07-2002 06:40 AM


All times are GMT -6. The time now is 12:20 AM.


Powered by vBulletin® Version 3.8.1
Copyright ©2000 - 2010, Jelsoft Enterprises Ltd.
Search Engine Optimization by vBSEO 3.3.2

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