【算法集训】基础算法：递推 | 概念篇

前言

递���最通俗的理解就是数列，递推和数列的关系就好比 算法 和 数据结构 的关系，数列有点像数据结构中的顺序表，而递推就是一个循环或者迭代的枚举过程。

递推本质上是数学问题，所以有同学问算法是不是需要数学非常好，也并不是，你会发现，这些数学只不过是初中高中我们学烂的东西，高考都经历了，这些东西又何足为惧！?

一、斐波那契数列

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

F(0) = 0，F(1) = 1

F(n) = F(n - 1) + F(n - 2)，其中 n > 1，给定 n(0 ≤ n ≤ 30) ，请计算 F(n) 。

拿到这个题目，我们首先来看题目范围， 最多不超过 30，那是因为斐波那契数的增长速度很快，是指数级别的。所以如果 n 很大，就会超过 c语言 中32位整型的范围。这是一个最基础的递推题，递推公式都已经告诉你了，我们要做的就是利用一个循环来实现这个递推。

我们只需要用一个 F[31] 数组，初始化好 F[0] 和 F[1]，然后按照给定的公式循环计算就可以了。像这样：

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

olli(1) 首先定义一个循环变量；/lili(2) 再定义一个数组记录斐波那契数列的第 n 项，并且初始化第 0 项 和 第 1 项。/lili(3) 然后一个 for 循环，从第 2 项开始；/lili(4) 利用递推公式逐步计算每一项的值；/lili(5) 最后返回第 n 项即可。/li/ol h3二、泰波那契数列/h3 p泰波那契序列 Tn 定义如下：/ppT(0) = 0, T(1) = 1, T(2) = 1/pp且在 n > 2 的条件下 T(n) = T(n-1) + T(n-2) + T(n-3)，给你整数 n，请返回第 n 个泰波那契数 T(n) 的值。

如果已经理解斐波那契数列，那么这个问题也不难，只不过初始化的时候，需要初始化前三个数，并且在循环迭代计算的时候，当前数的值需要前三个数的值累加和。像这样：

int tribonacci(int n){int T[100];T[0] = 0;T[1] = 1;T[2] = 1;for(int i = 3; i T[i] = T[i-1] + T[i-2] + T[i-3];}return T[n];}