[已解决]C++汉诺塔问题递归算法

122Ml

1. #include <stdio.h>
   
2. int t = 0;
   
3. int hanoi(int n, char A, char B, char C) {
   
4.        
   
5.         if (n == 1) {
   
6.                 printf("Move sheet %d from %c to %c\n", n, A, C);
   
7.                 t++;
   
8.                 return(t);
   
9.         }
   
10.         else {
    
11.                 t++;
    
12.                 hanoi(n - 1, A, C, B);
    
13.                 printf("Move sheet %d from %c to %c\n", n, A, C);
    
14.                 hanoi(n - 1, B, A, C);
    
15.                 return(t);
    
16.         }
    
17. }
    
18. 
    
19. int main() {
    
20.         int n;
    
21.         int total;
    
22.         printf("请输入盘数：");
    
23.         scanf_s("%d", &n);
    
24.         total=(hanoi(n, 'A', 'B', 'C'));
    
25.         printf("total:%d",total);
    
26.         return 0;
    
27.         //等效于2^n-1
    
28. }

复制代码

我不太能理解此程序的递归过程，以及

1. else {
   
2.         t++;
   
3.         hanoi(n - 1, A, C, B);
   
4.         printf("Move sheet %d from %c to %c\n", n, A, C);
   
5.         hanoi(n - 1, B, A, C);
   
6.         return(t);
   
7. }

复制代码

中写两边hanoi()函数的作用
麻烦大佬解答！

最佳答案

月排行榜 / 总排行榜

isdkz

2023-9-20 21:44:53

这是一个经典的汉诺塔问题，递归算法是其最优解法之一。

首先，让我们来理解一下汉诺塔问题的规则：有三根柱子，A、B、C，初始时在A柱上有n个盘子，盘子大小不等，大的在下面，小的在上面，现在需要将所有盘子从A柱移动到C柱，移动过程中可以借助B柱，但是在移动过程中，任何时刻都不能出现一个大的盘子放在小的盘子上面的情况。

接下来，我们来看一下这段代码的递归过程：

1. else {
   
2.     t++;
   
3.     hanoi(n - 1, A, C, B); // 将A柱上n-1个盘子通过借助C柱移动到B柱上
   
4.     printf("Move sheet %d from %c to %c\n", n, A, C); // 将A柱上第n个盘子移动到C柱上
   
5.     hanoi(n - 1, B, A, C); // 将B柱上n-1个盘子通过借助A柱移动到C柱上
   
6.     return(t);
   
7. }
   

复制代码

首先，当n=1时，只需要将A柱上的第一个盘子移动到C柱上即可，此时递归结束，返回t=1。

当n>1时，我们需要将A柱上的n个盘子通过借助C柱移动到C柱上。具体的做法是：

1. 将A柱上的n-1个盘子通过借助C柱移动到B柱上；
2. 将A柱上的第n个盘子移动到C柱上；
3. 将B柱上的n-1个盘子通过借助A柱移动到C柱上。

这个过程是一个递归的过程，每次递归都是将A柱上的n-1个盘子通过借助C柱移动到B柱上，然后将A柱上的第n个盘子移动到C柱上，最后将B柱上的n-1个盘子通过借助A柱移动到C柱上。

在递归过程中，t++表示移动次数加一，最后返回移动次数t。

总的移动次数为2^n-1，可以通过数学归纳法证明。

跳转到最佳答案楼层

isdkz

这是一个经典的汉诺塔问题，递归算法是其最优解法之一。

首先，让我们来理解一下汉诺塔问题的规则：有三根柱子，A、B、C，初始时在A柱上有n个盘子，盘子大小不等，大的在下面，小的在上面，现在需要将所有盘子从A柱移动到C柱，移动过程中可以借助B柱，但是在移动过程中，任何时刻都不能出现一个大的盘子放在小的盘子上面的情况。

接下来，我们来看一下这段代码的递归过程：

1. else {
   
2.     t++;
   
3.     hanoi(n - 1, A, C, B); // 将A柱上n-1个盘子通过借助C柱移动到B柱上
   
4.     printf("Move sheet %d from %c to %c\n", n, A, C); // 将A柱上第n个盘子移动到C柱上
   
5.     hanoi(n - 1, B, A, C); // 将B柱上n-1个盘子通过借助A柱移动到C柱上
   
6.     return(t);
   
7. }
   

复制代码

首先，当n=1时，只需要将A柱上的第一个盘子移动到C柱上即可，此时递归结束，返回t=1。

当n>1时，我们需要将A柱上的n个盘子通过借助C柱移动到C柱上。具体的做法是：

1. 将A柱上的n-1个盘子通过借助C柱移动到B柱上；
2. 将A柱上的第n个盘子移动到C柱上；
3. 将B柱上的n-1个盘子通过借助A柱移动到C柱上。

这个过程是一个递归的过程，每次递归都是将A柱上的n-1个盘子通过借助C柱移动到B柱上，然后将A柱上的第n个盘子移动到C柱上，最后将B柱上的n-1个盘子通过借助A柱移动到C柱上。

在递归过程中，t++表示移动次数加一，最后返回移动次数t。

总的移动次数为2^n-1，可以通过数学归纳法证明。