斐波那契数列

[[TOC]]

教学目标

• 使用小朋法来分解问题
• 理解递归的分支
• 理解递归是在树上的行走

题目

题目描述

斐波那契数列$(Fibonacci \; sequence)$是一个经典的数学问题，其定义如下：第一个和第二个数字都是$1$，接下来的每个数字都是前两个数字之和。例如，斐波那契数列的前几个数字是$1, 1, 2, 3, 5, 8, 13, 21, \cdots$,请编写一个程序，输出斐波那契数列中的第$n$个数字。

输入

一个整数$n$，表示要输出斐波那契数列的第$n$个数字$(1 \leqslant N \leqslant 100)$。

输出

斐波那契数列的第$n$个数字

示例

输入：

5

输出：

5

小朋友法

想像,有一个小朋友他的问题为:求斐波那契数列的第$n$项是什么,为了偷懒少写字,我们把这个问题设为:$f(n)$,根据数列的性质,这个聪明的小朋友找来另两个小朋友,分别去求$f(n-1),f(n-2)$,只要那两个小朋友的问题,那$f(n)$这个问题就解决了.显然,这两个小朋友还会再次去找其它小朋友,然后这样一直找下去,直到问题变为$f(1),f(2)$,这样问题就可以直接得出答案,因为$f(1),f(2)$太简单了,不需要计算.

加入有一个问题为$f(5)$的小朋友,那么整个问题的分解如下:

上面的图形有形状很像是一个倒过来的树,最上面的点$f(5)$就是树根. 类似这种类型的数据,我们称为树.

代码

#include <iostream>
using namespace std;

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

int main() {
    int n;
    cin >> n;
    int ans = fibonacci(n);
    cout << ans;
    return  0;
}

代码理解

如何理解代码的运行过程呢?

请同学们使用磊方块法,在纸上模拟整个过程.

TODO:动画

一边磊方块,一边栈顶的函数$f(i)$,发现:递归就是在树上的行走

• 递归前进: 就是从树上的父亲到孩子
• 递归回溯: 就是从树上的孩子到父亲

记忆化

上面的代码的运行过程中有很多重复的过程,比如$f(5)$的时候需要求一次$f(3)$,$f(4)$的时候还需要重新求$f(3)$,这显然会浪费,很多的时间.

可以想到$f(3)$一定被计算出来后,后面如果还有需要这个值,那么直接返回$f(3)$的值.就可以了.我们把$f(i)$的值存到数组里,如果已经得到了这个值,不需要重复计算,直接返回,这叫做++记忆化++

#include <iostream>
using namespace std;

const int maxn = 1e5+5;
int f[maxn];
int fibonacci(int n) {
    if( n ==1 || n ==2 )
        return 1;

    //如果f[n]的值不是0,表明已经得到值了
    // 直接返回
    if( f[n] != 0) return f[n];

    // 重新计算,并返回
    f[n] = fibonacci(n-1) + fibonacci(n-2);
    return f[n];
}

int main() {
    int n;
    cin >> n;
    int ans = fibonacci(n);
    cout << ans;
    return  0;
}

新的代码的时间复杂度是$O(n)$,因为每个$f(i)$只需要求一次.

总结

通过这个题目,我们学会了

分解子问题

你有一个问题$A$,我们发现可以通过求解子问题B_1,B_2,\cdots,B_n来解$A$ 也就是说问题A可以拆分成子问题B_1,B_2,\cdots,B_n

且子问题B_i与原问题A是相似的,只是规模变小了,那么显然子问题B_i也可以拆分,直到边界

前进就是分解子问题

回溯就是子问题得到解,回到原问题A时

递归本质就是树上行走

题目

• luogu P1255 数楼梯