Before solving this problem, we introduce a simple library of stack with integers. Many following questions need an integer stack. Not to reinvent the wheel in our following solutions, we make a standalone integer stack library. Actually, we should do it at the very beginning of this chapter. This library includes the following functions: init, push, pop, peek, shrink, extend, isEmpty, isFull, and clean. We much call init function before using it and clean function at the end. The header file is as following:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | /*============================================================================= # Author: Sheng Yu - https://34.145.67.234 # Email : yusheng123 at gmail dot com # Last modified: 2013-10-11 21:23 # Filename: stack.h # Description: a library of a simple stack, with int only =============================================================================*/ #include <stdlib.h> #include <string.h> #include <stdbool.h> #include <errno.h> #ifndef STACK_H #define STACK_H // the size to be shrinked or extended static const size_t INCREMENT=8; // Data struction for the stack struct stack{ bool unlimited; // should the stack be shrinked or extended automatically? int capacity; int *bottom; int *top; }; // Function definition // when capacity sets to -1, the size of stack is automatically // shrinked or extended. bool init(struct stack *stack, int capacity); bool push(struct stack *stack, int value); int pop(struct stack *stack); int peek(struct stack stack); bool shrink(struct stack *stack); bool extend(struct stack *stack); bool isEmpty(struct stack stack); bool isFull(struct stack stack); void clean(struct stack *stack); #endif |
The implementation is:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 | /*============================================================================= # Author: Sheng Yu - https://34.145.67.234 # Email : yusheng123 at gmail dot com # Last modified: 2013-10-11 21:25 # Filename: stack.c # Description: a library of a simple stack, with int only =============================================================================*/ #include <stdlib.h> #include <string.h> #include <stdbool.h> #include <errno.h> #include "stack.h" // function implementation bool init(struct stack *stack, int capacity){ // Allocate the initialize the struct // When capacity is -1, the size of stack is automatically // shrinked or extended. if(capacity == -1){ stack->unlimited = true; stack->capacity = INCREMENT; } else{ stack->unlimited = false; stack->capacity = capacity; } stack->bottom = (int *) malloc(sizeof(int)*stack->capacity); stack->top = stack->bottom; return (stack->bottom == NULL) ? false : true; } bool push(struct stack *stack, int value){ // Check whether the free space is available if( stack->top - stack->bottom == stack->capacity ){ if( stack->unlimited ){ if( !extend(stack) ){ return false; // Fail to exntend the stack. No space. } } else{ return false; // Full in limited mode } } *((stack->top)++) = value; return true; } int pop(struct stack *stack){ int ret = 0; if(isEmpty(*stack)){ errno = ENODATA; return -1; // return value does not matter } ret = *(--(stack->top)); if( stack->capacity - (stack->top - stack->bottom) >= 2*INCREMENT){ // Too much free space shrink(stack); } return ret; } int peek(struct stack stack){ if(isEmpty(stack)){ errno = ENODATA; return -1; // return value does not matter } return *(stack.top-1); } bool shrink(struct stack *stack){ // shrink the memory space (stack capacity) int new_size = stack->capacity - INCREMENT; int number_of_items = stack->top - stack->bottom; int *temp = NULL; if( new_size <= 0){ // No need to shrink. It is the last space. return false; } temp = realloc(stack->bottom, new_size * sizeof(int)); if( temp == NULL ){ // Fail to allocate the memory. The old content remains. return false; } // Re-allocation successes. Old content is not usable anymore. stack->bottom = temp; stack->top = stack->bottom + number_of_items; stack->capacity = new_size; return true; } bool extend(struct stack *stack){ // extend the memory space (stack capacity) int new_size = stack->capacity + INCREMENT; int number_of_items = stack->top - stack->bottom; int *temp = NULL; temp = realloc(stack->bottom, new_size * sizeof(int)); if( temp == NULL ){ // Fail to allocate the memory. The old content remains. return false; } // Re-allocation successes. Old content is not usable anymore. stack->bottom = temp; stack->top = stack->bottom + number_of_items; stack->capacity = new_size; memset(stack->top, 0, stack->capacity - (stack->top - stack->bottom)); return true; } bool isEmpty(struct stack stack){ return stack.top == stack.bottom; } bool isFull(struct stack stack){ // In unlimited mode, automatically extend, never full return (!stack.unlimited) && ((stack.top-stack.bottom)==stack.capacity); } void clean(struct stack *stack){ // Destrct the struction free(stack->bottom); stack->bottom = stack->top = NULL; stack->unlimited = false; stack->capacity = 0; } |
This is a very classic problem: the Tower of Hanoi. In the book, the solution is recursive. And we need stacks to mimic the pegs and store the plate information in each peg. The recursive is short and easy to understand. But it requires more space for recording function callings. The following is the recursive solution for Tower of Hanoi in C:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 | /*============================================================================= # Author: Sheng Yu - https://34.145.67.234 # Email : yusheng123 at gmail dot com # Last modified: 2013-10-12 17:01 # Filename: 3.4.rec.c # Description: a tool to solve Tower of Hanoi recursively =============================================================================*/ #include <stdio.h> #include <stdbool.h> #include "stack.h" #define RAW_INPUT_MAX_LEN 32 void MoveHanoi(int NoToMove, struct stack *original, struct stack *target, struct stack *buffer, struct stack *address[3], char *name[3]){ // We need to move NoToMove plates from original to targe, with buffer // as temporary space. // The address and name of pegs are used to pretty-print int plate = 0; int peg_index = 0; if(NoToMove == 1){ // base case plate = pop(original); push(target, plate); printf("Moving plate #%d from ", plate); for( peg_index = 0; peg_index < 3; ++peg_index ){ // Totally three pegs if( address[peg_index] == original ){ printf("%s peg", name[peg_index]); break; } } for( peg_index = 0; peg_index < 3; ++peg_index ){ // Totally three pegs if( address[peg_index] == target ){ printf(" to %s peg.n", name[peg_index]); break; } } } else{ // Recursive part MoveHanoi(NoToMove-1, original, buffer, target, address, name); MoveHanoi(1, original, target, buffer, address, name); MoveHanoi(NoToMove-1, buffer, target, original, address, name); } return; } int main(){ int HanoiSize = -1; int PlateNo = -1; char *strtol_res = NULL; char raw_in[RAW_INPUT_MAX_LEN]; struct stack first, second, third; struct stack *address[3] = {&first, &second, &third}; char *name[3]= {"first", "second", "third"}; // Get the number of plates in this Hanoi printf("Please input the number of plates in the Tower of Hanoi: "); fgets( raw_in, RAW_INPUT_MAX_LEN, stdin); if( raw_in[strlen(raw_in)-1] != 'n' ){ // The input is longer than RAW_INPUT_MAX_LEN // The left part should be ignored. // And the input definitely not a valid integer for us do{ // Read the left content and discard fgets( raw_in, RAW_INPUT_MAX_LEN, stdin); }while( raw_in[strlen(raw_in)-1] != 'n' ); printf("The input is not a valid integer for Tower of Hanoi.n"); return -11; } errno = 0; HanoiSize = strtol( raw_in, &strtol_res, 10); if( errno == ERANGE || *strtol_res != 'n' || HanoiSize < 1){ printf("Invalid argument for the number of plates: %s",raw_in); return -12; } // Initialize these three stacks if( !init(&first, -1) ){ printf("Fail to initialize the first stack.n"); return -1; } if( !init(&second, -1) ){ printf("Fail to initialize the second stack.n"); clean(&first); return -2; } if( !init(&third, -1) ){ printf("Fail to initialize the third stack.n"); clean(&first); clean(&second); return -3; } // Push all plates to the first stack, from the biggest to smallest for(PlateNo = HanoiSize; PlateNo > 0; --PlateNo){ push(&first, PlateNo); } // Play and solve the Tower of Hanoi MoveHanoi( HanoiSize, &first, &third, &second, address, name); // Clean up and finish our job clean(&first); clean(&second); clean(&third); return 0; } |
A non-recursive method seems more complex, but is more efficient. Wikipedia lists many iterative methods. And we implement one, mentioned here. Firstly, we label the plates from smallest to biggest with 1, 2, and 3 and so on. Therefore, the #1 plate means the smallest one. If we count the steps of moving from 1, we could get the relationship as:
$$! step=ptimes 2^{k}+2^{k-1}=left( 2p+1right) times 2^{k-1} $$
where p is the number of previous moving for this plate, and k is the plate ID/label. For example, in the fourth step, with the equation, we could get p being 0, and k being 3. Therefore, we could know, we are moving the plate #3. And we do not moved it before (the number of previous moving is zero). In addition, we lable the first peg with 0, the second 1, and the third 2. We could estimate the current position as:
$$! current-position={_{p%3,hspace{16mm} if hspace{8mm} left( N+kright) %2=1}^{left( 2times pright) %3,hspace{16mm} if hspace{8mm} left( N+kright) %2=0} $$
where the N means the total number of plates in this game. Similarly, the next postion is:
$$! next-position={_{left( p + 1right) %3,hspace{16mm} if hspace{8mm} left( N+kright) %2=1}^{left( 2times p + 2right) %3,hspace{16mm} if hspace{8mm} left( N+kright) %2=0} $$
These results could be proven in an induction method. In this method, we do not need to use the stacks. In each step, we know all the information before taking any action. The source code of the non-recursive method is:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 | /*============================================================================= # Author: Sheng Yu - https://34.145.67.234 # Email : yusheng123 at gmail dot com # Last modified: 2013-10-13 22:41 # Filename: 3.4.ite.c # Description: a tool to solve Tower of Hanoi non-recursively No stack is needed =============================================================================*/ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <string.h> #include <errno.h> #define RAW_INPUT_MAX_LEN 32 void MoveHanoi(int NoToMove){ // We need to move NoToMove plates from first peg // to the third peg, with second peg as buffer // The name of pegs are used to pretty-print int plate = 0; // peg[0] is reserved char *pegs[3]= {"first", "second", "third"}; int temp = 0; int total_round = 1; int current_round = 0; int plate_round = 0; int from=0, to=0; // Determine how many steps are needed for(temp = 0; temp < NoToMove; ++temp){ total_round *= 2; if( total_round <= 0 ){ printf("Too much plates: overflow!n"); return; } } total_round -= 1; // Compute each step/moving for(current_round = 1; current_round <= total_round; ++current_round){ plate_round = current_round; for(plate = 1; plate_round%2 == 0; ++plate) plate_round /= 2; plate_round = (plate_round - 1)/2; if( (NoToMove + plate) % 2 == 0 ){ // When the sum of NoToMove and plate # is even, the plate // is always moving to left as: first->third->second-> // first->third->... // from=( (-plate_round)%3 + 3)%3, after simplification: from = (( plate_round % 3) * 2 ) % 3; // Beware of overflow // to = ( (-( plate_round + 1)) % 3 + 3 ) % 3 to = ( from + 2) % 3 ; } else{ // Otherwise, they move toward right as: // first->second->third->first->second->... from = plate_round % 3; to = ( 1 + plate_round ) % 3; } printf("Moving plate #%d from %s peg to %s peg.n", plate, pegs[from], pegs[to]); } return; } int main(){ int HanoiSize = -1; char *strtol_res = NULL; char raw_in[RAW_INPUT_MAX_LEN]; // Get the number of plates in this Hanoi printf("Please input the number of plates in the Tower of Hanoi: "); fgets( raw_in, RAW_INPUT_MAX_LEN, stdin); if( raw_in[strlen(raw_in)-1] != 'n' ){ // The input is longer than RAW_INPUT_MAX_LEN // The left part should be ignored. // And the input definitely not a valid integer for us do{ // Read the left content and discard fgets( raw_in, RAW_INPUT_MAX_LEN, stdin); }while( raw_in[strlen(raw_in)-1] != 'n' ); printf("The input is not a valid integer for Tower of Hanoi.n"); return -11; } errno = 0; HanoiSize = strtol( raw_in, &strtol_res, 10); if( errno == ERANGE || *strtol_res != 'n' || HanoiSize < 1){ printf("Invalid argument for the number of plates: %s",raw_in); return -12; } // Play and solve the Tower of Hanoi MoveHanoi( HanoiSize ); return 0; } |