当前位置:首页 > 高性能开发 > 数据结构与算法

递归-习题8-noi1788Pell数列

优良自学吧提供递归-习题8-noi1788Pell数列,递归--练习8--noi1788Pell数列递归--练习8--noi1788Pell数列 一、心得 5 1、 6 //直接递归Time Limit Exceeded 7 //那就记忆化递

递归--练习8--noi1788Pell数列

递归--练习8--noi1788Pell数列

一、心得

 5 1、 
 6 //直接递归Time Limit Exceeded 
 7 //那就记忆化递归 
 8 2、
 9 直接记忆化递归后还有问题 
10 a[k]=2*f(k-1)%32767+f(k-2)%32767;
11 说明这句话超出范围了,所以修改成了如下 
12 a[k]=(2*(f(k-1)%32767)+f(k-2)%32767)%32767;
13 就AC了 

16 #define Max 1000005
17 using namespace std;
18 int a[Max]; 占的位置是
50816kB

如果代码部分对了说明自己有方面没有想到,想好就对了

二、题目

1788:Pell数列

总时间限制: 
3000ms
 
内存限制: 
65536kB
描述
Pell数列a1, a2, a3, ...的定义是这样的,a1 = 1, a2 = 2, ... , an = 2 * an 1 + an - 2 (n > 2)。
给出一个正整数k,要求Pell数列的第k项模上32767是多少。
输入
第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数k (1 ≤ k < 1000000)。
输出
n行,每行输出对应一个输入。输出应是一个非负整数。
样例输入
2
1
8
样例输出
1
408

三、AC代码

 1 /*
 2 noi1788Pell数列
 3 递推表达式: 
 4 a1 = 1, a2 = 2, ... , an = 2 * an ? 1 + an - 2 (n > 2)。
 5 1、 
 6 //直接递归Time Limit Exceeded 
 7 //那就记忆化递归 
 8 2、
 9 直接记忆化递归后还有问题 
10 a[k]=2*f(k-1)%32767+f(k-2)%32767;
11 说明这句话超出范围了,所以修改成了如下 
12 a[k]=(2*(f(k-1)%32767)+f(k-2)%32767)%32767;
13 就AC了 
14 */
15 #include <iostream>
16 #define Max 1000005
17 using namespace std;
18 int a[Max]; 
19 //直接递归Time Limit Exceeded 
20 //那就记忆化递归 
21 int f(int k){
22     if(a[k]!=0) return a[k];
23     else if(k==1) return 1;
24     else if(2==k) return 2;
25     else return a[k]=(2*(f(k-1)%32767)+f(k-2)%32767)%32767;
26 }
27 int main(){
28     int n;
29     cin>>n;
30     for(int i=1;i<=n;i++){
31         int a;
32         cin>>a;
33         cout<<f(a)<<endl;
34     }
35     return 0;
36 } 

 


(本文来自互联网,不代表搜站(http://www.ylzx8.cn/)的观点和立场)
本站所有内容来自互联网,若本站收录的信息无意侵犯了贵司版权,请给我们来信(ylzx8cn@163.com),我们会及时处理和回复,谢谢