递归解决汉诺塔问题---C++实现

问题描述

在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制: (1) 每次只能移动一个盘子; (2) 盘子只能从柱子顶端滑出移到下一根柱子; (3) 盘子只能叠在比它大的盘子上。

为了搞清楚汉诺塔问题，特意去玩了玩该类型的游戏。说真的，我自己玩的不咋滴，不过算法还是搞清楚了。

 

解题思路

这里假设 n 是盘子的个数。 有三个柱子：from，temp，to from表示来源，也就是要从哪里移动。 temp表示通过该柱子去往哪里，临时经过。 to表示最终目的地。 这只是三个柱子的名字，并不是from就是第一根，temp为第二根。并不是这样，柱子的命名视情况而定，有时第一根也可以为命名为temp。

n=1时： 很简单，直接移动到最后一个即可。

n=2时： 我们就利用到了temp柱子，之后from->to，temp->to。

n=3时： 我们要做的就是将最上面的两个盘先移动到第二个柱子上，然后将最下层的盘移动到to柱子上。此时第一个柱子为空，那么把它作为temp柱子，通过temp柱子将刚才的两个盘子移动到to柱子上，完成移动。 n=4时： 其实和n=3类似 先将最上面三个移动到第二个柱子，之后将最下层移动到to。第一根柱子作为temp，将三个盘通过temp移动到to。

以此类推… 除最下面的盘，上面一摞都先移动到第二个柱子。最下面盘移动到第三个柱子，然后将第二根柱子的盘通过temp移动到第三个柱子。 这就是汉诺塔的本质，n无论是几，一定是这样移动的。

那么递归的出口在哪里？ 很显然，每堆盘子剩下最下面的一个时，我们就把他移动到 to 柱子上，这就是出口。

 

C++实现

#include <iostream> #include <iostream> using namespace std; void hnmove(int n,char from,char temp,char to){ if(n==1){ cout << "from " << from << " to " << to << endl; }else{ hnmove(n-1,from,to,temp); //n-1个盘从第一个柱子移动到第二个，第二个柱子为to cout << "from " << from << " to " << to << endl; hnmove(n-1,temp,from,to); //n-1个盘从第二个柱子移动到第三个，第二个柱子为from } } int main(int argc, char** argv) { hnmove(3,'A','B','C'); return 0; }

n=3时的步骤：

 

总结

一定不要试图跟踪大型递归的过程！我们应该掌握规律，从而写出递归。 关键就是找出递归的递归方程式： 也就是说，要完成最后一步，那么最后一步的前一步要做什么。 最重要的还有要找到递归的出口，何时结束递归。