今天看《剑指Offer》看到了斐波那契数列其实用递归调用树的话会有很多重复计算......（之前自己就是一直图省事，感觉写的代码少，用递归很方便，但是仔细一想的确是有很多计算是重复的，浪费了很多时间所以今天的随笔就说一下斐波那契的顺序实现吧

一、常见的递归实现

int Fibonacci(int num){  if(num == 0 || num == 1) return num;  return Fibonacci(num-1)+Fibonacci(num - 2)}

以前的我一直是用递归写的，因为可以看到，真的很方便(这里写的简单了，没有考虑负数和异常输入之类的，自己编写时还是要多加考虑边界条件和异常输入啦~)

我们可以看出比如Num = 4时 要算Num = 3时的值 + Num = 2的值，而Num = 3时又要算一遍Num = 2的值，就很累赘。所以用顺序结构从1到n这样的话，就能少掉这个麻烦。

二、两种顺序实现

第一种方法是用两个数不断变换，最终得到目标值

/*顺序斐波那契额*/#include
    
     int Fibonacci(int n){    int sum = 0,tmp = 0;    int num1 = 0,num2 = 1;    if(n == 0 || n == 1) tmp = n;    for(int i=0;i<=n-2;i++)    {        tmp = num1 + num2;        num1 = num2;        num2 = tmp;    }    return tmp;}int main(){    int n;    while(std::cin>>n)    {        std::cout<<"fnums is :"<
     
      <<"\n";    }       return 0;}
     
    

这一个方法还可以用来寻找一组数的最大值和次大值，也是循环一遍的O(n)还是很方便的。

第二种是使用队列实现

#include
    
     #include
     
      int Fibonacci(int n){    if(n==0 || n==1)        return n;    std::queue
      
        q;    q.push(0);    q.push(1);    while(!q.empty() && n >= 2)    {        int x = q.front();        q.pop();        int y = q.front();        q.push(x+y);        n--;    }    q.pop();    int result = q.front();    q.pop();    return result;}int main(){    int n;    while(std::cin>>n)    {        std::cout<<"fnums is :"<
       
        <<"\n";    }        return 0;}
       
      
     
    

当然还有一种方法是数组实现啦~我觉得用的空间会大于第一种方式，而且原理也并没什么差别在此就不写啦~

总之呢，递归虽然代码量少，（可是代码量少并不是决定一个程序员的强弱啊喂！）但是重复计算过程有点点多，然后可怜的栈也会出现STACK OVERFLOW（栈溢出）的错误，所以还是顺序比较好嘛~随着n的增大，顺序的优势也会更加明显的~

---

在《剑指Offer》上还说了需要知识迁移的能力，提到了一只青蛙一次可以跳上1级台阶，也可以跳上两级台阶，问青蛙跳上n级台阶总共有几种跳法的问题.

这类问题可以这样想，1级台阶有1种，2级台阶有两种，我们可以知道上3级台阶前，青蛙一定是站在n-2(1)级台阶或者上n-1(2)级台阶，所以就是把F(n-2)+F(n-1)加在一起就是上n级台阶的跳法总数啦，没错，就是你！斐波那契数列！

和这个思维很像的还有汉诺塔问题，要把柱子A的N个圆盘放到C，也就是把柱子A的N-1个圆盘放到B，然后再把第N个圆盘放在C，最后把B柱子通过A放到C，也就是2*F（N-1）+1