······

equipy_rrt @ 2023-12-13 16:59:59

#include<bits/stdc++.h>
#define maxn 2000
using namespace std;

string f[maxn];
string add(string a,string b){
    int a1[maxn],b1[maxn],c1[maxn],len=max(a.size(),b.size());
    string ans;
    for(int i=a.size()-1,j=1;i>=0;i--,j++) a1[j]=a[i]-'0';
    for(int i=b.size()-1,j=1;i>=0;i--,j++) b1[j]=a[i]-'0';
    for(int i=1;i<=len;i++){
        c1[i]+=a1[i]+b1[i];
        c1[i+1]=c1[i]/10;
        c1[i]%=10;
    }
    if(c1[len+1]) len++;
    for(int i=len-1,j=1;i>=1;i--,j++)
        ans[j]=c1[i]+'0';
    return ans;
}

string fib(int n){
    if(f[n]!="-1") 
        return f[n];
    else f[n]=add(fib(n-2),fib(n-1));
    return f[n];
}

int main(){
    int k;
    for(int i=3;i<maxn;i++)
        f[i]="-1";
    f[1]="1",f[2]="2";  
    cin>>k;
    cout<<fib(k)<<endl;
    return 0;
}

by Brilliant11001 @ 2023-12-23 15:15:09

@rrt123456

看一下我给你改的

by Brilliant11001 @ 2023-12-23 15:15:34

#include<bits/stdc++.h>
#define maxn 5010
using namespace std;
int a1[maxn],b1[maxn],c1[maxn];
string f[maxn];
string add(string a,string b){
    memset(c1, 0, sizeof c1);
    int len=max(a.length(),b.length()), la = a.length(), lb = b.length();
    string ans = "";
    for(int i=la-1,j=1;i>=0;i--,j++) a1[j]=a[i]-'0';
    for(int i=lb-1,j=1;i>=0;i--,j++) b1[j]=b[i]-'0';
    for(int i=1;i<=len;i++){
        c1[i]+=a1[i]+b1[i];
        c1[i+1]+=c1[i]/10;
        c1[i]%=10;
    }
    if(c1[len+1]) len++;
    for(int i=len;i>=1;i--)
        ans+=(char)c1[i]+'0';
    return ans;
}

string fib(int n){
    if(n <= 3) return to_string(n);
    if(f[n] != "-1") return f[n];
    f[n] = add(fib(n-2),fib(n-1));
    return f[n];
}

int main(){
    int k;
    cin>>k;
    for(int i = 4; i < maxn; i++) f[i] = "-1";
    cout<<fib(k)<<endl;
    return 0;
}

by Brilliant11001 @ 2023-12-23 15:21:19

problems：

1.数组没开够，要5000；

2.大数组不能定义在函数中，会导致段错误；

3.第十行想存字符串b的每一位结果错写成了字符串a；

4.用字符串ans存计算结果时应该在字符串末尾累加而不是用下标赋值。

by equipy_rrt @ 2023-12-23 15:36:41

@Brilliant11001 谢谢