汉诺塔问题——递归算法

一、问题描述汉诺塔问题是一个经典的问题。汉诺塔Hanoi Tower又称河内塔源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定任何时候在小圆盘上都不能放大圆盘且在三根柱子之间一次只能移动一个圆盘。问应该如何操作二、递归算法个人认为递归算法核心主要有以下几点递归变量、递归过程、递归结束条件其中难点在于怎么模拟递归过程以及如何寻找递归变量对于不同的问题这两个核心所呈现的具体代码都是不一样的但都有共同的特点。所以建议读者不仅仅以解决汉诺塔问题为目标更要理解递归思想掌握递归算法在各种问题中的使用。1.递归变量在每一个能够使用递归算法解决的问题中题目会提供关键信息我们需要在其中找到递归变量这取决于你对信息解剖能力如果一开始无法快速找到递归变量不用过于伤心在往后的不断学习中你会慢慢提高自己的编程能力能够快速分析现实问题和程序之间的关系从而找到递归变量那些变量是在递归函数中表示递归层数或者起到其它作用例如汉诺塔问题中层数n以及柱子位置A,B,C则是递归开始。2.递归过程递归过程是递归算法中的关键行为这个关键行为在解决问题中可以不断重复循环最后递归变量达到结束条件就退出递归函数。如何在问题中找到这个关键行为是较难的但这也是区分您是否理解递归思想。在分析汉诺塔问题我们可以借助位置B先把n-1层以上的圆盘放到B位置然后把第n个圆盘放到C位置上最后将n-1层以上的圆盘放到C位置上那么就能够轻松解决问题了但是对于n-1层是如何移动B位置上的的呢聪明的你可能已经发现n-1层圆盘从A移动到B上其实与n层圆盘移动到C位置上是一样的过程即先把n-2层圆盘放到位置C上再把第n-1个圆盘放到位置B 上最后n-2层圆盘放到B上那么对于n-2层圆盘是如何放到C上的呢?其实这是一个重复性的过程。在这里为了将问题简单化我们设置了三个变量开始位置A、辅助位置B、目标位置C开始位置A放置所有圆盘将n-1层圆盘放置辅助位置B后再将第n个圆盘放置目标位置C然后将n-1层圆盘的位置B作为开始位置A原来的开始位置A作为辅助位置B将所有圆盘放到目标位置C。这个过程的关键点在于什么时候开始位置A和辅助位置B互换我们最开始需要把n-1层圆盘放到辅助位置B在放置n-1层圆盘时我们把辅助位置B当作是目标位置C将其将第n-1个圆盘放到它的目标位置那么如此一来n-2层圆盘需要一个辅助位置所以此时辅助位置B与目标位置互换按照这个想法不断寻找上一层圆盘直至第一层圆盘时我们将其放置在目标位置C上即可注意此时的目标位置C可能不是原来的C然后在回溯的过程中不断输入移动的圆盘作用是看到圆盘移动的过程。当n-1层圆盘移动到辅助位置B时将第n个移动到目标位置C后需要将第n-1个圆盘移动到目标位置C此时则借助开始位置A所以在这里开始位置A需要与辅助位置B互换原本n-1层圆盘所在的位置变成开始位置然后重复搬圆盘的过程直至所有圆盘放入目标圆盘完成递归。3.递归结束条件递归结束条件是用以结束递归过程的重复如果没有结束条件函数将会一直递归下去使得程序陷入死循环中。那么如何找到递归结束条件呢可以从递归变量中寻找例如汉诺塔问题中递归结束条件语句在于层数当发现递归到第一层圆盘时我们可以直接将它放到目标位置上然后就是回溯的过程这个工作就交给计算机我们只需分析问题写出解决问题的代码。三、汉诺塔问题具体代码#include iostream using namespace std; void move(int n, char A, char B, char C) { //n代表现在需要将第n个圆盘放到目标位置C if (n 1) //当递归到第1个圆盘时直接将其放到目标位置C cout A - C endl; else { move(n - 1,A,C,B); //1.将n-1层圆盘放到辅助位置B //2.对于第n-1个圆盘把B当作目标位置C当作辅助位置所以BC互换 cout A - C endl; //将第n个圆盘放到目标位置C上 move(n - 1,B,A,C); //1.将n-1层圆盘放到目标位置C //2.对于n-2层圆盘A当作辅助位置B当作开始位置所以AB互换 } } int main() { move(64,A, B, C); //开始时A是开始位置B是辅助位置C是目标位置 return 0; }注意本代码以64层圆盘移动若需要其他层圆盘只需修改64数字即可。