汉诺塔递归问题（C++）

汉诺塔递归问题

汉诺塔是典型的递归问题，这个问题可以这样描述：

完成目标： 将n个盘子从A搬运到C，求需要移动多少次完成？

**约束条件：**搬运的过程中每次只能移动一个盘子，且不能出现大的盘子在小的盘子之上。

详细分析如下：

为了分析将A中的n个盘子搬到C中，我们先分析一下n分别等于1，2，3的简单情况，在进行搬运之前我们有如下约定：

1、move(n,A,B,C)表示将n个盘子从A借助B搬到C中

2、move(1,A,C,B)表示将1个盘子从A搬到B中

当盘子的数目为n的时候，分三步

第一步：将A中前n-1个盘子借助C搬到B中 move(n-1,A,C,B)

第二步：将A中的第n个盘子搬到C中 move(1,A,B,C)

第三步：将B中的n-1个盘子借助A搬到C中 move(n-1,B,A,C)

那么第一步move(n-1,A,C,B)和第三步move(n-1,B,A,C)的实现又可以重复利用同样的思想，直到n-2，n-3，，，3，2，1就可以直接一步到位如move(1,A,B,C).

代码实现：

#include <bits/stdc++.h>
using namespace std;
 
void move(int n,char A,char B,char C)
{
    if(n==1)
    {
        cout<<"move 1# from "<<A<<" to "<<C<<endl;
    }
    else
    {
        move(n-1,A,C,B);
        cout<<"move "<<n<<"# from "<<A<<" to "<<B<<endl;
        move(n-1,B,A,C);
    }
    
}
int main()
{
    int n;
    cout<<"请输入盘子的数n:"<<endl;
    cin>>n;
    move(n,'A','B','C');
    return 0;
}