Fibonacci类

要实现所谓的Fibonacci查找，首先来实现Fibonacci数列类。
Fibonacci数列最早由数学家Leonardoda Fibonacci提出，它指的是一种满足如下递推关系的数列：

$$F(n)= \begin{cases} n& \text{n≤1}\\ F(n-1)+F(n-2)& \text{n≥2} \end{cases}$$

---

直观印象

根据此定义，可以直接利用二分递归计算第个Fibonacci数

_int64 fib(int n)
{
    return (2>n)?
    (_int64) n : fib(n-1)+fib(n-2);
}

这一实现的正确性显而易见，而且代码简洁自然。不幸的是，它的效率十分低下，时间复杂度高达指数形式。

为确切界定该算法的复杂度，不妨将计算所需的时间记作，可得递推式如下：

$$T(n)= \begin{cases} 1& \text{n≤1}\\ T(n-1)+T(n-2)+1& \text{n≥2} \end{cases}$$

若令 ，则有：

$$S(n)= \begin{cases} 1& \text{n≤1}\\ S(n-1)+S(n-2)& \text{n≥2} \end{cases}$$

我们发现，的递推形式与完全一致，只是起始项不同：

$$S(0) = (T(0)+1)/2 = 1 = F(1)\\ S(1) = (T(1)+1)/2 = 1 = F(2)$$

亦即，整体上相对于F(n)提前了一个单元。由此可知:

$$S(n) = F(n+1) = (\Phi^{n+1}-\hat{\Phi}^{n+1})/\sqrt{5}, \Phi = (1+\sqrt{5})/2, \hat{\Phi} = (1-\sqrt{5})/2$$ $$T(n) = 2*S(n)-1 = 2*fib(n+1)-1 = \mathcal{O}(\Phi^{n+1}) = \mathcal{O}(2^{n})$$

---

优化策略

为了消除递归算法中重复的递归实例，一种自然的思路是：借助一定量的辅助空间，在各子问题求解之后，及时记录保存下来。
比如，可以从原问题出发自顶而下，每遇到一个子问题，都首先检查它是否计算过，以期通过直接调阅记录获得解答，从而避免直接计算。也可以从递归基出发，自底而上递推得出各子问题的解，直至最终原问题的解。前者即所谓的制表(tabulation)或记忆(memoization)策略，后者即所谓的动态规划(dynamic programming)策略。

---

线性递归

为应用上述制表的策略，首先需从改造数的递归定义入手。
原算法之所以采用二分递归模式，完全是因为受到该问题原始定义的表面特征——由和共同决定——的误导。然而不难看出，子问题和实际上并非彼此独立。比如，只要转而采用定义如下的递归函数，计算一对相邻的数：

$$(fib(k-1),fib(k))$$

即可得到效率更高的线性递归版算法。

_int64 fib (int n,_int64& prev)
{
    if (n == 0) {prev = 1; return 0;} //到达递归基，直接取值：fib(-1) = 1, fib(0) = 0
    else
    {
        _int64 prevPrev; prev = fib(n-1,prevPrev); //递归计算前两项
        return prevPrev + prev; //其和即为正解
    }
}

原二分递归版本中对应于的另一次递归，在这里被省略掉了。其对应的解答，可借助形式参数的机制，通过变量“调阅”此前的记录直接获得。
该算法呈线性递归模式，递归的深度线性正比于输入，前后共计仅出现个递归实例，累计耗时不超过。遗憾的是，该算法共需使用规模的附加空间。

---

迭代

反观以上线性递归版算法可见，其中所记录的每一个子问题的解答，只会用到一次。在该算法抵达递归基之后的逐层返回过程中，每向上返回一层，以下各层的解答均不必继续保留。
若将以上逐层返回的过程，等效地视作从递归基出发，按规模自小而大求解各子问题的过程，即刻采用动态规划的策略，将以上算法进一步改写为迭代版。

class fib
{
	private:
		_int64 f,g;
		public:
			fib(_int64 n)                               //初始化为不小于n的最小fibonacci项 
			{·· 
				f=1;
				g=0;
				while(g<n) next();
			}
			_int64 get()                                //获取当前Fibonacci数
			{
				return g;
			 } 
			void next()                                 //转入下一项
			{
				g+=f; 
				f=g-f;
				return g;
			}
			void prev()                                 //转入上一项
			{
				f=g-f;
				g-=f;
				return g;
			}
			
};

这里仅使用了两个中间变量和，记录当前的一对相邻数。整个算法仅需线性步的迭代，时间复杂度为。更重要的是，该版本仅需常数规模的附加空间，空间效率也有了极大提高。