avatar

汉诺塔问题的求解与分析

一、递归算法介绍

  这篇文章讲的是一个古老而又经典的汉诺塔问题,他是递归算法的一个很好的应用实例。有关递归函数的介绍,在使用递归函数求解字符串的逆置问题文章中介绍过。递归思想是来解决可计算问题的,他的根本特征在于逐步的计算和分解这一计算,通过将某一大问题不断的分解成逻辑上相同的小问题,然后对小问题的求解进而获得最终的答案。使用递归算法的程序在形式上往往都比较简洁明了,这也正是他的价值所在。
  计算机使用栈内存结构来从物理上实现递归算法,每一次的递归调用,系统都要将本次调用的返回地址、局部变量、形式参数等值压入到栈中,调用结束之后,再从栈顶取出保存的信息返回给相应的变量并退出栈,再继续执行递归的上一层函数。由于计算机系统给每一个程序分配的栈空间有限,因此,在使用递归求解问题的时候,一定要注意递归的深度,如果递归的次数太多,很可能会出现栈溢出的情况,导致问题求解失败。

二、汉诺塔问题

2.1 问题由来

相传在古印度圣庙中,有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、由大到小按顺序放置64个金盘。游戏的目标:把A杆上的金盘全部移到C杆上,并仍保持原有顺序叠好。操作规则:每次只能移动一个盘子,并且在移动过程中三根杆上都始终保持大盘在下,小盘在上,操作过程中盘子可以置于A、B、C任一杆上.

柱子模型

2.2 问题分析

  汉诺塔问题是一种多分支的递归解法,相对于单分支的递归解法(如:阶乘的递归解法)来说,不太容易理解,但是只要把握住递归的思想核心就能够理解这个程序的逻辑。汉诺塔解法总结起来有三步骤:

1) 把 N-1个盘子 移到中转柱
2) 把第N个盘子移动到 目标柱
3) 把中转柱上面的N-1个盘子借助目前空闲的柱子 移动到 目标柱。

  注意,上面的中转柱,起始柱,是会变化的。每一层递归的逻辑都是,借助”目标柱子”,将n-1个 盘子移动到 “中转柱”,然后再将最后一个盘子移动到”目标柱子”。
  无论有多少盘子,在移动的过程中,都是遵循上面的三个步骤。在移动第N个盘子的时候,我们总得要想办法把前面N-1个盘子移到中转柱,然后才能将第N个盘子移到目标柱。在移动第N-1个盘子的时候,也是得要把前面N-2个盘子移到中转柱,然后才能把第N-1个盘子移到目标柱。所以,你可以看到,移动N、N-1、N-2···号盘子到目标柱的思路是一样的,因此,我们可以用递归的思想解决这个问题。

2.3 程序实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<stdio.h>

void hnt(int n, char a, char b, char c){

if(n == 1){ // 递归出界条件

printf("%c -- > %c \n", a,c);
}else{
/*
每一层递归的逻辑都是,借助"目标柱子",将n-1个 盘子移动到 "中转柱",然后再将最后一个盘子移动到"目标柱子".

注意,这里的中转柱是会变化的。

*/
hnt(n-1,a,c,b); // ① 借助 c 柱子将a柱子上的n-1个盘子 移动到 b 柱子上

printf("%c -- > %c \n", a,c); // ② 将 a柱子上的第n个盘子 移动到 c柱子上

hnt(n-1, b,a,c); // ③ 将在b柱子上的n-1个盘子,借助 a 柱子(此时a空闲) 移动到 c 柱子上
}
}

int main(){
int n;
scanf("%d", &n);
hnt(n,'a','b','c');
return 0;
}

2.4 程序分析

  通过对汉诺塔问题的分析,你或许会明白,上面的程序是可以求解出问题的答案,但是你可能会有一些疑惑,为什么上面的程序,可以记录下每一步的移动过程?对于这种多分支的递归算法来说,如果像理解单分支递归那样,在脑海中尽可能的穷举出每一步的移动过程,有时候是很困难的,这样也不符合用递归解决问题的原则。但是如果我们实在是想搞明白这每一步具体的过程,怎么办呢?下面用归纳总结的方式,来列出N∈[1,4]的移动过程,分析他的移动规律。
  当N =1时:
移动过程
  当N =2时:
移动过程
  当N =3时:
  通过N=1,N=2的求解,我们可以推断出,N =3的时候,会有 3 + 1 + 3 = 7次移动。3个盘子的话,我们得要先把前两个盘子移到B,然后把第三个盘子移到C,最后再把B上面的两个盘子,借助A移动到C。上面的两个盘子,先是移动到B,然后又移动到C,这两个过程,需要的移动次数是一样的,移动逻辑也是一样的。
移动过程
  当N =4时:
  还是前面的逻辑,N=4的时候,会有 7 + 1 + 7 = 15次移动。思路和前面一样, 把前3个盘子,借助C移到B,再把第四个盘子移到C。
移动过程

  通过前面的几个演示能看得出来,求解 N 和求解 N-1 的思路完全一致,这是保证可以使用递归算法的核心所在。
  A、B、C只是形式上的标注,本质上面的意义是,起始、中转、目标。在移动过程中,如果要保证小的在上,大的在下,我们就必须得要借助中转,才可以实现,至于中转是谁,这和(N-1)这一堆盘子所在的位置有关。
  在写递归程序的时候,需要注意的点如下图所示:
移动过程

三、总结

  递归算法的核心在于递推逻辑,因此,使用递归算法求解问题,我们不必要纠结每一层函数的具体操作是什么样子的,而要把核心放在逻辑上,如果问题的求解是可归纳的,有递推关系在里面,并且是可计算的,那么逻辑上就不存在问题,一般也就可以使用递归算法来求解。
  递归有单分支的递归和多分支递归,单分支相对来说简单理解一些,比如下面的递归程序

int f(int n) //求n的阶乘
{
  int fac;
  if (n == 0 || n == 1)
    fac = 1;
  else
    fac = f(n - 1) * n;
  return fac;
}

  多分支的如汉诺塔、二叉树遍历等,就比较难理解一些,但是思想是一样的。
  计算机执行递归程序的时候,对每一层函数的调用,是使用栈数据结构来进行现场保护的,因此在编写递归程序的时候,要注意递归的深度,防止出现 Stack Overflow 异常。

文章作者: IT之旅
文章链接: https://www.meijindong.top/posts/3531849507.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 程序员在旅途
打赏
  • 微信
    微信
  • 支付宝
    支付宝

评论