tower of hanoi

[ahmed mahmoud]

hi everybody
i try to write a code to solve the tower of hanoi but i cant
i dont konw how to make it solved by recursion and cant find the base case
is there anyone can help me in that

[JosAH]

hi everybody
i try to write a code to solve the tower of hanoi but i cant
i dont konw how to make it solved by recursion and cant find the base case
is there anyone can help me in that

Suppose you have to move a tower with n disks from position 'src' to position 'dst'. There's a third position 'aux' you can use to temporarily put a disk.

Moving the entire tower from 'src' to 'dst' can be done as follows:

1) move n-1 disks from 'src' to 'aux'
2) move the largest disk from 'src' to 'dst'
3) move n-1 disks from 'aux' to 'dst'.

The base case is simple: if n == 0 you simply do nothing. A single function with four parameters: src, dst, aux and the number of disks can do the job. It's a recursive function (see the three steps above and the base case).

kind regards,

Jos

[weaknessforcats]

Any recursion can be done using a loop.

I suggest you get this working using a loop.

Then a) put the loop in a recursuive function where b) the exit condition of the loop is also in the function to stp the recursion.

[JosAH]

Any recursion can be done using a loop.

I suggest you get this working using a loop.

Then a) put the loop in a recursuive function where b) the exit condition of the loop is also in the function to stp the recursion.

Theoretically yes, but the Towers of Hanoi problem needs either an explicit stack or quite some nifty (bit) fiddling to implement it as a loop (an iteration). Here a recursive solution is much more intuitive.

kind regards,

Jos

[whodgson]

So, can you visualise the moves set out in the JosAH algorithm?
Say n=3.
This would mean:
disc_1 from src peg to dst peg
disc_2 from src peg to aux peg
disc_1 from dst peg to aux peg
disc_3 from src peg to dst peg
disc_1 from aux peg to src peg
disc_2 from aux peg to dst peg
disc_1 from src peg to dst peg
me thinks......... and so on for more discs
remember disc_1 is the smallest dia. disc and the rules are that you cannot put a larger dia. disc over a smaller one.

[ahmed mahmoud]

well i try to write the code and i think i did it in a right way and if any one can tell me if that is the best way or not

#include <stdio.h>
#include <stdlib.h>
void hanoi (int num,char t1,char t2,char t3)
{
  if(num==1)
  {
    printf("\n %c to ---> %c",t1,t2);
  }
  else
  {
    hanoi(num-1,t1,t3,t2);
    printf("\n %c to ---> %c",t1,t2);
    hanoi(num-1,t3,t2,t1);
  }
}
int main()
{
    int numberOfDisks=3;
    char first='a';
    char second='b';
    char third='c';
   hanoi(numberOfDisks,first,third,second);
    return 0;
}

and i think this tow links will be useful http://vincehuston.org/ps/hanoi_article.html

http://upload.wikimedia.org/wikipedia/commons/6/60/Tower_of_Hanoi_4.gif

[JosAH]

Well done; the base case can be simplified to: if n == 0 do nothing; your code ends up like this then:

void hanoi (int num,char t1,char t2,char t3)
{
  if(num > 0) {
    hanoi(num-1,t1,t3,t2);
    printf("%c to ---> %c\n",t1,t2);
    hanoi(num-1,t3,t2,t1);
  }
}

kind regards,

Jos

[ahmed mahmoud]

Well done; the base case can be simplified to: if n == 0 do nothing

thanks JosAH but will this simplified make difference in
performance or its just for readability and to make the code more clear

[JosAH]

thanks JosAH but will this simplified make difference in
performance or its just for readability and to make the code more clear

The only difference is that when you call that function for n == 0 the function will return immediately. If you have a base case of n == 1 you wouldn't have made that call, so my version is a teensy weensy bit slower but I doubt if you can even notice it. And indeed it makes the code much simpler.

kind regards,

Jos