第一讲递归与递推例题 AcWing 717. 简单斐波那契

悠悠 2023-09-26 21:48 13阅读 0赞

## 第一讲 递归与递推 例题 AcWing 717. 简单斐波那契 ##

### 原题链接 ###

[AcWing 717. 简单斐波那契][AcWing 717.]

### 算法标签 ###

循环结构 递推

### 思路 ###

依题意模拟

### 我的代码 ###

#include<bits/stdc++.h>
    #define int long long
    #define rep(i, a, b) for(int i=a;i<b;++i)
    #define Rep(i, a, b) for(int i=a;i>b;--i)
    #define x first
    #define y second
    #define ump unordered_map
    #define pq priority_queue
    #define pb push_back
    using namespace std;
    typedef pair<int, int> PII;
    const int N=50;
    int a[N];
    inline int rd(){
       int s=0,w=1;
       char ch=getchar();
       while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
       while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
       return s*w;
    }
    void put(int x) {
        if(x<0) putchar('-'),x=-x;
        if(x>=10) put(x/10);
        putchar(x%10^48);
    }
    signed main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        int n=rd();
        a[0]=0, a[1]=1;
        rep(i, 2, n){
            a[i]=a[i-1]+a[i-2];
        }
        rep(i, 0, n){
            printf("%lld ", a[i]);
        }
        return 0;
    }

## y总代码 ##

#include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    int main()
    {
        int a = 0, b = 1;
        int n;
        cin >> n;
    
        for (int i = 0; i < n; i ++ )
        {
            cout << a << ' ';
            int c = a + b;
            a = b, b = c;
        }
    
        cout << endl;
    
        return 0;
    }

相比之下，y总省略了开辟数组a的内存空间，同时将处理与输出放置一个循环中进行，减少了时间复杂度与空间复杂度

### 参考文献 ###

[AcWing 717. 简单斐波那契][AcWing 717. 1]

![在这里插入图片描述][9cb4cb80a18345158f8a69e2f196e5b9.png]

[AcWing 717.]: https://www.acwing.com/problem/content/719/
[AcWing 717. 1]: https://www.acwing.com/activity/content/code/content/159557/
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://img-blog.csdnimg.cn/9cb4cb80a18345158f8a69e2f196e5b9.png