home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / compiler / miracl / hanoi.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-05-25  |  1.4 KB  |  55 lines
  1. /* Non-recursive solution to Towers of Hanoi */
  2.  
  3. void main();
  4.  
  5. #include <stdio.h>
  6. #include <system.h>
  7.  
  8. #define width (rings+1)
  9.  
  10. void main()
  11. {
  12.    int rings, last, next, x, z[500], s[3];
  13.  
  14.    printf("how many rings?  "); scanf("%d",&rings);
  15.  
  16.    for(x=1; x<=rings; x++)  /* put rings on first peg */
  17.       z[x]=width-x;
  18.    for(x=0; x<=2*width; x+=width)  /* set base for each peg  */
  19.       z[x]=1000;
  20.  
  21. /* if even number of rings, put first ring on second peg; if odd, on third */
  22.  
  23.    if(rings%2==0)
  24.       {
  25.       last=1; s[2]=0; s[1]=1;
  26.       z[width+1]=z[rings];
  27.       }
  28.    else
  29.       {
  30.       last=2; s[1]=0; s[2]=1;
  31.       z[2*width+1]=z[rings];
  32.       }
  33.  
  34.    printf("from 1 to %d\n",last+1); s[0]=rings-1;
  35.  
  36.    while(s[0]+s[1])  /* while first and second pegs aren't empty */
  37.       {
  38. /* next ring to move is smaller of rings on the two pegs not moved onto last */
  39.  
  40.       if(last==0)  next=z[width+s[1]]<z[2*width+s[2]]?1:2;
  41.       if(last==1)  next=z[s[0]]<z[2*width+s[2]]?0:2;
  42.       if(last==2)  next=z[s[0]]<z[width+s[1]]?0:1;
  43.  
  44. /* top ring of 'to' peg must be larger and an even 'distance' away */
  45.  
  46.       if((z[next*width+s[next]]>z[last*width+s[last]])||
  47.      ((z[last*width+s[last]]-z[next*width+s[next]])%2==0)) last=3-next-last;
  48.  
  49.       printf("from %d to %d\n",next+1,last+1);
  50.  
  51.       s[next]=s[next]-1; s[last]=s[last]+1; /* move from 'next' to 'last' peg */
  52.       z[last*width+s[last]]=z[next*width+s[next]+1];
  53.       }
  54. }
  55.