汉诺塔问题介绍:
相传在古印度圣庙中,有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、由大到小按顺序放置64个金盘(如图1)。游戏的目标:把A杆上的金盘全部移到C杆上,并仍保持原有顺序叠好。操作规则:每次只能移动一个盘子,并且在移动过程中三根杆上都始终保持大盘在下,小盘在上,操作过程中盘子可以置于A、B、C任一杆上。
(该介绍来自——百度百科)
假设只有一个金盘,那么直接从A移动到C即可;
假设金盘数量大于一个,那我们需要将A上边除了最大的金盘以外的所有金盘先借助C移动到B,然后把A剩余的最大的金盘移动到C,再用同样的方法将B上的所有金盘借助A移动到C即可;
即假设A有n个金盘,步骤如下:
1. 将A上 n – 1 个金盘先借助C移动到B;
2. 将A上第n个金盘,也就是最大的金盘移动到C;
3. 将B上 n-1 个金盘借助A移动到C;
完成!
那么如何将 n-1个金盘移动到B呢?
步骤如下:
1. 将A上n – 2 个金盘借助B移动到C;
2. 将A上第 n-1 个金盘移动到B;
3. 将C上 n-2 个金盘移动到B;
完成!
而第一步中要移动 n-2 个金盘到C 也是同理。
通过观察我们可以发现,n不断减小,直到 n 等于 1 时便可以直接挪动。且每一步操作的逻辑相似。由此我们考虑使用
递归
来解决汉诺塔问题。
首先创建需要的变量:
我们需要: 三个柱子A、B、C ,金盘;
所以创建变量:char A; char B; char C; int n; //n为初始时A柱子上的金盘数量;
建议使用scanf()函数以便自定义n的值;
接下来我们来编写汉诺塔游戏的函数,命名为 Hanoi 。
首先考虑Hanoi所需要的参数:
三个柱子,和金盘个数。
先在main函数中继续写出:
Hanoi(A, B, C, n);
这里我们将Hanoi工作的逻辑认作为:通过 B 将 A上 的 n 个金盘移动到C。
你也可以修改游戏规则,比如要求把所有的圆盘移动到B,以进一步理解
代码的逻辑,要自己多做尝试!
由于Hanoi函数未定义,我们要在main函数上边新建函数:
void Hanoi(char A, char B, char C, int n) { }
函数的具体内容如下:
void Hanoi(char A, char B, char C, int n)
{
if (n == 1)
{
m(A,C);
}
else
{
Hanoi(A,C,B,n-1);
m(A,C);
Hanoi(B,A,C,n-1);
}
}
还记得Hanoi的逻辑吗?
代码中,Hanoi(A,C,B,n-1); 的含义为 通过C将A上的n-1个圆盘移动到B上。
那么 Hanoi(B,A,C,n-1); 是不是也很好理解了呢?
这个代码通过递归实现了我们最开始的想法。
在写到 if ( n == 1) 时,考虑如何实现移动,于是暂时用 m()函数来完成移动。
将 Hanoi代码写完后,再补上 m()函数。
该函数的功能是将圆盘A移动到C:
void m(char from, char dest)
{
printf("从%c 移动到%c\n",from,dest);
}
至此,代码关键部分完毕。
全代码如下:
void m(char from, char dest)
{
printf("从%c 移动到%c\n",from,dest);
}
void Hanoi( char A, char B, char C,int n)
{
if (n == 1)
{
m(A,C);
}
else
{
Hanoi(A,C,B,n-1);
m(A,C);
Hanoi(B,A,C,n-1);
}
}
int main ()
{
char A = 'A';
char B = 'B';
char C = 'C';
int n = 0;
scanf("%d", &n);
Hanoi(A,B,C,n);
return 0;
}
总结递归心得:
1. 当逻辑相似,且 上一步是下一步的铺垫,且有尽头
(比如在汉诺塔问题中n-1不断重复总会到n = 1,此时便会停止递归并且逐层返回)
,可以考虑使用递归。
2. 使用递归时,要明确递归函数的逻辑,即意义
(在本问题中为上文红字标出的部分)
。递归时,只要逻辑正确,便可以直接编写递归代码,不要详细考虑递归代码运行时的具体过程,此过程非常繁琐。
我容易犯得错误就是陷入思考递归代码运行的过程,忽略了函数的意义,以至于很难构建函数。
仅分享和记录经验与学习过程。 若有错误,还请大家指正!