20131128

< ----Recursive c program for towers of Hanoi problem ---->

key to solving this puzzle is to recognize that it can be solved by breaking the problem down into a collection of smaller problems and further breaking those problems down into even smaller problems hence making it a typical best suited problem for recursion .

example:   the pegs are  A, B, C and n is the total number of discs number the discs from 1 the largest of the discs and 5(variable DISCS) the smallest.
move n−1 discs from A to B. This leaves disc n alone on peg A
move disc n from A to C
move n−1 discs from B to C so they sit on disc n
The above is a recursive algorithm, to carry out steps 1 and 3, apply the same algorithm again for n−1. The entire procedure is a finite number of steps, since at some point the algorithm will be required for n = 1.

here is the program/code  in c
  1. #include<stdio.h>
  2. #define P(x) printf("%d\n",x);
  3. #define Ps(x) printf("\n\n%s=\n",x)
  4. #define DISCS 10
  5. struct stack1
  6. {int a[10],top;
  7. };
  8. typedef struct stack1 stack;
  9.  
  10. initialize(stack *s1,stack *s2,stack *s3)
  11. {
  12.     s1->top=s2->top=s3->top=-1;
  13. }
  14. int push(stack *s,int x)
  15. {
  16.     return(s->top<=(DISCS-2)?s->a[++s->top]=x,1:0);
  17. }
  18. int pop(stack *s)
  19. {
  20.     return(s->top==-1?-999:s->a[s->top--]);
  21. }
  22. move(stack *s1,stack *s2)
  23. {
  24.     int x=pop(s1);
  25.     push(s2,x);
  26. }
  27. printstack(stack *s3)
  28. {   int to=s3->top,d=pop(s3);
  29.     for(;!(d==-999);d=pop(s3))P(d);
  30.     s3->top=to;
  31. }
  32. tower_of_hanoi(stack *t1,stack *t2,stack *t3,int pgs)
  33. {    //you can print the stack here also, after each function call
  34.     if(pgs>0){
  35.      tower_of_hanoi(t1,t3,t2,pgs-1);
  36.     move(t1,t2);
  37.      tower_of_hanoi(t3,t2,t1,pgs-1);
  38.              }
  39. }
  40. main()
  41. {
  42.      stack s1,s2,s3;
  43.      initialize(&s1,&s2,&s3);
  44.      int d=1;//pegs 1  being the largest and DISCS the smallest
  45.      for(;push(&s1,d++););
  46.      Ps("orig/first stack");
  47.      printstack(&s1);
  48.      tower_of_hanoi(&s1,&s2,&s3,DISCS);
  49.      Ps("first stack");
  50.      printstack(&s1);
  51.      Ps("second stack");
  52.      printstack(&s2);
  53.      Ps("third stack");
  54.      printstack(&s3);
  55. }


NOTE : the number of discs is stored in predefined in DISCS , which can be changed to any value . But for every ring added the algorithm will take twice the time and memory for computation hence the following code may fail for values above 10 for DISCS