算法笔记：汉诺塔

野性酷女 2024-03-17 12:43 73阅读 0赞

### 题目： ###

[晴问算法Web site created using create-react-app![favicon.ico][]https://sunnywhy.com/sfbj/4/3][Web site created using create-react-app_favicon.ico_https_sunnywhy.com_sfbj_4_3]

> 题目描述  
> 汉诺塔（又称河内塔）问题源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
> 
> 抽象成模型就是说：
> 
> 有三根相邻的柱子，标号分别为A、B、C，A柱子按金字塔状叠放着n个不同大小的圆盘，现在要把所有盘子一个一个移动到柱子C上，并且任何时候同一根柱子上都不能出现大盘子在小盘子上方，请问至少需要多少次移动，并给出具体的移动方案。

### 思路： ###

将A上的盘子依次从最大到最小移动到C

**模拟一：**

如果只有两个盘就可以将A上的盘移到B，再将A上的盘移到C，最后将B上的盘移到C。

![659228afe8d44e2d89fae15b4787d1ae.jpeg][]

**模拟二：**

如果有n个盘，就可以将上方的n-1个盘先移到B，再将A最下面的最大的盘移到C，最后将B上的盘移到C。

整体来看：将A看作起始柱，B看作工具柱，C看作目标柱。

![f7226649153949b59e751d24263462ac.jpeg][]

内容细化：要将A柱除最底的盘之外的盘放到工具柱B的这个过程中，C柱就作为了工具柱。

此时就将一个大问题转换成了几个子问题

先将A移到B，C成工具柱

再将B移到C，A成工具柱

再将A工具柱上的盘移到B，C成工具柱

···

**1.将n-1个盘子从A柱移到B柱（C为工具柱）**

**2.将A柱底下最大的盘子移到C柱**

**3.将B柱的n-1个盘子移到C柱（A为工具柱）**

对于第一小问：至少需要多少次

也同时可以用递归来实现：

定义一个全局变量cnt来记录移动的次数，可直接复制上方代码而不中途输出，最后输出cnt即可

#include<bits/stdc++.h>
    using namespace std;
    char a='A',b='B',c='C';
    int n,cnt;
    void hntcnt(char a,char b,char c,int n)
    {
    	if(n==0)return;
    	hntcnt(a,c,b,n-1);
    	cnt++;
    	hntcnt(b,a,c,n-1);
    }
    void hnt(char a,char b,char c,int n)
    {
    	if(n==0)return;
    	hnt(a,c,b,n-1);
    	cout<<a<<"->"<<c<<endl;
    	cnt++;
    	hnt(b,a,c,n-1);
    }
    int main()
    {
    	cin>>n;
    	hntcnt(a,b,c,n);
    	cout<<cnt<<endl;
    	hnt(a,b,c,n);
    	return 0;
    }

[favicon.ico]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/7c5fd998d02c490c9e15a5a95f50b4de.png
[Web site created using create-react-app_favicon.ico_https_sunnywhy.com_sfbj_4_3]: https://sunnywhy.com/sfbj/4/3
[659228afe8d44e2d89fae15b4787d1ae.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/4d7122f7058d499d926ccc8bcda2751d.png
[f7226649153949b59e751d24263462ac.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/aa4ac0f443bc4897a0b5a73a734583ec.png