经典问题之汉诺塔

问题描述：

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

思路：

以3层的汉诺塔为例：

1、我们可以先将上面两个盘子，借助Z柱移动到Y柱

2、将最后一个盘子移动到Z柱

3、将Y柱的两个盘子，借助X柱移动到Z柱

一切搬圆盘都是在重复上面三个步骤，因此，这三步便是一个递归体，我们可以采用递归的方式实现，至于它到底怎么移动的，我们并不需要知道。

代码实现：

#include <iostream>
using namespace std;

int count = 0;
//将 n 个盘子从 x 借助 y 移动到 z
int move(int n,char x,char y,char z)
{
	if(1 == n){
		count++;  //将最下面的盘子，从x移动到z
		cout << x << "->" << z << endl;
	}
	else{
		move(n-1, x, z, y); //将n-1个盘子，借助z从x移动到y
		cout << x << "->" << z << endl;
		move(n-1, y, x, z); //将n-1个盘子，借助x从y移动到z
		count++;
	}
	return count;
}

int main()
{
	int n;
	cout << "请输入汉诺塔层数：";
        cin >> n;
	move(n,'X','Y','Z');  // X,Y,Z分别表示3个柱子
	cout << "共需要移动：" <<  count << "次" << endl;
	return 0;
}

结果：