手记

天花板编程手把手计划-第1期-第4天

由于迷宫的问题难度太大,有些人没有及时完成,所以这一篇晚发出一天。通过迷宫的问题,暴露出大家对递归掌握的不是很好,今天我们就专门来说说递归。

1. 递归

递归其实是通过一个函数不断调用自身来实现一组简单重复的功能。递归有一道非常经典的题目是打印斐波那契数列。我们先看看这道题。

1.1 斐波那契数列

一个数列中,每个数字都是前两个数字之和,这样的数列就是斐波那契数列。数列的前两个数字为1。

斐波那契数列有一个基础的解法,大概大家都能想到,代码如下:

#define PRINT_CNT 10void main(){    int i;    int arr[PRINT_CNT];    for (i = 0; i < PRINT_CNT; i++)
    {        if (i == 0 || i == 1)
        {
            arr[i] = 1;
        }        else
        {
            arr[i] = arr[i - 1] + arr[i - 2];
        }        printf("%d ", arr[i]);
    }
}

这段代码通过简单循环的方式打印出了数列的前10个数字,如果需要打印更多只需要修改PRINT_CNT这个宏。算法很朴素,这里就不多说了。

1.2 寻找递归子结构

在我们考虑一个问题是否能够通过递归的方法来解决时,首先要分析问题是否有一个反复迭代的子结构。这道题中,从第三个数字起,每个数字都是前面两个数字求和,这个动作是完全相同的简单重复。

于是我们设计代码框架如下:

#define PRINT_CNT 10int Fib(int n){

}void main(){    int i;    for (i = 1; i <= PRINT_CNT; i++)
    {        printf("%d ", Fib(i));
    }
}

我们需要通过函数Fib()来计算出第n个位置的元素。之后我们就通过循环打印出每一位数就OK了。递归子结构就需要通过函数Fib()的不断递归调用来完成。

1.3 设计递归函数


在设计函数Fib()时,我们需要考虑两个问题:

  • 递归跳出条件

由于递归是不断地调用自身,如果没有跳出条件的话就会陷入到无限死循环中。这一点需要最先考虑。

这道题中,由于前两个数是固定的,因此当n为1和2时不需要递归,直接返回1就行。这就是跳出条件。

  • 递归条件

需要考虑每一次递归和前一次的关系。

这道题中,每次递归都要通过自身调用得到前两次递归的结果,之后求和返回。这就是递归条件。

我们来看看源码:

int Fib(int n){    if (n == 1 || n == 2)
    {        return 1;
    }    else
    {        return Fib(n - 1) + Fib(n - 2);
    }
}

是不是很简单。运行一下,看看结果如何。


这道题目用递归解的效率并不高,但作为递归的例题却很容易理解,所以很多教科书把它当做递归的例题。

1.4 递归调用过程


图中只表示了前四次抛硬币的可能性,一个标准的二叉树。从根结点到每一个叶子结点的路径都是我们最终要输出的一行结果。

注意:没有学过二叉树的同学不用紧张,这里只是用了这个名词,并没有涉及到相关的数据结构知识。看懂图就行。

3. 程序实现

今天我们先给出完整的程序:

#include #define MAX_THROW_TIME 5int g_arr[MAX_THROW_TIME];void Throw(int face, int cnt){    int i;

    g_arr[cnt] = face;
    cnt++;    if (cnt >= MAX_THROW_TIME) // 跳出递归
    {        for (i = 0; i < MAX_THROW_TIME; i++)
        {            printf("%d ", g_arr[i]);
        }        printf("\n");
    }    else // 继续递归
    {
        Throw(0, cnt);
        Throw(1, cnt);
    }
}void main(){
    Throw(0, 0);
    Throw(1, 0);
}

全局变量g_arr数组用来保存每一次抛硬币的结果。

重点来看Throw()函数,这个函数的功能是在数组g_arr中标记出抛第cnt次的一种结果。注意,它只是标记一种结果,也就是二叉树中第cnt层的一个节点,至于是哪一个节点就要看是被哪一个节点调用的了。

Throw()函数有两个参数:

  • face

表示硬币的两个面,值为1表示正面,值为0表示反面。

  • cnt

用来记录抛硬币的次数。通过这个变量我们设置了退出条件,当达到我们设置的次数MAX_THROW_TIME时,打印g_arr中的全部内容。这就是一种完整的可能。

来看看执行结果吧:


4. 作业完成情况

大部分同学都用了二进制的方式打印出了全部结果,功能上完全正确。个别人也用了递归的思想,不过他使用了随机数的方式,模拟了真正的抛硬币过程。

随机的方式不是我们这道题所要求的,我们只是要打印出所有的可能性,因此每一次递归都是固定的,一个正面一个反面。我们要做的只是通过不同的递归路径来修改每一次抛硬币的结果,从而得到全部的可能。

5. 课后作业

5.1 作业一

编程实现把1~9九个数字填入九宫格中,满足每行、每列和对角线上的三个数字和为15。如图所示。


注意:由于结果不唯一,只要打印出一种满足条件的结果即可。



作者:天花板
链接:https://www.jianshu.com/p/cc312e23ed69


0人推荐
随时随地看视频
慕课网APP