简答题
偏难
#7441
Pell数列 Pell数列a 1 , a 2 , a 3 , ...的定义是这样的,a 1 = 1, a 2 = 2, ... , a n = 2 * a n…
Pell数列
Pell数列a1, a2, a3, ...的定义是这样的,a1 = 1, a2 = 2, ... , an = 2 * an − 1 + an - 2 (n > 2)。 给出一个正整数k,要求Pell数列的第k项模上32767是多少。
时间限制:3000
内存限制:65536
输入
第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数k (1 ≤ k < 1000000)。
输出
n行,每行输出对应一个输入。输出应是一个非负整数。
样例输入
2 1 8
样例输出
1 408
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//解法1:递推
#include <bits/stdc++.h>
using namespace std;
int a[1000005];
int main()
{
int n, x;
a[1] = 1, a[2] = 2;
for(int i = 3; i <= 1000000; ++i)
a[i] = (2*a[i-1] + a[i-2])%32767;
cin >> n;
for(int i = 1; i <= n; ++i)
{
cin >> x;
cout << a[x] << endl;
}
return 0;
}</pre><pre class="brush:cpp;toolbar:false">//解法2:迭代
#include<bits/stdc++.h>
using namespace std;
int main()
{
int ct, p;
cin >> ct;
for(int i = 1; i <= ct; ++i)
{
cin >> p;
if(p <= 2)
cout << p << endl;//第1项是1,第2项是2
else
{
int a = 1, b = 2, t;
for(int j = 3; j <= p; ++j)
{
t = b;
b = (2*b + a)%32767;
a = t;
}
cout << b << endl;
}
}
return 0;
}</pre><pre class="brush:cpp;toolbar:false">//解法3:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define N 1000010
#define k 32767
using namespace std;
int a[N];
int f(int x)
{
if(a[x]!=0) return a[x];
if(x==1) return 1;
if(x==2) return 2;
return a[x]=(2*(f(x-1))%k+(f(x-2))%k)%k;
}
int main()
{
int n,a;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a;
cout<<f(a)<<endl;
}
return 0;
}</pre>
这道题暂未补解析。