斐波南希数列

斐波南希数列

1,1,2,3,5,8,13,21,34,...这样看上去很特别的数列就是大名鼎鼎的斐波南希数列。从第二位开始每位数字都是前两位数字的和。
我们通过数学方法归纳后可以得出她的计算公式：
F[n]=F[n-1]+F[n-2]
那么我们就先用这个公式来给个最简单的算法：
long Fib(int n){
  if(n<=2){
    return 1;
  }
  else{
    return Fib(n)=Fib(n-1)+Fib(n-2);
  }
}
递归的方法看上去很直观，但是实际中这种方法在n太大的情况下效率很低。我个人比较喜欢用迭代的方法：
long Fib(int n){
  int x=0,y=1;
  for(int i=1;i<n;i++){
    y=x+y;
    x=y-x;
  }
  return y;
}


[ps:我为什么第一个写的算法学习笔记就是斐波南希数列呢。。。说起来惭愧，今天面试的题目中就有一道算法题是斐波南希数列。。。可惜我当时脑子宕机了没做出来。。。而且这个我个人推荐的算法也不是很好，在计算效率上还是比较低下。因此，求大家踊跃拍砖。]