前言

This Series aritcles are all based on the book 《经典算法大全》; 对于该书的所有案例进行一个探究和拓展，并且用python和C++进行实现; 目的是熟悉常用算法过程中的技巧和逻辑拓展。

提出问题

斐波拉契数列; 历史背景略， 有兴趣的可以自己查阅下这个兔子问题， 我们关注的是算法本身的逻辑优化; 问题 :首项是 n-1 A(n)=A(n−1)+A(n−2)

分析和解释

这个是非常直观的这个就不说了，相信很多读者根据特殊方程的思路都能很快求出这个通项公式。

代码

# coding = "utf-8" def feb(n): if(n==1 & n==2): return 1 else: return feb(n-1)+feb(n-2) def feb2(n): a = [] for i in [x+1 for x in range(n)]:

C++ template 编程版本

这里关于C++ 模板编程是将原本是指数级的复杂度压缩到了 O(1) . 将所有的负载全部转移到了编译期。 一般是对执行期的体验要就高这样做。N 必须在 编译期获知， 这里不解释了，以后专门有C++ template课题讲解。

#include<iostream> using namespace std; template<unsigned N> struct Fib { enum { Val = Fib<N-1>::Val + Fib<N-2>::Val }; }; template<> struct Fib<0> {enum {Val = 1};}; template<> struct Fib<1> {enum {Val = 1};}; #define FibT(n) Fib<n>::Val int main() { cout << FibT(10) << endl; return 0; }

”’

拓展和关联

Feb数列本身是个非常简单的递推关系， 对于我们优化算法本身的这个逻辑提升非常有限， 我们更愿意花更多的精力去探究更有价值的事物，这里略； python 也可以用迭代器的方法来优化; 这里略。

后记

NULL

参考书籍

《经典算法大全》维基百科