汉诺塔的动画（2） （TC2.0）
之前在论坛看到过Lydolphin做的汉诺塔的动画，我觉得比较新颖，因此我参考和借鉴他的做法，也做了一个，效果几乎是一样的（因此标题加了一个2）。不过编码实现时候的想法估计肯定略有不同。Lydolphin的代码中存在过多的“hard code”，在我的代码里试图改进这一点。此外，Hanoi函数我也参考了他的代码，Hanoi2函数引用自《C算法》的第五章5.2节。PS，有些电脑环境可能无法运行tc下的一些绘图或引用了特定头文件的程序，例如vista系统，那就没有办法看到效果了。
如果想改变盘子的个数，可以使用命令行，例如，在DOS SHELL下，输入“HANOI_~1 8”，回车，则盘子个数n即为8，程序将对n逻辑验证，允许值是在1到10之间。
代码如下：
程序代码：/*-------------------------------------------------------------------
* Desc: 汉诺塔动画
* Author: hoodlum1980
* Date: 2008.10.12
* Email: jinfd@*/
#include <graphics.h>
#include <stdlib.h>
#include <stdio.h>
/*---------------------------常量定义--------------------------------*/
#define XWIDTH 160 /*每个柱子占据的水平宽度*/
#define XHEIGHT 300 /*所有柱子的高度*/
/*全局场景的矩形*/
#define BLEFT (300-XWIDTH*3/2-20)
#define BRIGHT (300+XWIDTH*3/2+20)
#define BTOP 50
#define BBOTTOM (BTOP+XHEIGHT+40)
/*每个柱子的中心所在横坐标*/
#define POLE_CXA (300-XWIDTH)
#define POLE_CXB 300
#define POLE_CXC (300+XWIDTH)
#define POLE_BOTTOM (BTOP+XHEIGHT) /*所有柱子的水平面坐标*/
#define POLE_TOP (BTOP+100) /*所有柱子的顶部坐标*/
#define POLE_THICK 12 /*柱子厚度*/
/*绘制圆饼的参数*/
#define DISK_THICK 10 /*圆盘厚度*/
#define DISK_MINWIDTH (POLE_THICK+12) /*最小的圆盘宽度*/
#define DISK_MAXWIDTH (XWIDTH-20) /*最大的圆盘宽度*/
#define DISK_INCSIZE 10 /*圆盘宽度增长值*/
#define DISK_MAXCOUNT 10 /*最大圆盘数*/
#define DISK_GAP 1 /*相邻圆盘的垂直距离间隔*/
#define DISK_FLYHEIGHT (POLE_TOP - (DISK_THICK)*3) /*圆盘的飞行高度*/
/*延时的参数*/
#define DELAY_COUNT 1600 /*绘制时，delay()的参数*/
/*颜色定义*/
#define COLOR_POLE BLACK /*Pole颜色*/
#define COLOR_POLEBORDER LIGHTGRAY /*Pole边框颜色*/
#define COLOR_BKGND DARKGRAY /*背景颜色*/
#define COLOR_DISK YELLOW /*圆盘的填充色*/
#define BGI_PATH "" /*驱动路径*/
/*圆盘信息结构*/
typedef struct tagDISK
{
int cx; /*中心坐标cx*/
int y; /*上边缘cy*/
int halfwidth; /*宽度的一半*/
int atPole; /*它位于哪一个Pole上，hanoi2要用到这个信息*/
void *pImage; /*缓存的背景*/
} DISK, *PDISK;
/*---------------------------全局变量--------------------------------*/
int PoleCx[3]; /*记录每一个Pole的中心坐标*/
int DiskCount[3]; /*记录每一个POLE上面当前的圆盘数量*/
int DiskNo[DISK_MAXCOUNT][3]; /*记录每一个Pole上面的圆盘的索引*/
PDISK Disks[DISK_MAXCOUNT]; /*所有圆盘的指针*/
/*---------------------------函数声明--------------------------------*/
DISK* NewDisk(int cx1, int y1, int width1);
void DeleteDisk(DISK* disk);
void RecorverBkGnd(DISK *disk);
void DrawDisk(DISK *disk, int cx1, int y1);
int GetNextDiskTop(int count);
void textout(int x, int y, char* text, int color, int bordercolor);
void textoutwithborder(int x, int y, char* text, int color, int bordercolor);
void Init(int n);
void Quit(int n);
void MoveDisk(int from, int to);
void Hanoi(int n, int from, int to, int aux);
void Hanoi2(int n, int d);
int main(int argc,char *argv[]);
/*---------------------------函数体集合------------------------------*/
DISK* NewDisk(int cx1, int y1, int width1)
{
DISK* disk=(DISK*)malloc(sizeof(DISK));
disk->cx=cx1;
disk->y=y1;
disk->halfwidth=width1/2;
disk->atPole=0;/*默认位于A上*/
disk->pImage=NULL;
return disk;
}
/*释放所有DISK内存*/
void DeleteDisk(DISK* disk)
{
if(disk!=NULL && disk->pImage!=NULL)
free(disk->pImage);
if(disk!=NULL)
free(disk);
}
/*复原被DISK移动后的背景，这样会比putimage和getimage提高绘制时的效率！*/
/*这个方法虽然高效，但是情形过分特殊，即不能通用！*/
void RecorverBkGnd(DISK *disk)
{
setcolor(COLOR_BKGND);
rectangle(disk->cx - disk->halfwidth, disk->y, disk->cx + disk->halfwidth, disk->y+DISK_THICK);
/*看是否需要绘制POLE*/
if(disk->y >= POLE_TOP)
{
setcolor(COLOR_POLE);
line(disk->cx - POLE_THICK/2+1, disk->y, disk->cx + POLE_THICK/2-1, disk->y);/*柱心*/
putpixel(disk->cx - POLE_THICK/2, disk->y, COLOR_POLEBORDER);/*柱子边框*/
putpixel(disk->cx + POLE_THICK/2, disk->y, COLOR_POLEBORDER);
}
if(disk->y + DISK_THICK >= POLE_TOP) /*圆盘*/
{
setcolor(COLOR_POLE);
line(disk->cx - POLE_THICK/2, disk->y + DISK_THICK, disk->cx + POLE_THICK/2, disk->y + DISK_THICK);
putpixel(disk->cx - POLE_THICK/2, disk->y + DISK_THICK, COLOR_POLEBORDER);
putpixel(disk->cx + POLE_THICK/2, disk->y + DISK_THICK, COLOR_POLEBORDER);
}
/*是否应该重绘柱顶边框*/
if(disk->y == POLE_TOP || disk->y + DISK_THICK == POLE_TOP )
{
setcolor(COLOR_POLEBORDER);
line(disk->cx - POLE_THICK/2, POLE_TOP, disk->cx + POLE_THICK/2, POLE_TOP);
}
}
/*绘制圆盘 cx1-中心横坐标，cy1-中心纵坐标*/
void DrawDisk(DISK *disk, int cx1, int y1)
{
/*复原背景*/
RecorverBkGnd(disk);
/*更新坐标*/
disk->cx=cx1;
disk->y=y1;
/*绘制它*/
setfillstyle(SOLID_FILL, COLOR_DISK);
setcolor(BLACK);
bar(disk->cx - disk->halfwidth + 2, disk->y + 2, disk->cx + disk->halfwidth - 2, disk->y + DISK_THICK - 2);
/*连续绘制两个矩形边框，注意向内扩！*/
rectangle(disk->cx - disk->halfwidth, disk->y, disk->cx + disk->halfwidth, disk->y + DISK_THICK);
rectangle(disk->cx - disk->halfwidth+1, disk->y+1, disk->cx + disk->halfwidth-1, disk->y + DISK_THICK - 1);
}
/*根据某个柱上已有的圆盘数，计算出下一个放到上面的圆盘的Y坐标*/
/*count表示当前已经有的圆盘数量！*/
int GetNextDiskTop(int count)
{
int basement = POLE_BOTTOM - DISK_THICK - DISK_GAP; /*从水平面上升一定位置的基点*/
return basement - (DISK_THICK + DISK_GAP)*count; /*cy*/
}
/*输出带有阴影的文本*/
void textout(int x, int y, char* text, int color, int bordercolor)
{
setcolor(bordercolor);
outtextxy(x+1,y+1,text);
setcolor(color);
outtextxy(x,y,text);
}
/*输出带有边框的文本*/
void textoutwithborder(int x, int y, char* text, int color, int bordercolor)
{
int i,j;
setcolor(bordercolor);
for(i=-1;i<=1;i++)
for(j=-1;j<=1;j++)
if(i || j) outtextxy(x+i,y+j,text);
setcolor(color);
outtextxy(x,y,text);
}
/*初始化场景, 参数n表示圆盘数量*/
void Init(int n)
{
int gdriver=DETECT, gmode, i;
initgraph(&gdriver, &gmode, BGI_PATH);
setcolor(LIGHTGRAY);
/*绘制背景矩形*/
setfillstyle(SOLID_FILL, COLOR_BKGND);
bar(BLEFT+4, BTOP+4, BRIGHT-4, BBOTTOM-4);
/*所有元素绘制应该一律向内扩，不要外扩，以免无法确定该元素的边界*/
rectangle(BLEFT,BTOP,BRIGHT,BBOTTOM);
rectangle(BLEFT+1,BTOP+1,BRIGHT-1,BBOTTOM-1);
rectangle(BLEFT+3,BTOP+3,BRIGHT-3,BBOTTOM-3);
/*柱子边框*/
setcolor(COLOR_POLEBORDER);
rectangle(POLE_CXA-POLE_THICK/2, POLE_TOP, POLE_CXA+POLE_THICK/2, POLE_BOTTOM);
rectangle(POLE_CXB-POLE_THICK/2, POLE_TOP, POLE_CXB+POLE_THICK/2, POLE_BOTTOM);
rectangle(POLE_CXC-POLE_THICK/2, POLE_TOP, POLE_CXC+POLE_THICK/2, POLE_BOTTOM);
/*底盘边框*/
rectangle(POLE_CXA-XWIDTH/2, POLE_BOTTOM, POLE_CXC+XWIDTH/2, POLE_BOTTOM+POLE_THICK);
/*填充柱子*/
setfillstyle(SOLID_FILL, COLOR_POLE);
bar(POLE_CXA-POLE_THICK/2+1, POLE_TOP+1, POLE_CXA+POLE_THICK/2-1, POLE_BOTTOM);
bar(POLE_CXB-POLE_THICK/2+1, POLE_TOP+1, POLE_CXB+POLE_THICK/2-1, POLE_BOTTOM);
bar(POLE_CXC-POLE_THICK/2+1, POLE_TOP+1, POLE_CXC+POLE_THICK/2-1, POLE_BOTTOM);
/*填充底盘*/
bar(POLE_CXA-XWIDTH/2+1, POLE_BOTTOM+1, POLE_CXC+XWIDTH/2-1, POLE_BOTTOM+POLE_THICK-1);
/*用自定义的函数绘制柱子的字母名称，A，B，C*/
settextjustify(CENTER_TEXT, TOP_TEXT); /*水平居中*/
textout(POLE_CXA, POLE_BOTTOM+POLE_THICK+4, "A", BROWN, BLACK);
textout(POLE_CXB, POLE_BOTTOM+POLE_THICK+4, "B", BROWN, BLACK);
textout(POLE_CXC, POLE_BOTTOM+POLE_THICK+4, "C", BROWN, BLACK);
settextjustify(LEFT_TEXT, TOP_TEXT);
/*记录每个Pole的中心横坐标*/
PoleCx[0]=POLE_CXA;
PoleCx[1]=POLE_CXB;
PoleCx[2]=POLE_CXC;
for(i=0;i<n;i++)
{
/*从小到大，创建圆盘，最小的圆盘在上面*/
Disks[i]=NewDisk(
PoleCx[0], /*cx*/
GetNextDiskTop(n-1-i), /*cy*/
DISK_MINWIDTH + DISK_INCSIZE*i /*最大宽度不得超过XWIDTH*/
);
DiskNo[i][0]=n-1-i;/*设置A柱上的所有圆盘*/
DrawDisk(Disks[i], Disks[i]->cx, Disks[i]->y);/*绘制圆盘*/
}
DiskCount[0]=n;/*把n个圆盘位于POLE_A上*/
/*一些额外信息字符串*/
setcolor(LIGHTGRAY);
outtextxy(PoleCx[1]+40, BBOTTOM+20, "HANOI - by hoodlum1980");
outtextxy(PoleCx[1]+130, BBOTTOM+40, "2008.10.12");
}
/*退出前，把申请的所有disk的内存全部清理掉*/
void Quit(int n)
{
int i;
for(i=0;i<n;i++)
DeleteDisk(Disks[i]);
closegraph();
}
/*移动圆盘*/
void MoveDisk(int from, int to)
{
int i,j,index,step,floor;
DISK *disk;
/*from柱子上的最顶上面的一个DISK的索引号*/
index=DiskNo[ DiskCount[from]-1 ][from];
disk=Disks[ index ];
/*圆盘上升到飞行高度*/
while(disk->y > DISK_FLYHEIGHT)
{
DrawDisk(disk, disk->cx, disk->y-1);
delay(DELAY_COUNT);
}
/*在最高处位置水平移动圆盘*/
step = to > from? 1:-1;
while(disk->cx != PoleCx[to])
{
DrawDisk(disk, disk->cx+step, disk->y);
delay(DELAY_COUNT);
}
/*圆盘下落到最低高度*/
floor=GetNextDiskTop(DiskCount[to]);
while(disk->y < floor)
{
DrawDisk(disk, disk->cx, disk->y+1);
delay(DELAY_COUNT);
}
/*更新圆盘数量，索引号信息*/
disk->atPole=to;/*更新DISK的所在POLE*/
DiskCount[from]--;
DiskCount[to]++;
DiskNo[ DiskCount[to]-1 ][to]=index; /*已经移动到to*/
}
/*三个POLE分别用0，1，2表示, from-所在pole, to-目标pole, aux-辅助pole*/
void Hanoi(int n, int from, int to, int aux)
{
if(n==1)
MoveDisk(from, to);
else
{
Hanoi(n-1, from, aux, to);/*把上面n-1个借助to移动到aux*/
MoveDisk(from, to);
Hanoi(n-1, aux, to, from);/*把aux上的n-1个借助from移动到to*/
}
}
/*汉诺塔的另一个解法，n表示当前要移动哪个圆盘（以1为base）*/
/* d = 1表示向右移动（如果已经是最右则放到最左），d = -1表示向左移动*/
void Hanoi2(int n, int d)
{
if(n==0) return;
Hanoi2(n-1, -d);
/*d+3将保证它为正数！*/
MoveDisk((Disks[n-1])->atPole, ( (Disks[n-1])->atPole + d + 3 )%3 );
Hanoi2(n-1, -d);
}
/* Entry Point */
int main(int argc,char *argv[])
{
int i,n=4;
if(argc>1)
{
n=atoi(argv[1]); /*注意：argv[0]是应用程序的路径*/
if(n<=0 || n>DISK_MAXCOUNT) return 0;
}
Init(n);
/*Hanoi(n, 0, 2, 1);*/ /*设Pole B为辅助，从A移动C*/
Hanoi2(n, -1);/*把第N个盘向左移动，即从A到C*/
getch();
Quit(n);
return 0;
}[[it] 本帖最后由 hoodlum1980 于 2008-10-20 16:04 编辑 [/it]]
Hanoi_JFD.rar
