信息学奥赛一本通 1189：Pell数列 | 1202：Pell数列 | OpenJudge NOI 2.3 1788:Pell数列 | 2.3 1788:Pell数列

【题目链接】

ybt 1189：Pell数列
ybt 1202：Pell数列
OpenJudge NOI 2.2 1788:Pell数列
OpenJudge NOI 2.3 1788:Pell数列

【题目考点】

1. 递推

【解题思路】

• 递推状态：Pell数列第i项的值，记为$a_i$
• 初始状态：$a_1=1,a_2=2$
• 递推关系：题目要求对结果取模32767，那么递推关系为:$a_i=(2\ast a_{i-1}+a_{i-2})\%32767$。
  该题有多组询问。可以先求出Pell数列的前$10^6$项，然后针对每次询问取数组中的一项。

【题解代码】

解法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; }

解法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; }

总结

以上是生活随笔为你收集整理的信息学奥赛一本通 1189：Pell数列 | 1202：Pell数列 | OpenJudge NOI 2.3 1788:Pell数列 | 2.3 1788:Pell数列的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。