The Tower of Hanoi

learningbasics · #1 14-Feb-2006, 17:39

ok befor i start talking about what i need help with.... here is a link to the people that dont know what the tower of hanoi is, it will help you understand it by looking at a visual...
http://www.cut-the-knot.org/recurrence/hanoi.shtml
The object of this game is to move all of the rings to the right most peg. You may only move one ring at a time, you must never allow a large ring to rest on a smaller ring.

ok so i was going to make a program to do this (like the user enters how many disk they want and the computer (or program) will tell how many moves it will take, and what each disk will do at each step saying were it left from and were it went too..

my friend told me the code to accompish this...
let me shorten it to the function (or recursion) so the user already had put in the number of disks (for the sake of this thread say they put in 4 or 3 disks)

i just dont understand how it does this... he cant explain it to me, so im here for you guys to help explain in detail .....

now the function/recursion is....

CPP / C++ / C Code:

void moves (int Disk, Char A, Char B, Char C, Long Step)
{
  Step++;
  if(Disk<2)
     cout<<"Disk #"<<Disk<<" from "<<A<<" to "<<C<<endl;
   else
    {
      moves (Disk-1, A, C, B)
      cout<<"Disk #"<<Disk<<" from "<<A<<" to "<<C<<endl;
      moves (Disk-1, B, A, C)  
    }
}

now i under stand how step works.... but i mean i dont get
moves (Disk-1, A, C, B)
cout<<"Disk #"<<Disk<<" from "<<A<<" to "<<C<<endl;
moves (Disk-1, B, A, C)
part.....
like there isnt a cout for A to B or.. B to A... but i mean the program works, but can Someone PLEASE explain to me indetail how it works? i would love to understand...

thanks in advanced

learningbasics · #2 14-Feb-2006, 18:07

i see that 4 ppl already looked at this and no reply... so here to make things simplier... here is the full code (to make a better understanding of the whole thing) (if it will help).. i guess so you can try it on your C++ and i guess it will help you explain it to me... anyway here is the full thing

CPP / C++ / C Code:

//Var Section
int A, B, C;
int Disk;
long Step;
apstring Restart;

void data();
void moves(int, char, char, char, long);

void main()
{
do{
A='A';
B='B';
C='C';
Step=0;
clrscr();
data();
moves(Disk,A,B,C,Step);


cout << "would you like to restart? (Y=yes, N=no)" << endl;
cin >> Restart;
}while ( Restart == "y" || Restart == "Y" );
cout << "Press enter to end" << endl;
getch();
} //end

void data()
{
do
{
   cout<<"Please enter a number from 1 to 12"<<endl;
   cin>>Disk;
    if(Disk<1 || Disk>12)
     {
      cout<<"ERROR: please retype the number, needs to be between 1 ";
      cout<<"to 12!"<<endl;
     }
}while(Disk<1 || Disk>12);
}

void moves(int Disk, char A, char B, char C, long Step)
{
 Step++;
 if(Disk<2)
   cout<<"Disk #"<<Disk<<" from "<<A<<" to "<<C<<endl;
 else
 {
   moves(Disk-1,A,C,B,Step);
   cout<<"Disk #"<<Disk<<" from "<<A<<" to "<<C<<endl;
   moves(Disk-1,B,A,C,Step);
 }
}

like the post above, i really dont get the ......

CPP / C++ / C Code:

   moves(Disk-1,A,C,B,Step);
   cout<<"Disk #"<<Disk<<" from "<<A<<" to "<<C<<endl;
   moves(Disk-1,B,A,C,Step);

part
like the A,C,B and B,A,C ..... when the real function is A,B,C.... like for me it seems liek that goes into a completly new function... PLEASE help explain!

hope this helps!

agian the code works perfect, so dont try to look for errors, i just need a good long (i bet it gotta be long and thats A-OK with me ) explaination of how the recursion all works

PS.....A=the peg were all the disks start... and C=the peg were all the disk end

Paramesh · #3 14-Feb-2006, 19:01

Quote:

Originally Posted by learningbasics

i see that 4 ppl already looked at this and no reply... so here to make things simplier... here is the full code (to make a better understanding of the whole thing) (if it will help).. i guess so you can try it on your C++ and i guess it will help you explain it to me... anyway here is the full thing

Many people would just skim through the thread, and wont reply.
Please wait for a while...

Just a step by step looking at the code will greatly help a lot in your case.
For example, the function is this:

CPP / C++ / C Code:

void moves (int Disk, Char A, Char B, Char C, Long Step)
{
  Step++;
  if(Disk<2)
     cout<<"Disk #"<<Disk<<" from "<<A<<" to "<<C<<endl;
   else
    {
      moves (Disk-1, A, C, B)
      cout<<"Disk #"<<Disk<<" from "<<A<<" to "<<C<<endl;
      moves (Disk-1, B, A, C)  
    }
}

Assume that there are 2 disks for the start..
What will you do?
First you will move the disk 1 from A to B.
Then You will move the disk 2 from A to C.
And you will move the disk 1 from B to C. Isnt it?

So, look at what your code does now:
Initially the disk is 2.
So, The else part is executed, and the function is called again with disk = 1 and B and C interchanged.

Now, the disk is equal to 1.
So, move the disk 1 from A to B(Actually).(Because B and C are interchanged)
Now, it comes out of the inner recursive function, and then prints:
Move Disk from A to C.
Again, the function is called with Disk = 1, and with B and A interchanged.
Now what? This is printed:
Move disk from B to C(Actually)(Because A and B are interchanged)

Then, it finishes the function.
Now you see how this works?

Just to through step by step for disk = 3, and check whether it works!
(IT will! though)

Hope you understood this one..
Regards,

Paramesh.

learningbasics · #4 14-Feb-2006, 19:12

....................(SPEECHLESS).................. ...

o wait, no im not... i just need to say.......

THIS MAKES SOOOOO MUCH SENCE NOW!!!!!!!!!!!!!!!!!!!!!!!

no really, thanks alot.....
/hug
/thank
/sign basics

i will now try and do it with 3 disks now... anyways, THANKS SOO MUCH

jaininaveen · #5 14-Feb-2006, 19:23

hi,
A small suggetion for you. if you learn data structure topics "stacks" and "queues"(LIFO) you can do better coding for towers of hanai and also you can understand the topics easly, because towers of hanai is purly depends on LIFO topic, so you can do better code for that.....
all the best......

learningbasics · #6 14-Feb-2006, 20:39

if theres 3 disks, it goes through the functions over and over intill it hits Disk<2 (meaning its on the first disk).
hmmm a better way i could put it is that, the Recursion will go thru the 1st part of the else on the if/if else (A.K.A. moves(Disk-1,A,C,B)... part) intercanging C and B each time untill it hits Disk=1, depending on what they put, the recursion will switch from C and B, back to B and C, to agian B to C... over and over untill Disk=1.. then the recursion will just go back to its "inner recursive function".

did i get it??? am i right???

im sure i got it down now, thanks for all your help, just a post saying i got it will make me feel 10x more better

anyways THANKS SOO MUCH!

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
help: Computer tower noises	kelly_lam	Computer Hardware Forum	5	09-Jul-2004 06:36

The Tower of Hanoi

Re: the tower of hanoi

Re: the tower of hanoi

Re: the tower of hanoi

Re: the tower of hanoi

Re: the tower of hanoi