c/c++ 递归实现汉诺塔问题（代码内部运行详细解释）。

Wings_of_freedom2020-04-23 18:08:14114 收藏

文章标签：算法c++数据结构

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

本文链接：https://blog.csdn.net/xzy15703841578/article/details/105712794

版权

首先有下图可以看出汉诺塔的移动过程：

算法进行步骤：

如果是一个盘子直接将a柱子上的盘子从a移动到c。
否则先将a柱子上的n-1个盘子借助c移动到b肯定没有c柱子是不能移动的，
已知函数形参是hanoi(int n,char a,char b,char c)。
代表将a柱子上的盘子借助c柱子移动到b柱子，这里调用函数的时候是将a柱子上的n-1个盘子借助c柱子，移动到b柱子。
所以这里需要将位置调换一下hanoi(n-1,a,c,b)。
但是还没有移动结束，首先要将a柱子上的最后一个盘子（第n个）盘子直接移动到c。
最后将b柱子上的n-1个盘子借助a移动到c。

先看代码和解析：

#include<bits/stdc++.h>
using namespace std;
void hanoi(int n,char a,char b,char c) { //这里代表将a柱子上的盘子借助b柱子移动到c柱子
if(n==1) cout<<a<<"---->"<<c<<endl;//如果是一个盘子直接将a柱子上的盘子移动到c
else {
hanoi(n-1,a,c,b);//将a柱子上n-1个盘子借助c柱子，移动到b柱子
cout<<a<<"---->"<<c<<endl; //再直接将a柱子上的最后一个盘子移动到c
hanoi(n-1,b,a,c);//然后将b柱子上的n-1个盘子借助a移动到c
}
}
int main() {
int n;
cin>>n;
hanoi(n,'A','B','C');
return 0;
}

代码的内部运算：

 
提醒一下:编号在前的要先运行。