【题解】汉诺塔

题目汉诺塔

题意：

题意很简单不再赘述。

思路：

汉诺塔问题:

如果n==1，A->C

如果n>1，分三步：

1.先将前n-1块石板，借助C从A移动到B，终点是B

2.将第n块石板从A移动到C

3.将刚才放到B上的n-1块石板借助A从B移动到C，终点是C

而在完成第三步时，显然又回到1，2两步

那么，问题的关键就在于，为什么形参要这样写，先a c b 后b a c ，依据是什么？

我们先看第一步，我们要借助C将n-1块石板从A移动到B，显然我们的终点是B，那么将起点A放到开始，将B放到尾部。

第二步，直接输出即可。

第三步，借助A从B移动到C，起点是B，终点是C，这样写也没有问题。

那么，依据是什么呢？很遗憾，无法给出递归之间一层层清晰的解释，但在翻看各种解释之后，我觉得有个博主说的很有道理：如何理解汉诺塔的递归？ - Fireman A的回答 - 知乎

1.对递归的理解的要点主要在于放弃! 放弃你对于理解和跟踪递归全程的企图，只理解递归两层之间的交接，以及递归终结的条件。

2.放弃的基础在于信任，信任数学归纳法。

ps:

刚学习完循环开始接触递归时的我：“递归是魔法！”

代码：

#include<map>
#include<queue>
#include<cmath>
#include<string>//使用to_string必须加该头文件
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long 
#define itn int
const int array_size = (int)1e6 + 50;
const int INF = 0x3f3f3f3f;
using namespace std;

void slove(int n,char a,char b,char c)
{
    if (n == 1)cout <<"Move disk "<<1<<" from " << a << " to " << c << endl;
    else
    {
        slove(n - 1, a, c, b);
        cout << "Move disk " << n << " from " << a << " to " << c << endl;
        slove(n - 1, b, a, c);
    }
}
int main()
{
    int n;
    cin >> n;
    slove(n,'A','B','C');
    return 0;
}