首页 › 题库 › C/C++编程考级 › C/C++编程三级 › 简答题
简答题 偏难
#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 &lt;bits/stdc++.h&gt; using namespace std; int a[1000005]; int main() {     int n, x;   a[1] = 1, a[2] = 2;  for(int i = 3; i &lt;= 1000000; ++i)   a[i] = (2*a[i-1] + a[i-2])%32767;  cin &gt;&gt; n;  for(int i = 1; i &lt;= n; ++i)  {   cin &gt;&gt; x;   cout &lt;&lt; a[x] &lt;&lt; endl;  }  return 0; }</pre><pre class="brush:cpp;toolbar:false">//解法2:迭代 #include&lt;bits/stdc++.h&gt; using namespace std; int main() {     int ct, p;     cin &gt;&gt; ct;     for(int i = 1; i &lt;= ct; ++i)     {         cin &gt;&gt; p;         if(p &lt;= 2)             cout &lt;&lt; p &lt;&lt; endl;//第1项是1,第2项是2          else          {             int a = 1, b = 2, t;             for(int j = 3; j &lt;= p; ++j)             {                 t = b;                 b = (2*b + a)%32767;                 a = t;             }             cout &lt;&lt; b &lt;&lt; endl;         }     }     return 0; }</pre><pre class="brush:cpp;toolbar:false">//解法3: #include&lt;iostream&gt; #include&lt;cstdio&gt; #include&lt;cstdlib&gt; #include&lt;cstring&gt; #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&gt;&gt;n;  for(int i=1;i&lt;=n;i++)  {   cin&gt;&gt;a;    cout&lt;&lt;f(a)&lt;&lt;endl;  }  return 0; }</pre>
这道题暂未补解析。