首页 > 代码库 > 斐波那契数列快速计算
斐波那契数列快速计算
感觉一天时间过得挺快，而自己却没有什么收获。
1.之前恰好看了跟快速幂乘法一样的计算大数乘法模，防止溢出，感觉挺有用的，而且用的挺多的。
2.分析问题的能力还很差，遇到一个问题，无法正确的进行转化，怎么进行考虑，感觉自己这方面还很欠缺，这应该是通过大量做题，然后不断总结得出来的吧！毕竟题做的多了，遇到新题也就那几种套路。感觉也是挺对的，面试题的那些小套路在搞竞赛的人面前根本什么也不是，感觉这句话挺有道理的。
3. 这次做的这道题，最后就是转化为求第n个斐波那契数，而我根本没有推导出这个。然后，之前做过怎么快速求解，一个是根据递推公式，还想是f(n)可以通过f(n/2),f(n/2 + 1), f(n/2 - 1)这几个数导出来，我也懒得记，遇到的时候就拿前几个数推导一下，很简单的。另一个方法，就是转移矩阵，快速幂求解。这个方法算是通用的方法（套路），大多数题，搞出来递推公式，可能转移条件比较多，然后搞成转移矩阵的形式，给出初始值，然后求第n个，就是求矩阵的n次幂，然后就是快速幂乘法。这个方法很重要。
4. 忘了，这次还有一点非常重要，就是leetcode上面house robber 那题，思路倒不是挺难，但是感觉自己写的代码很丑，然后今天遇到类似的转化，就很麻烦。然后看题解，得出一种巧妙的方法。题目要求不能出现连续的1，因为是环形的，要求第一个和最后一个不能同时是1，这就增加的复杂性，你不能简单的一次递推，然后考虑这样，枚举第一个位置是0，然后从第二个位置开始，随意放，可以放还可以不放，最后的答案就是最后一个放和不放的总和，第二种情况是：第一个放，那么第二个不能放，然后从第三个开始，可以随意放，然后就转化成前面的那个问题，而且不用重复计算，最后的答案就是最后一个不能放的个数，最终把这两种情况加起来就是最后的答案。这样代码写出来，看起来也特别整齐。仔细想想，真的很巧妙！
下面贴一下我写的求斐波那契：
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn = 1e6 + 10; 5 const int mod = 1e9 + 7; 6 ll dp[maxn][2]; 7 ll n; 8 map<ll, ll> ma; 9 ll work(ll x) {10 if(x == 0) return 1;11 if(x < 4) return x;12 if(ma.count(x)) return ma[x];13 ll res = 0;14 ll t = x / 2;15 if(x & 1) {16 res = work(t) * (work(t - 1) + work(t + 1)) % mod;17 } else {18 res = work(t) * work(t) % mod + work(t - 1) * work(t - 1) % mod;19 }20 return ma[x] = res;21 }22 void solve() {23 cin >> n;24 ll res = (work(n) + work(n - 2)) % mod;25 cout << res << endl;26 }27 int main() {28 solve();29 /* Enter your code here. Read input from STDIN. Print output to STDOUT */ 30 return 0;31 }
1 #include<bits/stdc++.h> 2 #define pb push_back 3 #define FOR(i, n) for (int i = 0; i < (int)n; ++i) 4 #define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl 5 typedef long long ll; 6 using namespace std; 7 typedef pair<int, int> pii; 8 const int maxn = 1e3 + 10; 9 const int mod = 1e9 + 7;10 struct mat {11 ll a[4];12 void init() {13 a[0] = a[3] = 1;14 a[1] = a[2] = 0;15 }16 mat mul(const mat &x) {17 mat res;18 res.a[0] = (a[0] * x.a[0] % mod + a[1] * x.a[2] % mod) % mod;19 res.a[1] = (a[0] * x.a[1] % mod + a[1] * x.a[3] % mod) % mod;20 res.a[2] = (a[2] * x.a[0] % mod + a[3] * x.a[2] % mod) % mod;21 res.a[3] = (a[2] * x.a[1] % mod + a[3] * x.a[3] % mod) % mod;22 return res;23 }24 };25 mat pow(mat a, ll b) {26 mat res;27 res.init();28 while(b) {29 if(b & 1) res = res.mul(a);30 a = a.mul(a);31 b >>= 1;32 }33 return res;34 }35 ll fb(ll n) {36 if(n == 0) return 1;37 if(n < 4) return n;38 mat t;39 t.a[0] = 0; t.a[1] = 1; t.a[2] = 1; t.a[3] = 1;40 t = pow(t, n);41 return t.a[3];42 }43 ll n;44 void solve() {45 while(cin >> n) {46 47 ll res = (fb(n) + fb(n - 2)) % mod;48 cout << res << endl;49 }50 }51 int main() {52 //freopen("test.in", "r", stdin);53 //freopen("test.out", "w", stdout);54 solve();55 return 0;56 }
斐波那契数列快速计算