欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[数论] 求斐波那契的第N项

程序员文章站 2024-03-19 19:09:04
...

可能学过编程语言的同学们都一定接触过斐波那契数列。 求斐波那契数列的方法也有很多,有效率高低及空间开销高低之分;

本篇博客将对斐波那契数列进行一个分析,分析每一种算法的效率及空间开销;


递归实现(此处不考虑爆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.矩阵快速幂

[数论] 求斐波那契的第N项 这是公式 推导过程如下

[数论] 求斐波那契的第N项

基于此公式 不难写出代码

详解矩阵快速幂:点击打开链接

#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;
}