@[toc]

零、写在前面

  为了逼迫督促大家学习，《算法零基础100讲》 设置了付费模式，博主每天会开一篇试读文（免费阅读全文），文章中会有一些与本文相关的练习题。也就是今天的题不刷掉，非付费玩家明天就看不了了。此所谓聚焦学习，从 「 我可以学 」 变成 「 我必须学 」。
  当然，也可以选择跳过，只是今天不看，明天就会开放下一篇。这 100 篇更新完，至少可以刷掉 300 题（作者每天会至少开放三个题），如果每天都打卡坚持下来，算法就妥妥的入门了。
  每天早上 8点 开放文章试读，风雨无阻！
  任何事情都是要靠坚持的，但是坚持这件事情本身就不容易，所以，我把它转化成了游戏的形式，任何有规则，有乐趣的行为都可以称之为游戏，如果你看到了这篇文章，想要加入我们的刷题行列，和群友一起打卡学习，那就赶紧那就赶紧 联系博主 吧。

一、概念定义

  在数学上，数列是一个很经典的概念，而在程序中，数列的逻辑形式是数组。经典的数列有：等差数列、等比数列、斐波那契数列 等等。
  在C语言中，数组的表示如下：a[i]代表数组的第 $i$ 个元素，下标从 0 开始记，即a[0], a[1], a[2], a[3], ...分别对应的是数学上的数列： $a_0$、 $a_1$、 $a_2$、 $a_3$ … 。

1、等差数列

  对于等差数列而言，任意相邻两个数的差都是相等的，这个值被称为公差，我们用 $d$ 表示，那么 $a_0$ 作为数列的首项， $a_i$ 的递推公式如下：

$$a_i =\begin{cases} a_0 & i=0\\ a_{i-1} + d & i > 0\end{cases}$$

2、等比数列

  对于等比数列而言，任意后一个数除上前一个数的商都是相等的，这个值被称为公比，我们用 $q$ 表示，那么 $a_0$ 作为数列的首项， $a_i$ 的递推公式如下：

$$a_i =\begin{cases} a_0 & i=0\\ a_{i-1} \times q & i > 0\end{cases}$$

3、斐波那契数列

  对于斐波那契数列而言，除了第 0 项 和 第一项以外，任何一个项等于前两项之和，递推公式如下：

$$f(n) = \begin{cases} 0 & n=0\\ 1 & n=1\\ f(n-1)+f(n-2)& n>1\end{cases}$$

  斐波那契数列，在理解递归时有着至关重要的作用，这个后面的章节我会将，目前只需要理解它的任意一项能够通过前两项计算出来即可。

二、题目描述

  斐波那契数，通常用 $f(n)$ 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

$$f(n) = \begin{cases} 0 & n=0\\ 1 & n=1\\ f(n-1)+f(n-2)& n>1\end{cases}$$

给定 $n(0 \le n \le 30)$ ，请计算 $f(n)$。

三、算法详解

  斐波那契数列的前两项是已知的，所以我们可以利用 C语言 中的数组，和对数组的遍历操作，就能把斐波那契数列的第 $2$ 项，第 $3$ 项，…，第 $n$ 项依次求出来。

四、源码剖析

int fib(int n) {
    int f[31];                     // (1)
    f[0] = 0, f[1] = 1;            // (2)
    for(int i = 2; i <= n; ++i) {  // (3)
        f[i] = f[i-1] + f[i-2];    // (4)
    }
    return f[n];                   // (5)
}

• $(1)$ 定义一个数组，主要如果要求 $n \le 30$，数组定义必须大于 30；
• $(2)$ 这里利用逗号表达式初始化前两项；
• $(3)$ 利用一个for循环遍历数组；
• $(4)$ 利用斐波那契数列的递推公式，计算每一项的值；
• $(5)$ 返回第 $n$ 项的结果；

五、推荐专栏

六、习题练习

请参考原文