打表法解决递归时堆栈爆炸

KaQqi

题目：
http://ybt.ssoier.cn:8088/problem_show.php?pid=1189

打表递归

[C++] 纯文本查看 复制代码

#include <stdio.h>

int data[1000000]={0,1,2};


int calculate(int a)
{
	if(data[a]) return data[a];
	return 	data[a] = (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[n]);
	}
	return 0;
}

非打表递归

[C++] 纯文本查看 复制代码

#include <stdio.h>

unsigned long long data[1000000];


unsigned long long calculate(unsigned long long a)
{
	if(a == 1) return 1;
	if(a == 2) return 2;
	if(data[a]) return data[a];
	else 
	{
		unsigned long long result = 2*calculate(a-1) + calculate(a-2);
		data[a] = result;
		return result;
	}
		
		
}

int main()
{
	unsigned long long n;
	scanf("%lld",&n);
	unsigned long long buffer[100];
	for(unsigned long long i = 0;i<n;i++)
	{
	
		scanf("%lld",&buffer[i]);
		
	
	}
	for(unsigned long long i = 0;i<n;i++)
	{
		unsigned long long result = calculate(buffer[i]) % 32767;
		printf("%lld\n",result);
	}return 0;
}