| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2623 人关注过本帖, 1 人收藏
标题:汉诺塔的动画(2) (TC2.0)
只看楼主 加入收藏
hoodlum1980
Rank: 2
来 自:浙江大学
等 级:论坛游民
威 望:2
帖 子:289
专家分:23
注 册:2008-2-24
收藏(1)
 问题点数:0 回复次数:12 
汉诺塔的动画(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 (32.78 KB) 源代码和程序压缩包



hanoi_01.jpg (18.99 KB)
图片附件: 游客没有浏览图片的权限,请 登录注册
收到的鲜花
  • 子洋虾米2008-10-12 13:42 送鲜花  5朵   附言:好文章
  • 永夜的极光2008-10-12 15:05 送鲜花  20朵   附言:好文章
搜索更多相关主题的帖子: 汉诺塔 动画 
2008-10-12 08:44
blueboy82006
Rank: 5Rank: 5
来 自:幻想世界
等 级:贵宾
威 望:16
帖 子:1227
专家分:57
注 册:2007-7-23
收藏
得分:0 
顶一个...

2008-10-12 09:08
ytb745892798
Rank: 1
来 自:漳平。永福
等 级:新手上路
帖 子:63
专家分:0
注 册:2008-9-29
收藏
得分:0 
顶啊,不错!

我的梦想是成为一名出色的程序员!
2008-10-12 11:54
子洋虾米
Rank: 1
来 自:哈尔滨市第九中学
等 级:新手上路
帖 子:79
专家分:0
注 册:2008-9-15
收藏
得分:0 
非常好
呵呵

好花来年开,好景依旧在;趁你还年轻,抓紧搞竞赛。
2008-10-12 13:39
daniel3
Rank: 1
等 级:新手上路
帖 子:16
专家分:0
注 册:2008-9-29
收藏
得分:0 
太厉害了。
2008-10-12 14:10
hcanhong
Rank: 1
来 自:肇庆学院网络工程系
等 级:新手上路
帖 子:58
专家分:0
注 册:2008-9-6
收藏
得分:0 
浙江大学的就是不一样,我们这些普通本科高校的,只能看看这些代码,心里佩服~~
2008-10-12 14:50
永夜的极光
Rank: 6Rank: 6
等 级:贵宾
威 望:27
帖 子:2721
专家分:1
注 册:2007-10-9
收藏
得分:0 
[bo][un]hcanhong[/un] 在 2008-10-12 14:50 的发言:[/bo]

浙江大学的就是不一样,我们这些普通本科高校的,只能看看这些代码,心里佩服~~

无须妄自菲薄,其实并没有你想象的那么难,
认真学,多尝试,最多三个月,任何人都能编的出来,
这和读什么大学没关系

从BFS(Breadth First Study)到DFS(Depth First Study)
2008-10-13 07:58
x313867388
Rank: 1
来 自:中国
等 级:新手上路
帖 子:20
专家分:0
注 册:2008-10-4
收藏
得分:0 
研究研究``
不会再沉底。。
2008-10-13 08:35
guibin
Rank: 1
等 级:新手上路
帖 子:36
专家分:0
注 册:2008-9-22
收藏
得分:0 
强呀,顶。。。
2008-10-13 11:32
forrest123
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2008-10-13
收藏
得分:0 
用VC++打开graphics.h出现错误。VC++里面没有这个库
2008-10-13 14:37
快速回复:汉诺塔的动画(2) (TC2.0)
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.024941 second(s), 11 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved