[331] | 1 | /* example from http://barnyard.syr.edu/quickies/hanoi.c */
|
---|
| 2 |
|
---|
| 3 | /* hanoi.c: solves the tower of hanoi problem. (Programming exercise.) */
|
---|
| 4 | /* By Terry R. McConnell (12/2/97) */
|
---|
| 5 | /* Compile: cc -o hanoi hanoi.c */
|
---|
| 6 |
|
---|
| 7 | /* This program does no error checking. But then, if it's right,
|
---|
| 8 | it's right ... right ? */
|
---|
| 9 |
|
---|
| 10 |
|
---|
| 11 | /* The original towers of hanoi problem seems to have been originally posed
|
---|
| 12 | by one M. Claus in 1883. There is a popular legend that goes along with
|
---|
| 13 | it that has been often repeated and paraphrased. It goes something like this:
|
---|
| 14 | In the great temple at Benares there are 3 golden spikes. On one of them,
|
---|
| 15 | God placed 64 disks increasing in size from bottom to top, at the beginning
|
---|
| 16 | of time. Since then, and to this day, the priest on duty constantly transfers
|
---|
| 17 | disks, one at a time, in such a way that no larger disk is ever put on top
|
---|
| 18 | of a smaller one. When the disks have been transferred entirely to another
|
---|
| 19 | spike the Universe will come to an end in a large thunderclap.
|
---|
| 20 |
|
---|
| 21 | This paraphrases the original legend due to DeParville, La Nature, Paris 1884,
|
---|
| 22 | Part I, 285-286. For this and further information see: Mathematical
|
---|
| 23 | Recreations & Essays, W.W. Rouse Ball, MacMillan, NewYork, 11th Ed. 1967,
|
---|
| 24 | 303-305.
|
---|
| 25 | *
|
---|
| 26 | *
|
---|
| 27 | */
|
---|
| 28 |
|
---|
| 29 | #include <stdio.h>
|
---|
| 30 | #include <stdlib.h>
|
---|
| 31 |
|
---|
| 32 | #define TRUE 1
|
---|
| 33 | #define FALSE 0
|
---|
| 34 |
|
---|
| 35 | /* This is the number of "disks" on tower A initially. Taken to be 64 in the
|
---|
| 36 | * legend. The number of moves required, in general, is 2^N - 1. For N = 64,
|
---|
| 37 | * this is 18,446,744,073,709,551,615 */
|
---|
| 38 | #define N 4
|
---|
| 39 |
|
---|
| 40 | /* These are the three towers. For example if the state of A is 0,1,3,4, that
|
---|
| 41 | * means that there are three discs on A of sizes 1, 3, and 4. (Think of right
|
---|
| 42 | * as being the "down" direction.) */
|
---|
| 43 | int A[N], B[N], C[N];
|
---|
| 44 |
|
---|
| 45 | void Hanoi(int,int*,int*,int*);
|
---|
| 46 |
|
---|
| 47 | /* Print the current configuration of A, B, and C to the screen */
|
---|
| 48 | void PrintAll()
|
---|
| 49 | {
|
---|
| 50 | int i;
|
---|
| 51 |
|
---|
| 52 | printf("A: ");
|
---|
| 53 | for(i=0;i<N;i++)printf(" %d ",A[i]);
|
---|
| 54 | printf("\n");
|
---|
| 55 |
|
---|
| 56 | printf("B: ");
|
---|
| 57 | for(i=0;i<N;i++)printf(" %d ",B[i]);
|
---|
| 58 | printf("\n");
|
---|
| 59 |
|
---|
| 60 | printf("C: ");
|
---|
| 61 | for(i=0;i<N;i++)printf(" %d ",C[i]);
|
---|
| 62 | printf("\n");
|
---|
| 63 | printf("------------------------------------------\n");
|
---|
| 64 | return;
|
---|
| 65 | }
|
---|
| 66 |
|
---|
| 67 | /* Move the leftmost nonzero element of source to dest, leave behind 0. */
|
---|
| 68 | /* Returns the value moved (not used.) */
|
---|
| 69 | int Move(int *source, int *dest)
|
---|
| 70 | {
|
---|
| 71 | int i = 0, j = 0;
|
---|
| 72 |
|
---|
| 73 | while (i<N && (source[i])==0) i++;
|
---|
| 74 | while (j<N && (dest[j])==0) j++;
|
---|
| 75 |
|
---|
| 76 | dest[j-1] = source[i];
|
---|
| 77 | source[i] = 0;
|
---|
| 78 | PrintAll(); /* Print configuration after each move. */
|
---|
| 79 | return dest[j-1];
|
---|
| 80 | }
|
---|
| 81 |
|
---|
| 82 |
|
---|
| 83 | /* Moves first n nonzero numbers from source to dest using the rules of Hanoi.
|
---|
| 84 | Calls itself recursively.
|
---|
| 85 | */
|
---|
| 86 | void Hanoi(int n,int *source, int *dest, int *spare)
|
---|
| 87 | {
|
---|
| 88 | int i;
|
---|
| 89 | if(n==1){
|
---|
| 90 | Move(source,dest);
|
---|
| 91 | return;
|
---|
| 92 | }
|
---|
| 93 |
|
---|
| 94 | Hanoi(n-1,source,spare,dest);
|
---|
| 95 | Move(source,dest);
|
---|
| 96 | Hanoi(n-1,spare,dest,source);
|
---|
| 97 | return;
|
---|
| 98 | }
|
---|
| 99 |
|
---|
| 100 | int main()
|
---|
| 101 | {
|
---|
| 102 | int i;
|
---|
| 103 |
|
---|
| 104 | /* initialize the towers */
|
---|
| 105 | for(i=0;i<N;i++)A[i]=i+1;
|
---|
| 106 | for(i=0;i<N;i++)B[i]=0;
|
---|
| 107 | for(i=0;i<N;i++)C[i]=0;
|
---|
| 108 |
|
---|
| 109 | printf("Solution of Tower of Hanoi Problem with %d Disks\n\n",N);
|
---|
| 110 |
|
---|
| 111 | /* Print the starting state */
|
---|
| 112 | printf("Starting state:\n");
|
---|
| 113 | PrintAll();
|
---|
| 114 | printf("\n\nSubsequent states:\n\n");
|
---|
| 115 |
|
---|
| 116 | /* Do it! Use A = Source, B = Destination, C = Spare */
|
---|
| 117 | Hanoi(N,A,B,C);
|
---|
| 118 |
|
---|
| 119 | return 0;
|
---|
| 120 | }
|
---|
| 121 |
|
---|
| 122 | /* vim: set expandtab ts=4 sw=3 sts=3 tw=80 :*/
|
---|