Appendix One: Hanoi Towers Puzzle

In Chapter 5 we discussed recursion and mentioned the Hanoi towers puzzle and its recursive solution. For completeness we include a simple C program to solve the problem. The puzzle consists of three pegs, with wooden disks stacked on one. The disks are of different sizes. The only rule of the game is that a bigger disk can never rest atop a smaller one. The task is to move all the disks from the leftmost peg to the rightmost peg - with the aid of the middle peg (see Figure A.1). We shall refer to the peg from which we are moving the disks as origin, the peg to which we must move the disks as destination, and the peg we can use in the interim as help.

image from book
Figure A.1: Hanoi towers puzzle

The recursive solution is based on the following observations. Moving two disks is easy (the top disk to help, the bottom disk to destination, the top disk to destination on top of the bottom disk). Moving three disks is also easy: pretend that the bottom disk is a part of the base; move the remaining two disks from origin to help using destination (easy to do, we did two disks just a few sentences back); now we have two disks nicely stacked on help; move the remaining third disk from origin to destination and pretend that it is a part of the base; now move two disks from help to destination using empty origin. And so on, .... More generally : To move n disks from origin to destination using help, we move the top n - 1disks from origin to help using destination, then the remaining disk from origin to destination, then the remaining n - 1 from help (using origin) to destination.

The C program presented is rather simple (no graphics), but it does represent the pegs "graphically" on the screen in a schematic way. After each move, the program pauses and waits for the user to hit "enter" and so continue to the next move.

 #include <stdio.h> #include <string.h> #include <stdlib.h> #define HEIGHT 10 typedef int PEG[HEIGHT]; PEG A, B, C; void set_pegs(int nofdisks); void ht(int nofdisks,PEG origin,PEG help,PEG destination); int remove_top(PEG peg); void put_top(PEG peg,int disk); void move(PEG from,PEG to); void show_pegs(void); char *make_disk(int disk); /* function main -------------------------------------------- */ int main(int argc,char** argv) {  if (argc != 2) {    printf("usage - %s <nofdisks>\n",argv[0]);    exit(1);  }  if (sscanf(argv[1],"%d",&nofdisks) != 1) {    printf("number of disks must be 2 - %d\n",HEIGHT);    exit(0);  }  if (nofdisks < 2  nofdisks > HEIGHT) {    printf("number of disks must be 2 - %d\n",HEIGHT);    exit(0);  }  set_pegs(nofdisks);  show_pegs();  ht(nofdisks,A,B,C);  printf("done\n");  return 0; }/*end main*/ /* function set_pegs ---------------------------------- */ void set_pegs(int nofdisks) {  int i;  if (nofdisks > HEIGHT) {    printf("too many disks (%d) for the height of the pegs (%d)\n",            nofdisks,HEIGHT);    exit(1);  }  for(i = 0; i < HEIGHT; i++)      A[i] = B[i] = C[i] = -1;  for(i = 0; i < nofdisks; i++)      A[i] = nofdisks-1-i; }/* end set_pegs */ /* function ht ------------------------------------------ */ void ht(int nofdisks,PEG origin,PEG help,PEG destination) {  if (nofdisks == 2) { // base case    move(origin,help);    show_pegs();    move(origin,destination);    show_pegs();    move(help,destination);    show_pegs();    return;  }  // recursion  ht(nofdisks-1,origin,destination,help);  move(origin,destination);  show_pegs();  ht(nofdisks-1,help,origin,destination); }/* end ht */ /* function remove_top ------------------------------------ */ int remove_top(PEG peg) {  int i, res;  for(i = 0; i < HEIGHT; i++)   if (peg[i] == -1) break;  if (i == 0) {    printf("peg is empty\n");    exit(0);  }  i--;  res = peg[i];  peg[i] = -1;  return res; }/* end remove_top */ /* function put_top --------------------------------------- */ void put_top(PEG peg,int disk) {  int i;  for(i = 0; i < HEIGHT; i++)   if (peg[i] == -1) break;  if (i == HEIGHT) {    printf("peg is full\n");    exit(1);  }  peg[i] = disk; }/* end put_top */ /* function move ------------------------------------------ */ void move(PEG from,PEG to) {  int disk;  disk = remove_top(from);  put_top(to,disk); }/* end move */ /* function show_pegs ------------------------------------- */ void show_pegs(void) {  int i;  for(i = HEIGHT-1; i >= 0; i--) {   printf("%s",make_disk(A[i]));   printf("  %s",make_disk(B[i]));   printf("  %s\n",make_disk(C[i]));  }  printf("%s",make_disk(-2));  printf("  %s",make_disk(-2));  printf("  %s\n",make_disk(-2));  fflush(stdout);  getchar();  fflush(stdin); }/* end show_pegs */ /* function make_disk -------------------------------------- */ char *make_disk(int disk) {  static char buf[26];  int i, j;  if (disk == -2)  /* make base */    strcpy(buf,"HHHHHHHHHHHHHHHHHHHHHHHHH");  else if (disk == -1) /* make peg */    strcpy(buf,"                          "); else{   for(j = 0; j < 1+HEIGHT-disk; buf[j++] = ' ');    for(i = 0; i <= disk; buf[j++] = '=',i++);     buf[j++] = '';     for(i = 0; i <= disk; buf[j++] = '=',i++);     for(i = 0; i < 1+HEIGHT-disk; buf[j++] = ' ',i++);     buf[j] = ' 
 #include <stdio.h> #include <string.h> #include <stdlib.h> #define HEIGHT 10 typedef int PEG[HEIGHT]; PEG A, B, C; void set_pegs(int nofdisks); void ht(int nofdisks,PEG origin,PEG help,PEG destination); int remove_top(PEG peg); void put_top(PEG peg,int disk); void move(PEG from,PEG to); void show_pegs(void); char *make_disk(int disk); /* function main -------------------------------------------- */ int main(int argc,char** argv) { if (argc != 2) { printf("usage - %s <nofdisks>\n",argv[0]); exit(1); } if ( sscanf (argv[1],"%d",&nofdisks) != 1) { printf("number of disks must be 2 - %d\n",HEIGHT); exit(0); } if (nofdisks < 2  nofdisks > HEIGHT) { printf("number of disks must be 2 - %d\n",HEIGHT); exit(0); } set_pegs(nofdisks); show_pegs(); ht(nofdisks,A,B,C); printf("done\n"); return 0; }/*end main*/ /* function set_pegs ---------------------------------- */ void set_pegs(int nofdisks) { int i; if (nofdisks > HEIGHT) { printf("too many disks (%d) for the height of the pegs (%d)\n", nofdisks,HEIGHT); exit(1); } for(i = 0; i < HEIGHT; i++) A[i] = B[i] = C[i] = -1; for(i = 0; i < nofdisks; i++) A[i] = nofdisks-1-i; }/* end set_pegs */ /* function ht ------------------------------------------ */ void ht(int nofdisks,PEG origin,PEG help,PEG destination) { if (nofdisks == 2) { // base case move(origin,help); show_pegs(); move(origin,destination); show_pegs(); move(help,destination); show_pegs(); return; } // recursion ht(nofdisks-1,origin,destination,help); move(origin,destination); show_pegs(); ht(nofdisks-1,help,origin,destination); }/* end ht */ /* function remove_top ------------------------------------ */ int remove_top(PEG peg) { int i, res; for(i = 0; i < HEIGHT; i++) if (peg[i] == -1) break; if (i == 0) { printf("peg is empty\n"); exit(0); } i--; res = peg[i]; peg[i] = -1; return res; }/* end remove_top */ /* function put_top --------------------------------------- */ void put_top(PEG peg,int disk) { int i; for(i = 0; i < HEIGHT; i++) if (peg[i] == -1) break; if (i == HEIGHT) { printf("peg is full\n"); exit(1); } peg[i] = disk; }/* end put_top */ /* function move ------------------------------------------ */ void move(PEG from,PEG to) { int disk; disk = remove_top(from); put_top(to,disk); }/* end move */ /* function show_pegs ------------------------------------- */ void show_pegs(void) { int i; for(i = HEIGHT-1; i >= 0; i--) { printf("%s",make_disk(A[i])); printf(" %s",make_disk(B[i])); printf(" %s\n",make_disk(C[i])); } printf("%s",make_disk(-2)); printf(" %s",make_disk(-2)); printf(" %s\n",make_disk(-2)); fflush ( stdout ); getchar (); fflush(stdin); }/* end show_pegs */ /* function make_disk -------------------------------------- */ char *make_disk(int disk) { static char buf[26]; int i, j; if (disk == -2) /* make base */ strcpy(buf,"HHHHHHHHHHHHHHHHHHHHHHHHH"); else if (disk == -1) /* make peg */ strcpy (buf,"  "); else{ for(j = 0; j < 1+HEIGHT-disk; buf[j++] = ' '); for(i = 0; i <= disk; buf[j++] = '=',i++); buf[j++] = ''; for(i = 0; i <= disk; buf[j++] = '=',i++); for(i = 0; i < 1+HEIGHT-disk; buf[j++] = ' ',i++); buf[j] = '\0'; } return buf; }/* end make_disk */ 
'; } return buf; }/* end make_disk */


Memory as a Programming Concept in C and C++
Memory as a Programming Concept in C and C++
ISBN: 0521520436
EAN: 2147483647
Year: 2003
Pages: 64

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net