真·记忆化（秒杀！）O(1)! T(4)
2024-02-23 22:12:06
发布于：北京
185阅读
0回复
0点赞
题目既然都说了记忆化记忆化，咱就来个记忆化！
#include<bits/stdc++.h>
using namespace std;
long long s[105]={1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,1548008755920};
int main() {
int n;
cin>>n;
cout<<s[n-1];
return 0;
}
我就不信啦，还能WA
备注：数组内容为(long long类型)：1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,1548008755920
1~100位(double类型)：1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1.34627e+06,2.17831e+06,3.52458e+06,5.70289e+06,9.22746e+06,1.49304e+07,2.41578e+07,3.90882e+07,6.3246e+07,1.02334e+08,1.6558e+08,2.67914e+08,4.33494e+08,7.01409e+08,1.1349e+09,1.83631e+09,2.97122e+09,4.80753e+09,7.77874e+09,1.25863e+10,2.0365e+10,3.29513e+10,5.33163e+10,8.62676e+10,1.39584e+11,2.25851e+11,3.65435e+11,5.91287e+11,9.56722e+11,1.54801e+12,2.50473e+12,4.05274e+12,6.55747e+12,1.06102e+13,1.71677e+13,2.77779e+13,4.49456e+13,7.27235e+13,1.17669e+14,1.90392e+14,3.08062e+14,4.98454e+14,8.06516e+14,1.30497e+15,2.11149e+15,3.41645e+15,5.52794e+15,8.94439e+15,1.44723e+16,2.34167e+16,3.78891e+16,6.13058e+16,9.91949e+16,1.60501e+17,2.59695e+17,4.20196e+17,6.79892e+17,1.10009e+18,1.77998e+18,2.88007e+18,4.66005e+18,7.54011e+18,1.22002e+19,1.97403e+19,3.19404e+19,5.16807e+19,8.36211e+19,1.35302e+20,2.18923e+20,3.54225e+20,3.54225e+20
全部评论 8
递归版本：
#include<bits/stdc++.h> using namespace std; long long s[105]={1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,1548008755920}; int n; long long f(int i){ if(i==0){ return s[n-1]; } return f(i-1); } int main() { cin>>n; cout<<f(n); return 0; }2024-08-07 来自 北京
0
有帮助，赞一个