---
title: "简单斐波那契(递推实现)"
created: 2025-11-28
tags:
  - 算法
---

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

## 题目 [简单斐波那契](https://www.acwing.com/problem/content/719/)

![[image-8ff62e98.png]]

## 思路分析

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

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

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

每轮其实只需要知道前两轮的答案 所以可以用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.png]]

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

这就是滚动数组的雏形

## 代码实现

```cpp
#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;

}
```

```cpp
#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-刷题理模型]] ➡️ [[翻硬币|翻硬币]]