简单斐波那契(递推实现)

题目 简单斐波那契

image-8ff62e98

思路分析

从子问题入手 不断推出下一个答案

答案存在数组里实际上就等同于递归的记忆化数组

然后数组空间其实可以优化

每轮其实只需要知道前两轮的答案 所以可以用ab两个变量代替数组

这实际是个滚动的过程

a一开始等于f(n-2) b等于f(n-1) f(n)=f(n-2)+f(n-1）=a+b

当n+1时 f(n+1)=f(n-2+1)+f(n-1+1） 实际还是f(n)=f(n-2)+f(n-1）

此时a要变成b的f(n-1) b要变成上一轮的答案f(n)

即

image-d23416aa

ab不断滚动向前 从而使得空间从一维优化到0维的两个变量

这就是滚动数组的雏形

代码实现

#include<bits/stdc++.h>

using namespace std;

int n;

int main()

{

    cin>>n;

    int f[46];

    f[1]=0,f[2]=1;

    for(int i=3;i<=n;i++)

        f[i]=f[i-1]+f[i-2];

    for(int i=1;i<=n;i++)

        cout<<f[i]<<" ";

    return 0;

}

#include<bits/stdc++.h>

using namespace std;

int n;

int main()

{

    cin>>n;

    int a,b,fn;

    a=0,b=1;

    for(int i=1;i<=n;i++){

        cout<<a<<" ";

        fn=a+b;

        a=b,b=fn;

    }

    return 0;

}

同类题型

视频讲解

⬅️ 斐波那契字符串 🏠 00-刷题理模型 ➡️ 翻硬币