每日算法打卡：简单斐波那契

算法
627 words

原题链接

717. 简单斐波那契

题目难度：中等

题目描述

以下数列 0 1 1 2 3 5 8 13 21 ... 被称为斐波纳契数列。

这个数列从第 3 项开始，每一项都等于前两项之和。

输入一个整数 N，请你输出这个序列的前 N 项。

输入格式

一个整数 N。

输出格式

在一行中输出斐波那契数列的前 N 项，数字之间用空格隔开。

数据范围

0 < N < 46

输入样例：

1
5

输出样例：

1
0 1 1 2 3

题目分析

斐波那契数列一定要先看前两项是如何定义的，这里的前两项是0和1，对于当n大于等于3时，每一项等于前两项的和

这里其实有两种做法，一种是递归，一种是递推

用比较抽象的说法是，递归是把一类大问题分解成若干个类似的子问题，例如要求第n项的数字，只需要求第n-1和第n-2项即可，一直分解到第1项和第2项即可

递推则与之相反，是利用子问题直接计算出原问题的答案，例如同样的的求第n项的数字，我们只需要利用第1项和第2项求和计算出地3项，再利用第2项和第3项计算出第4项，直至计算出第n项

这里的代码非常好写，主要是注重理解递推与递归的含义

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
using namespace std;
const int N = 46; // 数据范围
int main()
{
    int n;
    cin >> n;
    int ans[N]; // 结果数组

    ans[1] = 0, ans[2] = 1; // 前两项的初始化

    for (int i = 3; i <= n; i++) // 递推计算
        ans[i] = ans[i - 1] + ans[i - 2];

    for (int i = 1; i <= n; i++) // 答案输出
        cout << ans[i] << ' ';
    cout << '\n';

    return 0;
}

优化

这里我们发现其实在计算每一项的时候，只用到了前两项的数据，因此我们可以只用前两项的变量用于计算第三项

例如，我们使用a表示第1项，使用b表示第2项，使用c表示第3项

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int a = 0, b = 1; // 前两项的定义
    for (int i = 1; i <= n; i++) // 递推
    {
        cout << a << ' '; // 不能忽略前两项的输出，因此我们从第一项开始输出
        // 对于前一次的数据进行更新
        int c = a + b;
        a = b, b = c;
    }
    return 0;
}
Comments