[已解决]函数递归问题，汉诺塔模型

余绍铭

#include<stdio.h>
void f(char a,char b)
{
        printf("从%c柱上往%c柱上挪动一个圆盘\n",a,b);
}
void g(int i,char a,char b,char c)          // i为要移动的盘子数
{
        if(i==2)
        {
                f(a,b);
                f(a,c);
                f(b,c);
        }
        else if(i>2)
        {
                g(i-1,a,c,b);    //调用g函数，把a上的i-1个盘子通过b放到c
                f(a，c）
                g(i-1,b,a,c);
        }
}
int main(void)
{
        g(4,'A','B','C');
        return 0;
}
能有个大佬写个流程图吗？我真的没理解到g函数的递归是怎么运算的

最佳答案

月排行榜 / 总排行榜

沉默的人e

2020-2-23 17:07:33

总体上就3步，把上面的片片移动到中介柱子上，把最下面的片片移动到目标柱子上，把中介柱子上的片片移动到目标柱子上
对于一个5个片片的塔，我详细说第一个步骤，第三个步骤和第一个步骤大致相同。在以下的内容中我不说移动到哪里，因为这很复杂，你也没有必要研究。

为达成目的先移动上面的4个片片，（为了达成这个目的，先移动上面的三个片片，（为达成目的，先移动上面的两个片片，（满足i = 2的条件，移动。），对于三个片片的情况，上面两个片片已经移动完毕，移动最下面（第三小）的片片，然后移动处于中介的两个片片），对于四个片片的塔，上面的三个片片已经移动完毕，移动最下面（第四小）的片片，然后移动处于中介的三个片片）
对于一个5个片片的塔，上面的4个片片已经移动完毕，移动最下面的大片片，然后移动处于中介的4个片片。

看好括号，每一层括号是一层递推和回归（递归的拆字释义）
加油，希望你能走到“不过如此”的境界

跳转到最佳答案楼层

沉默的人e

楼主是对这个版本的汉诺塔不熟悉，还是对整个汉诺塔不熟悉？
如果单独对整个汉诺塔不熟习，你先把注释写详细一些
给出了One Possible Version

1. 
   
2. #include<stdio.h>
   
3. void f(char a,char b)
   
4. {
   
5.         printf("从%c柱上往%c柱上挪动一个圆盘\n",a,b);
   
6. }
   
7. void g(int i,char a,char b,char c) /* i 是要移动的片片个数，a为起始柱，b是中介柱，c是目标柱*/
   
8.         if(i==2)//单独处理两个片
   
9.         {
   
10.                 f(a,b);
    
11.                 f(a,c);
    
12.                 f(b,c);
    
13.         }
    
14.         else if(i>2)//不是两个片时，以下为具体操作步骤
    
15.         {
    
16.                 g(i-1,a,c,b);    /*调用g函数，以起始柱为起始，目标柱为中介，中介柱为目标移动起始（起始柱）上的i -1个片片*/
    
17.                 f(a，c);/*单独处理最下面的片片，从起始直接移动到目标*/
    
18.                 g(i-1,b,a,c);/*处理剩下的片片，以中介柱为起始，以起始柱为中介，以目标柱为目标，移动起始（中介柱）上的i-1个片片*/
    
19.         }
    
20. }
    
21. int main(void)
    
22. {
    
23.         g(4,'A','B','C');
    
24.         return 0;
    
25. }

复制代码

把形参的知识弄明白。定义或者声明函数时，形参所在的位置代表的意义，在设计者的心理已经定型，不会改变。所以具体操作步骤里面的内容，那几个形参的顺序调动，是形参的意义改变，而第2个位置永远都代表起始，第3个位置永远代表中介，第4个位置永远代表目标

具体步骤，就像俄罗斯套娃倒过来想，分治的思想
以5个娃为例说明不是两个片时的具体操作步骤1>2>3>4>5(1>2:1号娃个头大于2号娃，以此类推)
1.把1号娃的盖子打开g(i-1,a,c,b)
2.把装有3号娃的2号娃放进1号娃里面。f(a,c)
3.把1号娃的盖子盖上g(i-1,b,a,c)

我说明白了么？

余绍铭

沉默的人e 发表于 2020-2-23 11:52
楼主是对这个版本的汉诺塔不熟悉，还是对整个汉诺塔不熟悉？
如果单独对整个汉诺塔不熟习，你先把注释写详 ...

我不懂的是  g(i-1,a,c,b); 他的执行过程？我想了一天都没想明白。。

沉默的人e

总体上就3步，把上面的片片移动到中介柱子上，把最下面的片片移动到目标柱子上，把中介柱子上的片片移动到目标柱子上
对于一个5个片片的塔，我详细说第一个步骤，第三个步骤和第一个步骤大致相同。在以下的内容中我不说移动到哪里，因为这很复杂，你也没有必要研究。

为达成目的先移动上面的4个片片，（为了达成这个目的，先移动上面的三个片片，（为达成目的，先移动上面的两个片片，（满足i = 2的条件，移动。），对于三个片片的情况，上面两个片片已经移动完毕，移动最下面（第三小）的片片，然后移动处于中介的两个片片），对于四个片片的塔，上面的三个片片已经移动完毕，移动最下面（第四小）的片片，然后移动处于中介的三个片片）
对于一个5个片片的塔，上面的4个片片已经移动完毕，移动最下面的大片片，然后移动处于中介的4个片片。

看好括号，每一层括号是一层递推和回归（递归的拆字释义）
加油，希望你能走到“不过如此”的境界

余绍铭

沉默的人e 发表于 2020-2-23 17:07
总体上就3步，把上面的片片移动到中介柱子上，把最下面的片片移动到目标柱子上，把中介柱子上的片片移动到 ...

谢谢了，我其实是理解这个步骤的，疑惑的是为什么计算机他就能这样执行下去。。。

沉默的人e

余绍铭 发表于 2020-2-23 18:04
谢谢了，我其实是理解这个步骤的，疑惑的是为什么计算机他就能这样执行下去。。。

编程语言支持递归有如下的条件，缺一不可
第一个，这个编程语言有函数这么个东西
第二个，编程语言中函数具有调用其他函数的功能
第三个，两个函数可以完全相同（或两个函数的主体部分可以完全相同，比如函数a的功能是打印哈哈，函数b的功能也是打印哈哈。）
满足这几个条件，这个编程语言就支持递归。
所以计算机完成递归，实际上就是计算机完成”调用函数”