Question

关于C++ 汉诺塔（Tower of Hanoi）递归算法的一点问题

void Hanoi(int n,char A,char B,char C) //n为要移动的盘数，从A移动到C，B为辅助塔
{
if(n==1) {cout<<"移动盘1从"<<A<<"到"<<C<<endl;}
else
{
Hanoi(n-1,A,C,B);
cout<<“移动盘”<<n<<"从"<<A<<“到”<<C<<endl;
Hanoi(n-1,B,A,C);
}
}

比如说我现在n是3，
执行Hanoi(3,A,B,C)，
进入程序后将执行Hanoi(2,A,C,B)，
这里递归吧。。。执行Hanoi(1,A,B,C)，
再次递归，由于n为1，满足if（n==1） 好了，这将第一个盘移动出去了，
那接下来几部程序执行什么操作？

Answer 1

接下来嘛，由于n==1时已经得出结果了，那当然是算n==2时的结果了，再然后就是n==3,4……，明白了没？

追问

我想问的是程序执行哪一行代码呢。。。难道是hanoi(2 A C B)?这不是又套到递归里面去了吗？

追答

执行的就是hanoi(2 A C B）啊，递归是从最后那个算起的。这样说吧，当你执行n==1的时候，前面的都在执行中，n==1的情况是在n==2时的Hanoi(n-1,A,C,B)和Hanoi(n-1,B,A,C)里面的，当n==1执行完了，n==2时的Hanoi(n-1,A,C,B)就执行完了，然后继续调用Hanoi(n-1,B,A,C)，又执行一次n==1的情况，然后Hanoi(n-1,B,A,C)就执行完了，至此，n==2也执行完了，然后就是n==3，如此类推，明白了吗？

Answer 2

不知道楼主是否理解递归的含义 既然进入到 if(n==1) 中去了 很明显 输出后面的一句话之后, 就跳出Hanoi(1,A,B,C) 这一层了 返回到 Hanoi(2,A,C,B)的 else 中去了啊.

Answer 3

可以用栈的特性来理解递归程序。递归则入栈，遇到出口则出栈。

Answer 4

质汉诺塔
ESC 退出， 空格切换 自动手动
tc 2.0, 3.0 均可运行

#include <dos.h>
#include <fcntl.h>
#include <io.h>
#include <math.h>
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

#define MINDISK 1
#define MAXDISK 15
#define DISKHEIGHT 30
#define TEXT_BIG_CURSOR 0
#define TEXT_NORMAL_CURSOR 7

typedef struct /*16Mrgb像素类型*/
{
unsigned char b;
unsigned char g;
unsigned char r;
}rgb16M;

typedef struct tagDisks
{
int x;
int y;
int Left;
int Top;
int Lenth;
int Height;
int Tag;
int Cylinder1;
int Cylinder2;
int Cylinder3;
}Disks;

void DrawPillar(int number, int bottom);
void DrawDisk(int x, int y, int lenth, int height);
void HanoiMove(int n, int X, int Y, int Z);
void MoveDisk(int n, int DiskFrom, int DiskTo);
void SetXY(Disks *disk, int nX, int nY, int cleardisk);

int disk_num;
int automove = 1;
int toquit = 0;
int delayperiod;
int CylinderHeight[3];
Disks disks[MAXDISK + 1];
rgb16M backcolor = , backcolor1 = ;
rgb16M woodcolor[2][4] = ,,,},,,,}};
rgb16M bordercolor = ;

long woodfillcolor[35][30] = {
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
};

unsigned char set_SVGA_mode(int vmode)
{union REGS r;
r.x.ax=0x4f02;
r.x.bx=vmode;
int86(0x10,&r,&r);
return(r.h.ah);
}

void hide_text_cursor(void)
{union REGS r;
r.h.ah=1;
r.h.ch=32;
int86(0x10,&r,&r);
}

void selectpage(register char page)
{union REGS r;
r.x.ax=0x4f05;
r.x.bx=0;
r.x.dx=page;
int86(0x10,&r,&r);
}

void show_text_cursor(char size)
{union REGS r;
r.h.ah=1;
r.h.cl=size;
r.h.ch=7;
int86(0x10,&r,&r);
}

unsigned int get_SVGA_mode()
{union REGS r;
r.x.ax=0x4f03;
int86(0x10,&r,&r);
return(r.x.bx);
}

unsigned int Vmode=0;
void init16M()
{Vmode=get_SVGA_mode();
hide_text_cursor();
if(set_SVGA_mode(0x118))
{printf("\nSorry, Your graphics driver does not supplied.\n");
show_text_cursor(TEXT_NORMAL_CURSOR);
exit(0);
}
}

void close16M()
{
union REGS r;
r.h.ah = 0;
r.h.al = 3;
int86(0x10, &r, &r);
r.h.ah = 0x05;
r.h.al = 0;
int86(0x10, &r, &r);
}

void putpoint16M(int x, int y, rgb16M color)
{
static int nowpage = 0, lastpage = 50;
static long temp;
unsigned char far *p = (unsigned char *)0xa0000000;
temp = y;
x <<= 2;
temp <<= 12;
temp += x;

nowpage = temp >> 16;
temp &= 0xffff;
if (nowpage != lastpage)
{
static union REGS r;
r.x.ax = 0x4f05;
r.x.bx = 0;
r.x.dx = nowpage;
int86(0x10, &r, &r);
lastpage = nowpage;
}

*((rgb16M *)(p + temp)) = color;
}

void line(int startx, int starty, int endx, int endy, rgb16M color)
{
register int t, distance;
int x = 0, y = 0;
int delta_x, delta_y;
int incx, incy;

delta_x = endx-startx;
delta_y = endy-starty;

if (delta_x > 0) incx = 1;
else if(delta_x == 0) incx = 0;
else incx = -1;
if(delta_y > 0) incy = 1;
else if (delta_y == 0) incy = 0;
else incy = -1;

if (delta_x < 0) delta_x = -delta_x;
if (delta_y < 0) delta_y = -delta_y;

if(delta_x > delta_y) distance = delta_x;
else distance = delta_y;

for (t = 0; t <= distance + 1; t++){
putpoint16M(startx, starty, color);
x += delta_x;
y += delta_y;
if (x > distance){
x -= distance;
startx += incx;
}
if(y > distance){
y -= distance;
starty += incy;
}
}
}

void fillbox(int startx, int starty, int endx, int endy, rgb16M color)
{
int i, j;

if (startx > endx)
{
i = startx;
startx = endx;
endx = i;
}
if (starty > endy)
{
i = starty;
starty = endy;
endy = i;
}
if (startx < 0)
startx = 0;
if (endx > 1023)
endx = 1023;
if (starty < 0)
starty = 0;
else if (endy > 767)
endy = 767;

for (j = starty; j <= endy; j++)
for (i = startx; i <= endx; i++)
putpoint16M(i, j, color);
}

int main(void)
{
int i, j;
int left, top;
int width = 975;
int height = 600;

reinnum:;
printf("input the number of disk(%d-%d, 0 to quit): ", MINDISK, MAXDISK);
delayperiod = 500;
scanf("%d", &disk_num);
if (disk_num == 0)
return 0;
if (disk_num < MINDISK || disk_num > MAXDISK)
goto reinnum;
printf("select play style(0:auto, 1:manual): ");
scanf("%d", &automove);
if (automove != 0)
automove = 1;
if (automove == 0)
{
reintime:;
printf("input the delay period(100-5000): ");
scanf("%d", &delayperiod);
if (delayperiod < 100 || delayperiod > 5000)
goto reintime;
}

init16M();

left = (1024 - width) >> 1;
top = (768 - height) >> 1;;

fillbox(left, top, left + width, top + height, backcolor1);
fillbox(left - 10 , top - 12, left - 2, top + height + 13, bordercolor);
fillbox(left + width + 2, top - 12, left + width + 10, top + height + 13, bordercolor);
fillbox(left, top - 12, left + width, top - 2, bordercolor);
fillbox(left, top + height + 2, left + width, top + height + 13, bordercolor);

for (i = 0; i < 3; i++)
CylinderHeight[i] = 0;

disks[1].Cylinder1 = left + width / 6;
disks[1].Cylinder2 = left + width / 2;
disks[1].Cylinder3 = left + width / 6 * 5;
DrawPillar(1, 0);
DrawPillar(2, 0);
DrawPillar(3, 0);

DrawDisk(disks[1].Cylinder1 - ((width / 4) + 7) / 2 - 20, 673, (width / 4) + 47, 12);
DrawDisk(disks[1].Cylinder2 - ((width / 4) + 7) / 2 - 20, 673, (width / 4) + 47, 12);
DrawDisk(disks[1].Cylinder3 - ((width / 4) + 7) / 2 - 20, 673, (width / 4) + 47, 12);

for (i = disk_num; i >= 1; i--)
{
disks[i].x = 1;
disks[i].y = i;
disks[i].Cylinder1 = left + width / 6;
disks[i].Cylinder2 = left + width / 2;
disks[i].Cylinder3 = left + width / 6 * 5;
disks[i].Height = DISKHEIGHT;
disks[i].Tag = i;
disks[i].Lenth = (width / 4 / disk_num * i) + 7;
SetXY(&disks[i], 1, CylinderHeight[0], 0);
CylinderHeight[0]++;
}

getch();
HanoiMove(disk_num, 1, 2, 3);
getch();

close16M();

return 0;

}

void DrawPillar(int number, int bottom)
{
int x, y = 110;
int lenth = 8, height;
int i, j, m, n;

if (number == 1)
x = disks[1].Cylinder1 - 4;
else if (number == 2)
x = disks[1].Cylinder2 - 4;
else
x = disks[1].Cylinder3 - 4;

if (bottom == 0)
height = 575;
else
height = bottom;

m = 0;
n = 0;
for (i = y + 4; i <= y + height - 1 && i < bottom; i++)
{
for (j = x + 4; j <= x + lenth - 5; j++)
{
woodcolor[0][3].r = (unsigned char)woodfillcolor[n][m];
woodcolor[0][3].g = (unsigned char)(((int)woodfillcolor[n][m])>>8);
woodcolor[0][3].b = (unsigned char)(woodfillcolor[n][m]>>16);
putpoint16M(j, i, woodcolor[0][3]);
m++;
if (m > 29)
m = 0;
}
m = 0;
n++;
if (n > 34)
n = 0;
}

woodcolor[0][3] = backcolor;
for (i = 0 ; i < 4; i++)
{
line(x + i, y + i, x + i, y + height - 1, woodcolor[0][i]);
line(x + i + 1, y + i, x + lenth - i - 1, y + i, woodcolor[0][i]);
line(x + lenth - i - 1, y + i, x + lenth - i - 1, y + height - 1, woodcolor[1][i]);
}

}

void DrawDisk(int x, int y, int lenth, int height)
{
int i, j, m, n;
woodcolor[0][3] = backcolor;

for (i = 0 ; i < 4; i++)
{
line(x + i, y + i, x + i, y + height - i - 1, woodcolor[0][i]);
line(x + i + 1, y + i, x + lenth - i - 1, y + i, woodcolor[0][i]);
line(x + i + 1, y + height + i - 4, x + lenth - 1, y + height + i - 4, woodcolor[1][3 - i]);
line(x + lenth - i - 1, y + i, x + lenth - i - 1, y + height - 4, woodcolor[1][i]);
}

m = 0;
n = 0;
for (i = y + 4; i <= y + height - 5; i++)
{
for (j = x + 4; j <= x + lenth - 5; j++)
{
woodcolor[0][3].r = (unsigned char)woodfillcolor[n][m];
woodcolor[0][3].g = (unsigned char)(((int)woodfillcolor[n][m])>>8);
woodcolor[0][3].b = (unsigned char)(woodfillcolor[n][m]>>16);
putpoint16M(j, i, woodcolor[0][3]);
m++;
if (m > 29)
m = 0;
}
m = 0;
n++;
if (n > 34)
n = 0;
}

}

void MoveDisk(int n, int DiskFrom, int DiskTo)
{
if (toquit == 1)
return;

SetXY(&disks[n], DiskTo, CylinderHeight[DiskTo - 1], 1);
CylinderHeight[DiskFrom - 1]--;
CylinderHeight[DiskTo - 1]++;

}

void SetXY(Disks *disk, int nX, int nY, int cleardisk)
{
if (cleardisk == 1)
{
fillbox(disk->Left, disk->Top, disk->Left + disk->Lenth - 1, disk->Top + disk->Height - 1, backcolor1);
DrawPillar(disk->x, DISKHEIGHT - 35 + 599 - disk->Height * CylinderHeight[disk->x - 1] - 1);
}
disk->x = nX;
disk->y = nY;
switch (nX)
{
case 1 :
disk->Left = disk->Cylinder1 - disk->Lenth / 2;
break;

case 2 :
disk->Left = disk->Cylinder2 - disk->Lenth / 2;
break;

case 3 :
disk->Left = disk->Cylinder3 - disk->Lenth / 2;
break;

default :
;
}

disk->Top = 35 - DISKHEIGHT + 638 - disk->Height * disk->y;
DrawDisk(disk->Left, disk->Top, disk->Lenth, disk->Height);

}

void HanoiMove(int n, int X, int Y, int Z)
{
int a;
if (n == 0 || toquit == 1)
return;
HanoiMove(n - 1, X, Z, Y);
MoveDisk(n, X, Z);

if (toquit == 1)
return;

if (automove == 1)
{
a = getch();
if (a == 0)
{
a = getch();
}
else if (a == 27)
{
toquit = 1;
return;
}
else if (a == 32)
{
automove = 1 - automove;
}
}
else
{
if (kbhit())
{
a = getch();
if (a == 27)
{
toquit = 1;
return;
}
else if (a == 32)
{
automove = 1 - automove;
}
}
delay(delayperiod);
}

HanoiMove(n - 1, Y, X, Z);

}