【汉诺塔】汉诺塔问题深入讲解

关于汉诺塔问题，小编在这里做了一些小结，分享给大家！

汉诺塔问题及其变式

1、标准汉诺塔问题

（1）问题引入

问题描述： 有三根柱子（A、B、C）和 n 个大小不同的盘子，初始盘子都叠在 A 柱，小盘子在大盘子上面。 要求：

• 每次只能移动一个盘子
• 大盘子不能放在小盘子上面
• 把所有盘子从 A 柱 → C 柱（B 做辅助）

（2）算法设计

① 针对于这个标准汉诺塔问题，我们的思路是使用 递归 的方式来实现，这套 算法的思路 设计如下：

递归思路：

• 先把 n – 1 个盘子 从 A → B（C 做辅助）
• 把 最后 1 个大盘子 从 A → C
• 再把 n – 1 个盘子 从 B → C（A 做辅助）

② 所以我们接下来去设计这个递归调用函数，先考虑 参数部分：

• 首先我们需要有 盘子个数 n
• 其次我们需要 三根柱子
  • 源头柱子 src
  • 辅助移动的柱子：temp
  • 目标柱子（最终要移到的柱子）：dest
• 最后我们需要计算的是移动的次数，所以我们还需要引入一个 计数器 count

③ 好的，参数部分我们已经设计完成，接下来就是对 移动的情况进行分析，从而确定递归的终止条件和递归的迭代部分：

• 当 源头柱子上只有一个盘子的时候，只需要将它从源头柱子（A 柱）移到目标柱子（C 柱），此时计数器加 1 即可（所以这就是递归的 终止条件，只要源头柱子上还有很多盘子，就要递归移动，直到只剩下一个盘子）
• 当 源头柱子上还有不止一个盘子，就递归移动，同时计数器做好累加

④ 那么接下来我们就 根据上面的算法 对这个函数进行封装实现：

/// <summary>
/// 标准汉诺塔问题解法 – 递归实现
/// </summary>
/// <param name="n"></param> 盘子个数
/// <param name="src"></param> 源头柱子
/// <param name="temp"></param> 辅助柱子
/// <param name="dest"></param> 目标柱子
/// <param name="count"></param> 移动次数
void HanNuoTa(int n, char src, char temp, char dest, int& count)
{
//1.情况一：源头柱子只有一个盘子
if (1 == n)
{
count++;//计数器累加
return;//返回，递归结束
}
//2.情况二：源头柱子上还有不止一个盘子，就要继续递归移动下去
//2.(1)先将源头柱子上面的 n-1 个盘子从源头柱子借助目标柱子移到辅助柱子
//盘子数 源头柱子(源头) 目标柱子(辅助作用) 辅助柱子(目标) 移动次数
HanNuoTa(n – 1, src, dest, temp, count);
//2.(2)再将源头柱子上剩下的那个最大的盘子从源头柱子上移到最后的目标柱子上
count++;//因为这一步我们只移动了那个最大的盘子，所以只需要计数一次即可
//2.(3)最后将辅助柱子上面的 n-1 个盘子从辅助柱子上移动到最后的目标柱子上
//盘子数 辅助柱子(源头) 源头柱子(辅助作用) 目标柱子(目标) 移动次数
HanNuoTa(n – 1, temp, src, dest, count);
//注意，这一步不需要单独计数，因为这里的 n-1 个盘子是需要递归调用回去的，调回去了会继续计算
//也就是调回去以后，先判断 n-1 个盘子是否是只有一个盘子了，还是不止一个盘子
//这一点需要着重理解，以及第二步的时候，只需要移动一个盘子，所以只需要计数一次即可
}
int main()
{
int n = 0;//盘子个数
while (cin >> n)
{
int count = 0;//移动次数
HanNuoTa(n, 'a', 'b', 'c', count);
cout << count << endl;
}
return 0;
}

2、汉诺塔牛客网实例1（原模型）

典型例题：牛客网：汉诺塔 点击链接即可跳转牛客网做这道题

描述：

有三根杆子 A,B,C。A 杆上有 n 个穿孔圆盘，盘的尺寸由下到上依次变小。请你按下列规则，使用尽可能少的移动次数将所有圆盘移至 C 杆：

• 每次只能移动一个圆盘。

• 大盘不能叠在小盘上面。

输入描述：

第一行输入一个整数 n(1≦n≦20)n(1≦n≦20)。

输出描述：

对于每次操作，新起一行。输出两个字母 X Y 代表移动 X 杆顶端的盘子至 Y 杆。

示例1

输入：

2

输出：

A B
A C
B C

示例2

输入：

3

输出：

A C
A B
C B
A C
B A
B C
A C

题目分析：

① 和标准汉诺塔问题一样，我们可以分三步来实现：

• 先把 n – 1 个盘子 从 A → B（C 做辅助）
• 把 最后 1 个大盘子 从 A → C
• 再把 n – 1 个盘子 从 B → C（A 做辅助）

② 需要注意的是，我们需要输出的信息是从哪里移动到哪里，也就是源盘子和目的盘子，而非源盘子和辅助盘子

#include <iostream>
using namespace std;
// 汉诺塔递归函数
// n: 盘子数量
// src: 源杆
// temp: 辅助杆
// dest: 目标杆
void HanNuoTa(int n,char src,char temp,char dest)
{
if(1==n)
{
cout<<src<<" "<<dest<<endl;// 递归终止条件：只有 1 个盘子时，直接从源杆移到目标杆
return;
}
HanNuoTa(n–1, src, dest, temp);//1：把 n-1 个盘子从 src 借助 dest 移到 temp
cout<<src<<" "<<dest<<endl;//2：把第 n 个盘子从 src 直接移到 dest
HanNuoTa(n–1, temp, src, dest);//3：把 n-1 个盘子从 temp 借助 src 移到 dest
}
int main()
{
int n=0;
cin>>n;
HanNuoTa(n, 'A', 'B', 'C');
return 0;
}

2、汉诺塔变式（只能相邻柱子移动）

典型例题：牛客网：大吉大利，今晚吃鸡 点击这个链接即可跳转牛客网做这道题哦

描述

糖和抖m在玩个游戏，规定谁输了就要请谁吃顿大餐：抖m给糖a b c三个驻， 并在a柱上放置了数量为n的圆盘，圆盘的大小从上到下依次增大，现在要做的事就是把a柱的圆盘全部移到c柱，移动的过程中保持小盘在上，大盘在下，且限定圆盘只能够移动到相邻的柱子，即a柱子上的圆盘只能够移动到b，b柱子上的圆盘只能够移动到a或者c，c同理。现在请你设计一个程序，计算所需移动的最小步数， 帮助糖赢得大餐！

输入描述：

每一行输出有一个整数 n (0<=n<26), 直至文件末尾。

输出描述：

对于每一组数据，输出一行，输出移动的最小步数M。

示例1

输入：

1

输出：

2

① 题目限定我们 只能在相邻的盘子间进行移动，且从题目中我们可以看出，盘子个数有可能为 0 （整数 n (0<=n<26)），那么对于这道题目，就存在 两个递归终止条件：

• 没有盘子，无需移动，直接返回
• 只有1个盘子，只能相邻移动，从 src 到 dest 必须经过 temp，共2步

② 分析完题目以后，那么这道题我们的 算法设计思路 如下：（依据标准汉诺塔 3 步修改，扩充两个额外步骤）

注意：下面我荧光笔标记的部分是我们按照题目要求实现相邻柱子移动的关键所在，对比标准汉诺塔算法，我们可以发现，标准汉诺塔算法是步步跨盘子

• 第一步：把 n-1 个盘子 从源头柱子 src 移动到目标柱子 dest （借助 temp 中转）实现相邻
• 移动第 n 个盘子：从 src 移动到 temp（相邻移动，步数 +1）
• 第二步：把 n-1 个盘子 从目标柱子 dest 移动回源柱子 src （借助 temp 中转）实现相邻
• 移动第 n 个盘子：从 temp 移动到 dest（相邻移动，步数 +1）
• 第三步：把 n-1 个盘子 从源头柱子 src 再次移动到目标柱子 dest （借助 temp 中转）实现相邻

③ 那么 根据上面的算法，我们接下来对递归函数进行封装

//牛客网：大吉大利，今晚吃鸡
//https://www.nowcoder.com/share/jump/1502296931779205719261
#include <iostream>
using namespace std;
/// <summary>
/// 汉诺塔变式
/// </summary>
/// <param name="n"></param> 盘子数量
/// <param name="src"></param> 源头柱子
/// <param name="temp"></param> 辅助柱子
/// <param name="dest"></param> 目标柱子
/// <param name="count"></param> 移动次数
void HanNuoTa(int n, char src, char temp, char dest, int& count)
{
// 递归终止条件1：没有盘子，无需移动，直接返回
if (0 == n)
{
return;//递归结束
}
// 递归终止条件2：只有1个盘子
// 规则：只能相邻移动，从 src 到 dest 必须经过 temp，共2步
if (1 == n)
{
count += 2;// 累计2步
return;//递归结束
}

//***从下面的递归函数的相邻参数也可以发现，盘子都是相邻的，印证我上面荧光笔高亮***

// 第一步：把 n-1 个盘子 从 源柱子 src 移动到 目标柱子 dest（借助 temp 中转）
HanNuoTa(n – 1, src, temp, dest, count);
// 移动第 n 个盘子：从 src 移动到 temp（相邻移动，步数 +1）
count++;
// 第二步：把 n-1 个盘子 从 dest 移动回 src（借助 temp 中转）
HanNuoTa(n – 1, dest, temp, src, count);
// 移动第 n 个盘子：从 temp 移动到 dest（相邻移动，步数+1）
count++;
// 第三步：把 n-1 个盘子 从 src 再次移动到 dest（借助 temp 中转）
HanNuoTa(n – 1, src, temp, dest, count);
}
int main()
{
int n = 0;//盘子个数
while (cin >> n)
{
int count = 0;//移动次数
HanNuoTa(n, 'a', 'b', 'c', count);
cout << count << endl;
}
return 0;
}

小编今天的分享就到这里，如果文中小编有写的不正确的地方，还请大家帮忙指出哦！