打表法解决递归时堆栈爆炸
题目：http://ybt.ssoier.cn:8088/problem_show.php?pid=1189
打表递归
#include <stdio.h>
int data={0,1,2};
int calculate(int a)
{
if(data) return data;
return data = (2*calculate(a-1) + calculate(a-2))%32767;
}
int main()
{
int nn,n;
scanf("%d",&nn);
for(int i=2;i<1000000;i=i+10000){
calculate(i);
}
while(nn--){
scanf("%d",&n);
printf("%d\n",data);
}
return 0;
}
非打表递归
#include <stdio.h>
unsigned long long data;
unsigned long long calculate(unsigned long long a)
{
if(a == 1) return 1;
if(a == 2) return 2;
if(data) return data;
else
{
unsigned long long result = 2*calculate(a-1) + calculate(a-2);
data = result;
return result;
}
}
int main()
{
unsigned long long n;
scanf("%lld",&n);
unsigned long long buffer;
for(unsigned long long i = 0;i<n;i++)
{
scanf("%lld",&buffer);
}
for(unsigned long long i = 0;i<n;i++)
{
unsigned long long result = calculate(buffer) % 32767;
printf("%lld\n",result);
}return 0;
}
页:
[1]