rootUser

tower of hanoi non recursion

May 26th, 2016
44
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include<math.h>
  3. #define MX_SIZE 1024
  4.  
  5. void HANOI( int n , int i , int j , int k ) ;
  6.  
  7. /* initializing max size and top */
  8.  
  9. int stack_n[ MX_SIZE ] ;
  10. int stack_i[ MX_SIZE ] ;
  11. int stack_j[ MX_SIZE ] ;
  12. int stack_k[ MX_SIZE ] ;
  13. int top_n ;
  14. int top_i ;
  15. int top_j ;
  16. int top_k ;
  17.  
  18. /* function for push and pop */
  19.  
  20. void push_n( int n ) ;
  21. void push_i( int n ) ;
  22. void push_j( int n ) ;
  23. void push_k( int n ) ;
  24. int pop_n( void ) ;
  25. int pop_i( void ) ;
  26. int pop_j( void ) ;
  27. int pop_k( void ) ;
  28. void push( int n , int i , int j , int k ) ;
  29. int pop( int &n , int &i , int &j , int &k ) ;
  30. void empty_stack( void ) ;
  31. int stack_is_empty( void ) ;
  32.  
  33. void HANOI( int n , int i , int j , int k )
  34. {
  35.     empty_stack() ;
  36.     push( n , i , j , k ) ;
  37.     while( !stack_is_empty() )
  38.     {
  39.         pop( n , i , j , k ) ;
  40.         if( n == 1 )
  41.         {
  42.             printf( "move disk from %d to %d . \n" , i , k ) ;
  43.         }
  44.         else
  45.         {
  46.             push( n - 1 , j , i , k ) ;
  47.             push( 1 , i , j , k ) ;
  48.             push( n - 1 , i , k , j ) ;
  49.         }
  50.     }
  51. }
  52.  
  53. int main( void )
  54. {
  55.     int disks ;
  56.     printf("Enter the number of disks: ");
  57.     scanf( "%d" , &disks ) ;
  58.  
  59.     int move_count = pow(2,disks)-1;
  60.     printf("\nTotal moves: %d\n\n",move_count);
  61.  
  62.     HANOI( disks , 1 , 2 , 3 ) ;
  63.  
  64.     return 0 ;
  65. }
  66.  
  67.  
  68.  
  69. void push_n( int n )
  70. {
  71.     top_n = top_n + 1 ;
  72.     stack_n[ top_n ] = n ;
  73. }
  74.  
  75. void push_i( int n )
  76. {
  77.     top_i = top_i + 1 ;
  78.     stack_i[ top_i ] = n ;
  79. }
  80.  
  81. void push_j( int n )
  82. {
  83.     top_j = top_j + 1 ;
  84.     stack_j[ top_j ] = n ;
  85. }
  86.  
  87. void push_k( int n )
  88. {
  89.     top_k = top_k + 1 ;
  90.     stack_k[ top_k ] = n ;
  91. }
  92.  
  93. int pop_n( void )
  94. {
  95.     int number ;
  96.     number = stack_n[ top_n ] ;
  97.     top_n = top_n - 1 ;
  98.     return number ;
  99. }
  100.  
  101. int pop_i( void )
  102. {
  103.     int number ;
  104.     number = stack_i[ top_i ] ;
  105.     top_i = top_i - 1 ;
  106.     return number ;
  107. }
  108.  
  109.  
  110.  
  111. int pop_j( void )
  112. {
  113.     int number ;
  114.     number = stack_j[ top_j ] ;
  115.     top_j = top_j - 1 ;
  116.     return number ;
  117. }
  118.  
  119.  
  120.  
  121. int pop_k( void )
  122. {
  123.     int number ;
  124.     number = stack_k[ top_k ] ;
  125.     top_k = top_k - 1 ;
  126.     return number ;
  127. }
  128.  
  129. void push( int n , int i , int j , int k )
  130. {
  131.     push_n( n ) ;
  132.     push_i( i ) ;
  133.     push_j( j ) ;
  134.     push_k( k ) ;
  135. }
  136.  
  137. int pop( int &n , int &i , int &j , int &k )
  138. {
  139.     n = pop_n() ;
  140.     i = pop_i() ;
  141.     j = pop_j() ;
  142.     k = pop_k() ;
  143. }
  144.  
  145. void empty_stack( void )
  146. {
  147.     top_n = -1 ;
  148.     top_i = -1 ;
  149.     top_j = -1 ;
  150.     top_k = -1 ;
  151. }
  152.  
  153. int stack_is_empty( void )
  154. {
  155.     if( top_n == -1 && top_i == -1 && top_j == -1 && top_k == -1 )
  156.     {
  157.         return 1 ;
  158.     }
  159.     else
  160.     {
  161.         return 0 ;
  162.     }
  163. }
Add Comment
Please, Sign In to add comment