0
Follow
11
View

# Question about #c language # : Logol P1255 is related to recursion and recursion do not know why wrong, find the error and correct the code used test

cwg620 注册会员
2023-02-28 21:37

long long supports a maximum of 19 digits if N=5000

ycwc880924wc 注册会员
2023-02-28 21:37
PS: Q&A VIP annual card [limited time plus: free IT technical books], for details > > > https://vip.csdn.net/askvip?utm_source=1146287632
ddhhhnj 注册会员
2023-02-28 21:37

long long type also can not save, use high precision addition.

``````#include
int f[5050][5050];
int len=1;
//本题结果可能很大，正常处理会溢出，故考虑高精度
void deal(int x)
{
for(int i=1;i<=len;i++)//直接处理和
{
f[x][i]=f[x-1][i]+f[x-2][i];
}
for(int i=1;i<=len;i++)//处理进位
{
if(f[x][i]>=10)//必须满足大于等于10
{
f[x][i+1]+=f[x][i]/10;//向高一位进1
f[x][i]=f[x][i]%10;
if(f[x][len+1]) len++;//处理最高到达的位数
}
}
}

int main()
{
int n;
scanf("%d",&n);
f[1][1]=1;
f[2][1]=2;//f[i][j]代表走到第i个楼梯有的方法数
for(int i=3;i<=n;i++)
{
deal(i);
}
for(int i=len;i>=1;i--)//倒叙输出就是值
{
printf("%d",f[n][i]);
}
return 0;
}
``````

deathyeah 注册会员

Publish Time
2023-02-28 21:37
Update Time
2023-02-28 21:37