gpt4 book ai didi

c - 如何让下面的递归更快?

转载 作者:行者123 更新时间:2023-11-30 20:38:03 25 4
gpt4 key购买 nike

long long int num(int n,int m)
{
long long int k,i;

k=0;

if(n>1)
{
for(i=0;i<=m;i++)
{
k+=((p[i]%MOD)*(num(n-1,i)%MOD))%MOD;
k%=MOD;
}

return k;
}
else
return q[m];
}

上面的代码是用 C 编写的,我需要让它运行得更快,数组 p[i],q[i] 是全局值,MOD 也是如此,有什么方法可以让它更快,可能是通过存储值或其他东西。我认为DP可以在这里使用,但我不确定该方法。

因为我被要求发布 p[i] 和 q[i] 以及 MOD ,所以它们总是 MOD =1000000000 。

void seive(int c)
{
long long int i,temp;

p[0]=1;
q[0]=p[0];
for(i=c+1;i<=(2*c+2);i++)
{
temp=((p[i-c-1]%MOD)*(c%MOD))%MOD;
temp/=(i-c);

p[i-c]=((p[i-c-1]%MOD)+(temp%MOD))%MOD;
q[i-c]=((q[i-c-1]%MOD)+(p[i-c]%MOD))%MOD;

}
}

c=m-1(第一个代码中的m和第二个代码中的c相关)

最佳答案

声明全局二维数组。

由于 MOD 没有改变,最初计算 p[i]=p[i]%MOD

% 运营成本较高

  long long temp[][];   // size can be max value of n and m  and initialize to LLONG_MIN

long long int num(int n,int m) {

long long int k,i;

k=0;

if(n>1)
{
for(i=0;i<=m;i++)
{
int h=0;
if(temp[n-1][i]!= LLONG_MIN){
h=temp[n-1][i];
}else{
temp[n-1][i]= num(n-1,i)%MOD;
h=temp[n-1][i];
}
k+=((p[i])*(h))%MOD;
k%=MOD;
}

return k;
}

else
return q[m];

}

关于c - 如何让下面的递归更快?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30681439/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com