Fibonacci的4种变式 |
您所在的位置：网站首页 › 斐波那契数列用途 › Fibonacci的4种变式 |
Fibonacci的4种变式
|
目录
基础题：求大项斐波那契：变式一：Fibonacci 前 n 项和变式二：类斐波那契数列1变式三：斐波那契平方和变式四：类斐波那契数列2
基础题：求大项斐波那契：
题目：Fibonacci 分析： 当代计算机计算量1s大约1e7 复杂度数量级最大规模 O ( log N ) O\left( \log N\right) O(logN) 1 0 20 10^{20} 1020很大 O ( N ) O\left( \sqrt {N}\right) O(N ) 1 0 12 10^{12} 1012 1 0 14 10^{14} 1014 O ( N ) O\left( N\right) O(N) 1 0 6 10^{6} 106 1 0 7 10^{7} 107 O ( N log N ) O\left( N\log N\right) O(NlogN) 1 0 5 10^{5} 105 1 0 6 10^{6} 106 O ( N 2 ) O\left( N^{2}\right) O(N2)10002500 O ( N 3 ) O\left( N^{3}\right) O(N3)100500 O ( N 4 ) O\left( N^{4}\right) O(N4)5050 O ( 2 N ) O\left( 2^{N}\right) O(2N)2020 O ( 3 N ) O\left( 3^{N}\right) O(3N)1415 O ( N ! ) O\left( N!\right) O(N!)910常用算法： 时间复杂度算法举例 O ( log N ) O\left( \log N\right) O(logN)快速幂，数位dp O ( N ) O\left( N\right) O(N)KMP，欧拉筛法 O ( N log N ) O\left( N\log N\right) O(NlogN)线段树 O ( N 2 ) O\left( N^{2}\right) O(N2)某些dp O ( N 3 ) O\left( N^{3}\right) O(N3)匈牙利算法 O ( 2 N ) O\left( 2^{N}\right) O(2N)二进制枚举 O ( N ! ) O\left( N!\right) O(N!)爆搜无疑问1e9>1e7而且差距较大，常规 O ( n ) O(n) O(n)算法会爆掉，（斐波那契数列的项数n一旦过大，就要考虑快速幂，普通算法时间空间都开销太大）因此题没给出数据组数范围，可选择不储存数列各项来试水，果然ac，矩阵快速幂求解即可 代码: #include #define fo(i,a,b) for(long long i=a;i>n; t.a[0][0] = t.a[1][1] = 1; t.a[0][1] = t.a[1][0] = 0;//别忘记清零 o.a[0][0] = o.a[1][0] = o.a[0][1] = 1; o.a[1][1] = 0;//别忘记清零 return n; } int main(){ while(init()>=0){ for (LL i=n;i;i>>=1,o=o*o) if (i&1) t = t*o;//快速幂 printf( "%lld\n", t.a[0][1]%M ); } return 0; }需要注意： 取余题目数据一般用：long long要用sizeof(r.a),不要用16，因为是long long 的前提多次用t,o矩阵，自然别忘清零因为我们经常求的是特殊矩阵的n次方，所以一般是结果的F[0][0]为Fn+1，F[1][0]为Fn 变式一：Fibonacci 前 n 项和题目： Fibonacci 前 n 项和 核心公式： S n = f n + 2 − 1 S_{n}=f_{n+2}-1 Sn=fn+2−1 详细推导方法请参考：斐波那契数列的前N项和 解决思路： 求出n+2次幂来，减去1即可 变式二：类斐波那契数列1题目：佳佳的 Fibonacci 思路： 能否像变式一样简单的求出一个 S n S_{n} Sn表达式，仅以 f n f_{n} fn为变量呢？ 核心公式：
T
n
=
n
f
n
+
2
−
f
n
+
3
+
2
T_{n}=nf_{n+2}-f_{n+3}+2
Tn=nfn+2−fn+3+2 推导过程：（受louhc指点） 解决思路： 多求两项就可以了，但是本题还有其他解法，当二维公式比较难推出时，同样也可以构造三维或四维方阵，有兴趣参考大佬代码：四维方阵解法 变式三：斐波那契平方和题目：#6264. friend-斐波那契 题意： |
核心公式：
∑
a
n
2
=
a
n
a
n
+
1
\sum a^{2}_{n}=a_{n}a_{n+1}
∑an2=anan+1 推导： 
代码：【本文地址】
今日新闻 |
推荐新闻 |