汉诺塔的动画(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]]