1189.Pell数列
Pell数列a_1,a_2,a_3,...a_1,a_2,a_3,...的定义是这样的,a_1=1,a_2=2,...,a_n=2a_n−1+a_n−2(n>2)a_1=1,a_2=2,...,a_n=2a_n−1+a_n−2(n>2)。
给出一个正整数k,要求Pell数列的第k项模上32767是多少。
输入
第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数k (1≤k<1000000)。
输出
n行,每行输出对应一个输入。输出应是一个非负整数。
样例
输入数据 1
2
1
8
输出数据 1
1
408
思路:减少运行时间:
1.用<记录数组>存储数据,不在每次输入k时重新循环,而是在一次循环后可以在数组对应位置直接调用对应索引处的数据(动态规划)
2.记录k的最大值max,若新输入的k小于max,则不再重新生成<记录数组>max索引位置及以前的数据,并且不生成max之后的数据
3.在每次得出一个数据后直接取余 与每次运算不取余,算出最终结果后再取余所得余数相同,因为冗余的可以被32767除去的数什么时候除都行
#include <iostream>
using namespace std;
int arr[1000000] = {0,1,2};
int main()
{int n = 0,k = 0,max =-1;cin >> n;for (int i = 1; i <= n; i++){cin >> k;if(max<k){max = k;for (int j = 1; j <= max; j++){if (j >= 3)arr[j] = (2 * arr[j - 1] + arr[j - 2]) % 32767;}}cout << arr[k] << endl;}return 0;
}