c++实现多层汉诺塔问题（信息素养大赛复赛）

问题描述

相信大大家应该做过最经典的汉诺塔题目，那什么是多层汉诺塔呢？

【题目描述】 汉诺塔是一个有意思的游戏，每个柱子上套上多个中心有洞的圆盘，每次只能移动一个圆盘，并且每个圆盘不能放在比它面积小的圆盘的上面。现在有三套圆盘并叠加放在一个柱子上了，请移动圆盘，使每个柱子上的圆盘都按照相同的顺序从大到小的摆放好，也就是把三份盘子平均分开。请问对于 n 个不同数量的圆盘（也就是共有 3*n 个盘子），分别在每个柱子上分好 n 个盘子，最少需 要移动多少步？示意图如下图。

【输入格式】 输入共 1 行，包括一个正整数 n

【输出格式】输出共 1 行，一个整数，表示需要移动圆盘的最少的步骤数。

【样例输入】 1

【样例输出】 2

下面是n=3时的示意图：

解题思路

首先我们要知道经典的汉诺塔是怎么解决的，我们就把最经典的称为一阶n层汉诺塔吧，把题目上要做的称为3阶n层汉诺塔（3阶为一层三个盘子，同理一阶为一层一个盘子）。

一阶n层汉诺塔

我们对一阶汉诺塔的思路就是

（1）当n == 1时，直接把盘子从A柱移动到C柱。（n为层数）

（2）当n > 1时，1.将n - 1个盘子从A---->B

                            2.将第n个盘子从A---->C

                            3.将n - 1个盘子从B---->C

我们用一个图片来解释就是：

A----->B

A------>C

B---->C

步骤（2）明显是个递归调用，一直不断的调用自己，直到层数n==1时结束。

代码实现

#include 
using namespace std;
int count = 0;   //计算步数
 
void hanoi(char a, char b, char c, int n)
          //起始柱  辅助柱  目标柱  层数
{
	if (n == 1)//只有一层的时候，直接A-->C
	{
		cout << a << " --> " << c << endl;
		count++;
	}
	else
	{
		hanoi(a, c, b, n - 1);   //将n-1个盘子从A柱-->B柱，借助于C柱
		hanoi(a, b, c, 1);       //将第n个盘子A柱-->C柱，一步
		hanoi(b, a, c, n - 1);   //将n-1个盘子从B柱-->C柱，借助于A柱
	}
}
int main() {
	int n;
	cout << "请输入需要的层数：";
	cin >> n;  //层数
	hanoi('A', 'B', 'C', n);
	cout << "一共" << count << "步";
	return 0;
}

我们解决了一阶汉诺塔之后就可以开始来思考多层汉诺塔，那我们多层汉诺塔是不是也可以用同样的思路呢，我们先来分析一下题目是什么意思。

三阶n层汉诺塔

思考一下当n=1,2,3,4,5......n时，移动前和移动后分别是什么样子的，如图所示，n为层数，3阶为一层有3个盘子。移动过后变成了一阶n层的样子。

思路分析

现在我们知道了开始和结果是什么样的，那过程是什么样的呢？我们从n=1是来观察，只需要移动两步就可以解决了：A-->B,A-->C。

当n==2时，我们将第一层从A--->B，借助于C柱，

                          将第二层的第一个盘子从A--->C，

                          将第一层从B--->C，借助于A柱，

                          将第二层的第二个盘子从A--->B，这样我们最后一层我们就放好了（n-1）。

                          现在只有一层了，移动方法和第一层一样（相当于递归调用）。

注意：这里我们在移动第一层的时候相当于把第一层的三个盘子看成一个整体，但是移动的时候是一个盘子一个盘的移动。

当n==3的时候，一共有3x3=9个盘子，我们将上面两层看做一个整体去移动他：

                          将第一二层从A--->B，借助于C柱，

                          将第三层的第一个盘子从A--->C，

                          将第一二层从B--->C，借助于A柱，

                          将第二层的第二个盘子从A--->B，这样我们最后一层我们就放好了（n-1）。

现在我们就可以用同样的方法移动第二层和第一层。只不过第二层时从C柱开始。

思路总结

从上面我们可以分析出如果是n==4时，也可以用同样的方法，n==n的时候也可以用同样的方法。

当有n层时，一共有3n个盘子，我们首先移动上面的n-1层：

                    1.将第n-1层从A--->B，借助于C柱，

                    2.将第n层的第一个盘子从A--->C，

                    3. 将第n-1层从B--->C，借助于A柱，

                    4. 将第n的第二个盘子从A--->B，这样我们就放好了第n层。

注意 ：

我们把n-1层看做一个整体，把每一层的三个盘子看做一个整体，就相当于是一个一阶n-1层的汉诺塔。那么我们在移动n-1层时，就相当于一阶n-1层汉诺塔从一个柱子移动到另一个柱子，这个过程和一阶汉诺塔过程是一样的。所以我们在移动时是调用的一阶汉诺塔的函数进行操作的。当一层移动完之后再递归调用三阶汉诺塔函数。直到n==1时是递归调用的结束标志。

核心代码

	if (n > 1) {
		hanoi1(a, c, b, n - 1);          // 把n-1层从A-->B，借助于C柱
		cout << a << "-->" << c << endl; // 把第n层的第一个盘子从A--->C
		hanoi1(b, a, c, n - 1);          // 把n-1层从B-->C，借助于A柱
		cout << a << "-->" << b << endl; // 把第n层的第二个盘子从A--->B
		hanoi2(c, a, b, n - 1);          // 交换，因为n-1层在c柱，然后继续重复调用自己
	}
	else if (n == 1)  //如果只有一层的话就之有两步
	{
		cout << a << "-->" << b << endl; 
		cout << a << "-->" << c << endl;
	}

打印步骤的代码实现

#include 
using namespace std;
int count = 0;  //计算步骤
 
void hanoi1(char a, char b, char c, int n) {
	if (n == 1) {
		for (int i = 0; i < 3; i++) {
			count++;
		}
	}
	else {
		hanoi1(a, c, b, n - 1);  
		hanoi1(a, b, c, 1);   
		hanoi1(b, a, c, n - 1);
	}
}
 
void hanoi2(char a, char b, char c, int n)
{
	if (n > 1) {
		hanoi1(a, c, b, n - 1);  // 把n-1层从A-->B，借助于C柱
		count++;                 // 这里步骤加1是因为第n层的第一个盘子从A-->C
		hanoi1(b, a, c, n - 1);  // 把n-1层从B-->C，借助于A柱
		count++;                 // 这里步骤加1是因为第n层的第二个盘子从A-->B
		hanoi2(c, a, b, n - 1);
	}
	else if (n == 1)   //当只有1层时，只需要移动两步；
	{
		count++;
		count++;
	}
}
 
int main() {
	int k;//层数
	cin >> k;
	hanoi2('A', 'B', 'C', k);
	cout << "一共" << count << "步";
	return 0;
}

打印过程的代码实现

#include 
using namespace std;
 
void hanoi1(char a, char b, char c, int n) {
	if (n == 1) {
		cout << a << "-->" << c << endl;
		cout << a << "-->" << c << endl;
		cout << a << "-->" << c << endl;
	}
	else {
		hanoi1(a, c, b, n - 1);
		hanoi1(a, b, c, 1);
		hanoi1(b, a, c, n - 1);
	}
}
 
void hanoi2(char a, char b, char c, int n)
{
	if (n > 1) {
		hanoi1(a, c, b, n - 1);
		cout << a << "-->" << c << endl;
		hanoi1(b, a, c, n - 1);
		cout << a << "-->" << b << endl;
		hanoi2(c, a, b, n - 1);
	}
	else if (n == 1)
	{
		cout << a << "-->" << b << endl;
		cout << a << "-->" << c << endl;
	}
}
 
int main() {
	int k;
	int count = 0;
	cin >> k;
	hanoi2('A', 'B', 'C', k);
	return 0;
}

运行结果

当层数n==3的时候，运行结果为30步（打印步数）

当层数n=3时，打印步骤运行结果为：

 

 

这个题还可以使用数学方法来解决，将在下一章讲到。