turing_IK @ 2024-04-14 19:20:01

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

by wang1h @ 2024-04-14 19:35:22

#include<bits/stdc++.h>
using namespace std;
int len=1,f[5005][5005];
void add(int k){
    for(int i=1;i<=len;i++)
        f[k][i]=f[k-1][i]+f[k-2][i];
    for(int i=1;i<=len;i++)
        if(f[k][i]>=10){
            f[k][i+1]+=f[k][i]/10;
            f[k][i]=f[k][i]%10;
            if(f[k][len+1])len++;
        }
}
int main(){
    int n;
    cin>>n;
    f[1][1]=1; f[2][1]=2;
    for(int i=3;i<=n;i++)
        add(i);
    for(int i=len;i>=1;i--)
    cout<<f[n][i];
    return 0;
}

by wang1h @ 2024-04-14 19:35:43

@tlsonghangtong

by xd244 @ 2024-04-14 19:42:30

@tlsonghangtong

#include<bits/stdc++.h>
using namespace std;
#define maxn 2000
struct Bigint{
    int len,a[maxn];
    Bigint(int x=0){
        memset(a,0,sizeof(a));
        for(len=1;x;len++)a[len]=x%10,x/=10;
        len--;
    }int &operator[](int c){
        return a[c];
    }void flatten(int L){
        len=L;
        for(int c=1;c<=len;c++){
            a[c+1]+=a[c]/10;a[c]%=10;
        }for(;!a[len];)len--;
    }void print(){
        for(int c=max(len,1);c>=1;c--)cout<<a[c];
    }
};Bigint operator+(Bigint a,Bigint b){
    Bigint ans;
    int len=max(a.len,b.len);
    for(int c=1;c<=len;c++)ans[c]+=a[c]+b[c];
    ans.flatten(len+1);
    return ans;
}int main(){
    int n;cin>>n;
    Bigint f[5010];
    f[1]=Bigint(1);
    f[2]=Bigint(2);
    for(int c=3;c<=n;c++)f[c]=f[c-1]+f[c-2];
    f[n].print();
}

封装高精结构体

by turing_IK @ 2024-04-17 16:35:26

@xd244 @wang1h 已关，但能不能在我的代码上改？

by xd244 @ 2024-04-17 20:30:01

@tlsonghangtong 好的:

#include<bits/stdc++.h>
using namespace std;
#define maxn 2000
struct Bigint{
    int len,a[maxn];
    Bigint(int x=0){
        memset(a,0,sizeof(a));
        for(len=1;x;len++)a[len]=x%10,x/=10;
        len--;
    }int &operator[](int c){
        return a[c];
    }void flatten(int L){
        len=L;
        for(int c=1;c<=len;c++){
            a[c+1]+=a[c]/10;a[c]%=10;
        }for(;!a[len];)len--;
    }void print(){
        for(int c=max(len,1);c>=1;c--)cout<<a[c];
    }
};
Bigint operator+(Bigint a,Bigint b){
    Bigint ans;
    int len=max(a.len,b.len);
    for(int c=1;c<=len;c++)ans[c]+=a[c]+b[c];
    ans.flatten(len+1);
    return ans;
}
Bigint ans[5010];//记录答案
bool ansed[5010];//记录答案是否已经搜索过
Bigint f(int n){
    if(n==1)return Bigint(1);
    if(n==2)return Bigint(2);
    if(n==3)return Bigint(4);
    if(ansed[n]!=0)return ans[n];
    return ans[n]=f(n-1)+f(n-2)+f(n-3);
}int main(){
    int n;cin>>n;
    f(n).print();
}

by turing_IK @ 2024-04-21 08:56:52

@xd244 谢谢

by turing_IK @ 2024-04-21 09:04:20

@xd244 高精度20分

by Before_Dream @ 2024-05-01 16:20:39

@tlsonghangtong 其实我认为你用封装结构体不用写那麽多代码 况且我想问一下问什么要加f(n - 3)因为我看这道题是用斐波那契数列的 或许你可以这样写

void add_CHY(int x,int y){
    int max_len = max(edge[x].a_len,edge[y].a_len);
    for(int j = 0;j < max_len;j++){
        edge[i].a[j] += edge[x].a[j] + edge[y].a[j];
        if(edge[i].a[j] > 9){
            edge[i].a[j + 1]++;
            edge[i].a[j] %= 10;
        }
    }
    if(edge[i].a[max_len] != 0){
        max_len++;
    }
    edge[i].a_len = max_len;
    return;
}

不喜勿喷