c++汉诺塔问题

z13jy25

问题背景：
汉诺塔有三个柱子A、B、C，柱子A上有n个从小到大的盘子，我们需要将这些盘子移动到柱子C上，且每次只能移动一个盘子，并且大盘子不能放在小盘子上面。

解题思路：
递归思想：我们可以将问题分解为更小的子问题。假设我们有n个盘子，我们可以先将上面的n-1个盘子从A移动到B，然后将最下面的一个盘子从A移动到C，最后将n-1个盘子从B移动到C。
递归函数：我们定义一个递归函数hanoi(n, A, C, B)，其中n是盘子的数量，A是源柱，C是目标柱，B是辅助柱。

代码分析：

1. #include <iostream>
   
2. using namespace std;
   
3. int n, k=1;//n:圆盘个数   k:移动次数
   
4. void hanoi(int n, char A, char C, char B){//n:圆盘个数  A:源柱  B:过渡柱 C:目标柱
   
5.         if(n==1 ){ //当A柱上只剩一个圆盘的时候，直接移动到C柱
   
6.                 cout << k << ":" << A << "-"<< C << endl;//移动过程
   
7.                 k++;//移动次数累计
   
8.                 return ;
   
9.         }
   
10.         hanoi( n-1, A, B, C);//填空1，当A柱上还有超过一个圆盘的时候，先把上面的n-1个圆盘移动到中间B柱上面
    
11.         cout << k << ":" << A << "-"<< C << endl;//当把n-1个圆盘移走之后，再把最后一个圆盘从A柱移动到C柱
    
12.         k++;//移动次数累计
    
13.         hanoi(n-1, B, C, A); //填空2，当前B柱上有n-1个圆盘，需要再把这n-1个圆盘移动到C柱上，此时A变为过渡柱
    
14. }
    
15. int main(){
    
16.         cin >> n;//输入圆盘个数
    
17.         hanoi(n,'A','C','B');//调用汉诺塔函数，初始状态为：A柱上有n个圆盘，B为中间过渡柱，C为目标柱
    
18.         return 0;
    

复制代码

解题顺序：
输入盘子数量n：我们从用户输入中获取盘子的数量n。
调用递归函数：我们调用hanoi(n, 'A', 'C', 'B')，开始移动盘子。
递归终止条件：如果n等于1，直接将盘子从A移动到C，并输出移动过程。
递归步骤：
第一步：将n-1个盘子从A移动到B（递归调用hanoi(n-1, A, B, C)）。
第二步：将第n个盘子从A移动到C，并输出移动过程。
第三步：将n-1个盘子从B移动到C（递归调用hanoi(n-1, B, C, A)）。