SHOW:
|
|
- or go back to the newest paste.
| 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 | } |