汉诺塔的非递归（演示、动画）

Hanoi,非递归,演示,动画效果

kensta
  有动画演示，move2()是标准解的调用
  move()是用于演示动画或显示移动秩序和包含监测有无错误移动的调用
使用Borland c++ 3.0(Turbo c++ 3.0,Turbo c 2.0也可)编译通过，图形方式使用Tc的bgi
*/

/*************************************/
/*
 about error process
*/
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
/*
 if debuging use #define ERROR_DEBUG
 otherwise remove it.
*/
//#define ERROR_DEBUG
#ifdef  ERROR_DEBUG
 #define error(x) error_debug(x)
 #define report() report_debug()
 #define initerror() initerror_debug()

char *err[10];
int errs=0;

void initerror_debug(){
 int i;
 for(i=0;i<10;i++)err[i]=NULL;
}

void error_debug(char *a){
 if(errs>9)return;
 err[errs]=(char *)malloc(strlen(a)+1);
 strcpy(err[errs],a);
 printf(a);
 errs++;
}

void report_debug(){
 int i;
 if(!errs)return;
 for(i=0;i<errs;i++){
  printf(err[i]);
  free(err[i]);
 }
}
#else
 #define error(x)
 #define report()
 #define initerror()
#endif
/*************************************/
/*
 about stack
*/

#define STACK_SIZE 31
typedef struct {
 int data[STACK_SIZE];
 int top;
}stack;
int clear(stack *a);
int create(stack **a);
int push(stack *a,int data);
int pop(stack *a,int *data);
int gettop(stack *a,int *data);
int dispose(stack *a);

int pop(stack *a,int *data){
 if(a->top){
  *data=a->data[--a->top];
  return 1;
 }else{
  error("pop(stack *,int *):stack empty!\n");
  return 0;
 }
}

int push(stack *a,int data){
 if(a->top<STACK_SIZE){
  a->data[a->top++]=data;
  return 1;
 }else {
  error("push(stack *,int):stack full!\n");
  return 0;
 }
}

int create(stack **a){
 *a=(stack *)malloc(sizeof(stack));
 if(*a)return clear(*a);
 else{
  error("create(stack **):create error! Not enough momery!\n");
  return 0;
 }
}

int clear(stack *a){
 if(a){
  a->top=0;
  return 1;
 }else {
  error("clear(stack *):stack not exist!\n");
  return 0;
 }
}

int gettop(stack *a,int *data){
 if(a->top){
  *data=a->data[a->top-1];
  return 1;
 }else{
  error("gettop(stack *,int *):stack empty!\n");
  return 0;
 }
}

int dispose(stack *a){
 if(a){
  free(a);
  return 1;
 }else{
  error("dispose(stack *):stack not exist!\n");
  return 0;
 }
}
/**************************************/
/*
 about Hanoi the game
*/
#include <graphics.h>
#include <dos.h>
#define MAX_LEVEL STACK_SIZE
int position[MAX_LEVEL+1];
stack *theStack[3];
int depth;
int mode;
int print;
int initgame(int d){
 int i;
 int x,y;
 int h=5;
 int w;
 initerror();
 if(mode){
  int gdriver = DETECT, gmode, errorcode;
  /* initialize graphics mode */
  initgraph(&gdriver, &gmode, "");
  setfillstyle(1,7);
 }
 for(i=0;i<3;i++)
  if(!create(&theStack[i]))
   break;
 if(i!=3){
  for(;i>=0;i--)dispose(theStack[i]);
  error("initgame(int):can not init stack!\n");
  return 0;
 }
 depth=d;
 for(i=d;i;i--){
  push(theStack[0],i);
  if(mode){
   y=200+100-theStack[0]->top*(h+1);
   w=i*10;
   x=150-w/2;
   setcolor(i);
   setfillstyle(1,i);
   bar(x,y,x+w,y+h);
  }
  position[i]=0;
 }
 if(mode){
  setcolor(15);
  for(i=0;i<3;i++)
   rectangle(150+i*150-1,120,150+i*150+1,300);
  line(50,300,500,300);
 }
 return 1;
}

int endgame(){
 int i=2;
 for(;i>=0;i--)dispose(theStack[i]);
 printf("report:");
 report();
 if(mode)closegraph();
 return 1;
}

void show(int p,int from,int to){
 int i;
 int x,y;
 int newx,newy;
 int h=5;
 int w=p*10;
 y=200+100-(theStack[from]->top+1)*(h+1);
 x=from*150+150-w/2;
 newx=to*150+150-w/2;
 newy=200+100-theStack[to]->top*(h+1);
 while(y>100){
  setcolor(0);
  setfillstyle(1,0);
  bar(x,y,x+w,y+h);
  y-=(h+1);
  setcolor(15);
  rectangle(150+from*150-1,120,150+from*150+1,300);
  setcolor(p);
  setfillstyle(1,p);
  bar(x,y,x+w,y+h);
  delay(10);
 }
 while(x!=newx){
  setcolor(0);
  setfillstyle(1,0);
  bar(x,y,x+w,y+h);
  (x>newx)?x--:x++;
  setcolor(p);
  setfillstyle(1,p);
  bar(x,y,x+w,y+h);
  delay(2);
 }
 while(y<newy){
  setcolor(0);
  setfillstyle(1,0);
  bar(x,y,x+w,y+h);
  setcolor(15);
  rectangle(150+to*150-1,120,150+to*150+1,300);
  y+=(h+1);
  setcolor(p);
  setfillstyle(1,p);
  bar(x,y,x+w,y+h);
  delay(10);
 }
}

int move(int p){
 int t,s;
 if(!gettop(theStack[position[p>,&t)){
  error("move(int):the stack is empty\n");
  return 0;
 }
 if(t==p){
  pop(theStack[position[p>,&t);
  if(!mode&&print)printf("%c -> ",'A'+position[p]);
  /* another important core line */
  s=(position[p]+1+(depth%2?p%2:(p+1)%2) )%3;
  if(gettop(theStack[s],&t)&&t<p){
   error("move(int):can not move big level above small one\n");
   return 0;
  }
  push(theStack[s],p);
  if(mode)show(p,position[p],s);
  else if(print)printf("%c\t",'A'+s);
  position[p]=s;
 }else error("move(int):position error\n");
 return 1;
}
int move2(int p){
 int t,s;
 s=(position[p]+1+(depth%2?p%2:(p+1)%2) )%3;
 if(print)printf("%c->%c\t",'A'+position[p],'A'+s);
 position[p]=s;
 return 1;
}
#include <conio.h>
void main(){
 unsigned long i;
 unsigned long N=10;
 unsigned long p,q;
 printf("Welcome to Hanoi\n");
 printf("Note that this Hanoi is not write by recurrence!\n");
 printf("And not calculate with any stack.\n");
 printf("but i want to check if the a is right.\n");
 printf("i use 3 stack to show if there is any violent move happens.:)\n");
 printf("\nEnter a number as level(1 to 30):");
 scanf("%d",&N);
 if(N<1||N>30){
  printf("error: not 1 to 30\n");
  return;
 }
 printf("\n Select show mode('c' in TEXT 'g' in GRAPHICS)\n");
 printf("Note that if the level is to big you'd better not use 'g' for speed.\n");
 printf("19 is about 20 seconds. 20 is about double of that. etc.\n");
 printf("I test on a intel 166mmx cpu. 30 may be 40*1024 seconds.\n");
 printf("wish you succeed!\n");
 switch(getch()){
  case 'c':
   printf("do you want to show the result?(y/n)\n");
   printf("print result will be slow!!!\n");
   do{
    mode=getch();
    if(mode=='y')print=1;
    if(mode=='n')print=0;
   }while(mode!='y'&&mode!='n');
   mode=0;
   break;
  case 'g':mode=1;break;
  default:printf("error: nei ther 'c' nor 'g'\n");return;
 }

 printf("processing...\n");
 initgame(N);
 /*
  core here!!!
  only 8 lines, ha!
  here get the level queue
  as 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
 */
 for(i=1;i<(1L<<N);i++){
  q=1L<<N;p=N+1;
  while(q&&i%q){
   q>>=1;
   p--;
  }
  if(mode||print)move(p);
  else move2(p);
 }
 printf("ok\n");
 getch();
 endgame();
}