首页 > 代码库 > 斐波那契数列高效递归求法

斐波那契数列高效递归求法

时间;2014.05.19

地点:图书馆

-------------------------------------------------------------------

一、简述

  前面给出了一种斐波那契数列解法的矩阵幂方法,这是最高效的方法,时间复杂度为O(log)。正常来说通过递推公式 F(n)=F(n-1)+F(n-2)直接来计算F(n)效率是很差的,因为这里会涉及很多冗余计算,比如求F(5),我们要求【F(4)和F(3)】,【要求F(4)则得求F(3)和F(2),要求F(3)得求F(2)和F(1)】...等等,于是这里有好多数都设计要求重复计算,可以通过一颗二叉树来展开,所以这样的递归虽然使大问题化解为子问题了,但子问题的个数迅速膨胀而且还包含了重复的子问题。

-------------------------------------------------------------------

二、不同一般的递归

  首先关系依旧,即 F(n)=F(n-1)+F(n-2),F(0)=0,F(1)=1,,有序列如下,假如我们要求F(6).

t0 t1t2 t3 t4 t5 t6t7 t8...                                             本序列以0 和1开始,求的是F(6)

0 11 2 3 5 813 21..


t0 t1t2 t3 t4 t5 t6t7....                                                    本序列以1和1开始,上面的F(6)对应现在的F(5)

1 12 3 5 8 1321...

....

....

以此规则继续往下面走,我们甚至可以假设一个滑动窗口,该窗口最初占据起始序列的两个值,然后每递归以此,向后滑动一个距离,当然离要求的目标也就靠近一次,最终即滑动窗口会占据要求的值,而我们知道,每次滑动窗口移动占据的值是很容易求得。如此,通过滑动窗口可以一步步缩减问题规模,在这里表现为F(n)中的n会一步步减小。通过这种递归的方式可以有效减少冗余计算,很明显,中间碰到的每个值都值被计算了一次。

-------------------------------------------------------------------

三、实现

#include<iostream>
int AdditiveSequence(int n, int t0, int t1)
{
	if (n == 0)
		return t0;
	if (n == 1)
		return t1;
	return AdditiveSequence(n - 1, t1, t0 + t1);
}
int Fibonacci(int n)
{
	return AdditiveSequence(n, 0, 1);
}
int main()
{
	int n;
	std::cin >> n;
	std::cout << Fibonacci(n) << std::endl;
	return 0;
}
这个算法的时间复杂度就为O(n)了,是比较可观的。