汉诺塔问题——递归解决

  汉诺塔问题递归比较入门级的问题，主要是引导一个递归的思想和感觉，很多人初次接触递归感觉很懵，而汉诺塔问题就比较典型了。

  问题来源：

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

问题解决思路：

     在问题规模很小的时候，我们想或者上手模拟一下便可得出答案，但在问题规模较大的时候（n个），就没那么容易想出来，但用递归的想法可以大致分为一下三步：

1.从X拿n-1到Y上；

2.把X上最后一个拿到Z上；

3.把n-1个再从Y拿到Z上；

而递归出口就在n=1时。

在这个过程中我们发现，X，Y，Z的身份在不断交换。

代码（c++）：

输入：一个整数n，表示金盘数。

输出：移动的过程和总次数。

#include
using namespace std;
int num = 0;
//X表示原柱，Y表示过渡柱子，Z表示目标柱子，输出移动步骤和总的移动次数
//当有n个园片时，可以递归成为x向y移动n-1个，然后把最后一个移到z上，再将n-1个从y移到z上，出口为n=1时。
void hanoit(int n, char x, char y, char z) {
	if (n == 1) {
		cout <> n;
	hanoit(n, x, y, z);
	cout << "一共移动" << num << "次";
}

3
X向Z移动一个
X向Y移动一个
Z向Y移动一个
X向Z移动一个
Y向X移动一个
Y向Z移动一个
X向Z移动一个
一共移动7次