[数论] 求斐波那契的第N项
可能学过编程语言的同学们都一定接触过斐波那契数列。 求斐波那契数列的方法也有很多,有效率高低及空间开销高低之分;
本篇博客将对斐波那契数列进行一个分析,分析每一种算法的效率及空间开销;
递归实现(此处不考虑爆int,单纯的将其实现,下同)
#include <iostream>
using namespace std;
int fib(int n)
{
if(n == 1 || n == 2)//代表前两项
return 1;
else//其他情况返回fib(n-1) + fib(n-2)
return fib(n-1) + fib(n-2);
}
int main()
{
int n;//代表所求的第n个斐波那契数是多少;
cin >> n;
cout<<fib(n);
return 0;
}
分析:此算法是初学者都会接触到的 我们可以自己尝试发现,这种方法计算较小的fib(n)还是可以很快的算出结果 但是一旦数据略大 就会变得很慢(有兴趣的同学试试 计算fib(45)) 原因就是递归调用会造成大量的重复计算 导致效率极低. 基于此 我们可以优化 将每次的计算结果存储在数组中,这样就可以加快运算。
用数组存储加快运算(同样不考虑爆int)
#include <iostream>
using namespace std;
int a[100] = {0};//用来存储 放置重复运算 默认都为0 当计算之后 其值就为非0
int fib(int n)
{
if(a[n])//如果该项计算过 则直接返回 没计算过 其值为0 即false
return a[n];
else
{
return a[n] = fib(n-1) + fib(n-2);//将计算结果存储;
}
}
int main()
{
a[1] = a[2] = 1;//初始化前两项
int n;
while(cin >> n)
{
cout<<fib(n)<<endl;
}
return 0;
}
分析:实测后我们可以发现 我们可以马上计算出第n项斐波那契数列 但是有了一定的空间开销,我们能否把这部分开销给节省了呢? 细想后是可以的。 fib数列就是 不断迭代求新值的一个过程 所以我们可以用3个变量进行迭代 求出fib数列的第n项;
循环迭代实现求fib的第n项
#include <iostream>
using namespace std;
int fib(int n)
{
if(n <= 2)//如果是前两项 则直接返回1
return 1;
int fib_1 = 1, fib_2 = 1, fib_3 = 1;//定义用来循环迭代的变量
while(n > 2)
{
fib_3 = fib_1 + fib_2;
fib_1 = fib_2;
fib_2 = fib_3;
n--;
}
return fib_3;
}
int main()
{
int n;
while(cin >> n)
{
cout<<fib(n)<<endl;
}
return 0;
}
分析:要求fib(1),fib(2)则直接返回1 求其他项 则用迭代求 如 求fib(4).
第一次迭代 求出fib(3)
fib_3 = fib_1 + fib_2 = 1 + 1 = 2;
此时 fib_1 = fib_2 = 1, fib_2 = fib_3 = 2, fib_3 = 2;
循环继续 求出fib(4)
fib_3 = fib_1 + fib_2 = 1 + 2 = 3;
此时 fib_1 = fib_2 = 2, fib_2 = fib_3 = 3, fib_3 = 3;
至此 已经求出了fib(4) 所以 求 >2 的第n项斐波那契数 需要循环n-2次
以上讨论的都是求fib数列较小的情况,那么在算法竞赛中,经常考察的是数值较大的fib数列的值为多少(结果膜常数后储存),在这种情况下 ,我们不得不学习一些快速高效的算法来求解这种问题
例如:51nod 1242 点击打开链接
这里我们将给出两个高效的算法解决此题;
1.矩阵快速幂
这是公式 推导过程如下
基于此公式 不难写出代码
详解矩阵快速幂:点击打开链接
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000009
#define LL long long
struct Node{
LL c[2][2];
}ans;
Node mul(Node a, Node b)
{
Node tmp;
tmp.c[0][0] = 0;
tmp.c[0][1] = 0;
tmp.c[1][0] = 0;
tmp.c[1][1] = 0;
for(int i = 0; i<2; i++)
{
for(int j = 0; j<2; j++)
{
for(int k = 0; k<2; k++)
tmp.c[i][j] = (tmp.c[i][j]%mod + (a.c[i][k] * b.c[k][j])%mod) % mod;
}
}
return tmp;
}
Node pow_mod(LL n)
{
Node tmp;
tmp.c[0][0] = 1;
tmp.c[0][1] = 0;
tmp.c[1][0] = 0;
tmp.c[1][1] = 1;
while(n)
{
if(n&1)
tmp = mul(tmp,ans);
ans = mul(ans,ans);
n >>= 1;
}
return tmp;
}
int main()
{
LL n;
while(cin >> n)
{
ans.c[0][0] = 1;
ans.c[0][1] = 1;
ans.c[1][0] = 1;
ans.c[1][1] = 0;
ans = pow_mod(n);
cout<<ans.c[1][0]<<endl;
}
return 0;
}
2.规律性的解题方法 代码极简,效率极高
原博客链接:点击打开链接
#include <map>
#include <iostream>
using namespace std;
#define long long long
const long M = 1000000007; // modulo
map<long, long> F;
long f(long n) {
if (F.count(n)) return F[n];
long k=n/2;
if (n%2==0) { // n=2*k
return F[n] = (f(k)*f(k) + f(k-1)*f(k-1)) % M;
} else { // n=2*k+1
return F[n] = (f(k)*f(k+1) + f(k-1)*f(k)) % M;
}
}
main(){
long n;
F[0]=F[1]=1;
while (cin >> n)
cout << (n==0 ? 0 : f(n-1)) << endl;
}
上一篇: 使用values批量插入多条数据