时间；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;
}