1202：Pell数列

【题目描述】
Pell数列a1,a2,a3,…的定义是这样的，a1=1,a2=2,…,an=2an−1+an−2(n>2)。

给出一个正整数 k，要求Pell数列的第 k 项模上 32767 是多少。

【输入】
第1行是测试数据的组数 n，后面跟着 n 行输入。每组测试数据占 1 行，包括一个正整数k(1≤k<1000000)。

【输出】
n 行，每行输出对应一个输入。输出应是一个非负整数。

【输入样例】
2
1
8
【输出样例】
1
408

分析

1.直接递归

如果直接递归，会超时的，因为此题求得项1≤k<1000000，不同于1201：菲波那契数列，斐波那契数列这个题项数比较小；
此代码超时，所以我们可以利用数组保存已求过得值进行记忆化递归；

#include <bits/stdc++.h>
using namespace std;
int x;
int f(int i) {
	if(i==1)//递归出口
		return 1;
	if(i==2)
		return 2;
	return (2*f(i-1)+f(i-2)) % 32767;
}
int main() {
	int n;
	cin>>n;
	while(n--) {
		cin>>x;
		cout<<f(x)<<endl;
	}
	return 0;
}

2.记忆化递归

用一个数组a，来记录已经求过的项 ，可以减少重复性计算，减少程序运行的时间，AC代码：

#include <bits/stdc++.h>
using namespace std;
int x;
int a[1000010];//用此来记录已经求过的项 
int f(int i) {
	if(a[i]!=0)
		return a[i];//说明这个项前面已经求过 ，不用再次求 
	if(i==1)
		return 1;
	if(i==2)
		return 2;
	return a[i]=(2*f(i-1)+f(i-2)) % 32767;//返回的同时，记录这个所求的项 
}
int main() {
	int n;
	cin>>n;
	while(n--) {
		cin>>x;
		cout<<f(x)<<endl;
	}
	return 0;
}

3.递推

此题递推式为：f[i]=(2*f[i-1]+f[i-2])；我们用f数组，提前计算每一项的值，最后直接输出；我们在求的时候，需要进行对32767求余，因为答案要的是求余后的结果；也可以防止int爆掉；此题同1189：Pell数列、1188：菲波那契数列(2)，同一个题解

#include <bits/stdc++.h>
using namespace std;
int x;
int f[1000010];
int main() {
	int n;
	cin>>n;
	f[1]=1;
	f[2]=2;
	for(int i=3;i<=1000000;i++){
		f[i]=(2*f[i-1]+f[i-2])%32767;
	}
	while(n--) {
		cin>>x;
		cout<<f[x]<<endl;
	}
	return 0;
}