程序员在旅途

用这生命中的每一秒，给自己一个不后悔的未来！

0%

汉诺塔问题的求解与分析

发表于 更新于 分类于 Valine：
本文字数： 2.5k 阅读时长 ≈ 2 分钟

一、递归算法介绍

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

二、汉诺塔问题

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 异常。

相关文章推荐