递归50求调 5TLE

qiufangguo @ 2024-12-07 14:43:46

#include<bits/stdc++.h>
using namespace std;
int n;
int step(int a){
    if(a==1)return 1;
    else if(a==2)return 2;
    else{
        return step(a-1)+step(a-2);
    }
}
int main() {
    cin>>n;
    cout<<step(n);
    return 0;
}

by qiufangguo @ 2024-12-07 14:46:58

加了高精变40了。，

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
struct Bigint {
    int len, a[1500];
    Bigint(int x = 0) { // 初始化数值为x
        memset(a, 0, sizeof(a));
        for (len = 0; x; len++)
            a[len] = x % 10, x /= 10;
    }
    int &operator[](int i) { return a[i]; }
    void print() {
        for (int i = max(len-1, 0); i >= 0; i--)
            printf("%d", a[i]);  // 若数值为0，也需要输出0       
    }
};

Bigint operator+(Bigint &a, Bigint &b)//原理与高精加法一样
{
    Bigint c;
    c.len=max(b.len, a.len);
    for (int i = 0; i < c.len; i++) {
        c[i] += a[i] + b[i];
        c[i + 1] = c[i] / 10;
        c[i] %= 10;
    }
    if (c[c.len])
        c.len++;
    return c;
};
int n;
Bigint step(int a){
    if(a==1)return Bigint(1);
    else if(a==2)return Bigint(2);
    else{
        Bigint aa = step(a-1),bb = step(a-2);
        return aa+bb;
    }
}
int main() {
    cin>>n;
    Bigint res=step(n);
    res.print();
    return 0;
}

by linyutong123123 @ 2024-12-14 10:25:50

数据量太大，n ≤ 5000 递归的时间复杂度是O(2^n), 所以用递归会超时。可以用递推的方法求解

#include <bits/stdc++.h>
using namespace std;
class bigint {
public:
    string num;
    bigint(string x) {
        this -> num = x;
    }
    bigint() {
        this -> num = "0";
    }
    bigint operator+ (bigint& x) {
        int m = num.size();
        int n = x.num.size();
        int *a = new int[m];
        int *b = new int[n];
        for (int i = 0; i < m; i++) {
            a[i] = num[m - i - 1] - '0';
        }
        for (int i = 0; i < n; i++) {
            b[i] = x.num[n - 1 - i] - '0';
        }
        int carry = 0;
        int len = max(m, n);
        string ans = "";
        for (int i = 0; i < len; i++) {
            int a1 = i < m ? a[i] : 0;
            int b1 = i < n ? b[i] : 0;
            int k = a1 + b1 + carry;
            carry = k / 10;
            k %= 10;
            ans += to_string(k);
        }
        if (carry) {
            ans += '1';
        }
        reverse(ans.begin(), ans.end());
        delete[] a;
        delete[] b;
        return bigint(ans);
    }
};
int main() {
    int n;
    cin >> n;
    vector<bigint> dp(n + 1, bigint("1"));
    dp[1] = bigint("1");
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    cout << dp[n].num << endl;
    return 0;
}