递归__汉诺塔问题

一.问题描述

汉诺塔：汉诺塔(Tower of Hanoi)源于印度传说中，大梵天创造世界时造了三根金钢石柱子，其中一根柱子自底向上叠着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

这是一道非常经典的题目，笔者还在高中就接触过，最近又在书上看见此题，我以为我懂，但仔细去理解，又感觉玄之又玄，看来非得深入理解一下才行，希望此文对大家有帮助，如有错误还望指正。

二.问题分析

通过问题描述已经初步了解了问题，如果感觉理解不清晰可以找汉诺塔玩具和相关游戏加深理解。

 

 这是示意图，A是起始柱，C是目标柱，B起到中转作用在进行转移操作时，都必须确保大盘在小盘下面，且每次只能移动一个圆盘，最终c柱上有所有的盘子且也是从上到下按从小到大的顺序。

问题看起来好像很复杂，不要被题目中的64个圆盘吓到了，我们可以减少问题规模来理解，复杂度会降低很多，但问题没有发生变化。

       当A柱子上只有一个盘子时只要把那个盘子直接移到C就行了

       有两个盘子的话把1号盘先移到B柱，在把2号盘移到C柱，最后把B柱上的1号盘移到C柱就行了

       但我们现在的问题是64个盘子，怎么办呢？

       ① 我们可以把上面63个圆盘看成一个整体，将63个盘子移动到B柱，再将第64个盘子移动到C柱。

 

       ② 再假设现在A柱上有63个盘子，我们将上面62个盘子看做一个整体，将62个盘子移动到B柱，再将第63个盘子移动到C柱。

③ 这时候问题再继续下去，一步一步直到找到可以直接移动的盘子（单个的盘子!!!），62,61,60，......，2,1。最上面的盘子是可以直接移动到C柱的，第2个盘子也可以转移到C柱，第3个也可以，第4个......直到第64个。

对于汉诺塔问题，我们在写递归式时只需要确定两个条件

       ① 结束条件？（n等于1的时候）

       ② 递归式是什么？（将第n个盘子移动到C柱，上一步需要做什么？）

话不多说，上C代码

void Hanoi(int n, char a, char b, char c) {  // 将 n 个盘子从 a 通过 b 移动到 c
	if (n > 1) {
		Hanoi(n - 1, a, c, b); // 先将前 n-1 个盘子从 a 处通过 c 处移动到 b 处 
		printf("将第 %d 个盘子从 %c 移动到 %c \n", n, a, c); // 直接将第 n 个盘子从 a 处移动到 c 处 
		Hanoi(n - 1, b, a, c); // 再将前 n -1 个盘子从 b 处通过 a 处移动到 c 处   
	} else {
		printf("将第 %d 个盘子从 %c 移动到 %c \n", n, a, c); // 只有一个盘子时，直接从 a 处移动到 c 处
	} 
}

对于这种大型递归问题，不建议直接上手推导，不信可以试试，分分钟逝世哈哈哈，同样的，我们可以缩小问题规模，将盘子的数量控制在个位数自己推导一下，不仅有助于问题理解，还可以锻炼思维。

补充：关于递归你不得不知道的数据结构知识

       ① 栈（stack）：先进后出的特性，所以递归程序的答案都是自底而上的。

       ② 二叉树 ：可以尝试通过二叉树的数据结构来理解递归是如何将一个问题拆分成若干子问题，求解再回溯的。

 

参考资料:汉诺塔问题