数据结构与算法

斐波那契数列

略

题目：写一个函数：输入n，求斐波那契（Fibonacci）数列的第n项。斐波那契数列的定义如下：

当n=0，f(n)=1；当n=1，f(n)=1，当n>1，f(n)=f(n-1)+f(n-2)。

  斐波那契数列在基础学习中就遇到过，关于递归的讲解经常会用斐波那契做为例子，斐波那契数列的特点是数列中从第三个数开始，数值都是前两个数之和。

分析

递归

讲递归的时候，斐波那契数列的例子一般是这样的：

1
2
3
4
5
int Fibonacci(int n){
  if(n <= 0)	return 1;
  if(n == 1)	return 1;
  return Fibonacci(n - 1) + Fibonacci(n - 2);
}

  处理数据时，它是这样的，例如n=6，要求n=6，就要求n=5和n=4，要求n=5，就要求n=4和n=3，同理要求n=4就要求n=3和n=2，要求n=3，就要求n=2和n=1。根据递归的机制，完成这个计算需要大量重复地计算f(0)和f(1)。

  递归的方法代码量比较少，但是它却把繁重的处理过程交给机器去完成，随着数据量的增加，这种方法必定不可取.

循环

  由本题可知，计算一个数需要知道前两个数，所以我们可以利用循环，依次计算出每个数，例如要算n=6，那就从n=3开始，f(3)=1+1=2，f(4)=1+2=3，f(5)=2+3=5，f(6)=3+5=8，即可得出n=6时的数。

代码实现

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int Fibonacci(int n) {
        if(n == 1) return 1;
        if(n == 2) return 1;
        
        int one = 1;
        int two = 1;
        int sum = 0;
        for(int i = 3;i <= n;++i){
            sum = one + two;
            two = one;
            one = sum;
        }
        return sum;
    }
}

总结

  1. 使用递归的解法非常直观，但是时间效率却很低，实际开发中不会用到这种方法。
  2. 使用循环实现，极大的提高了时间效率，很多情况下要学会把递归用循环来实现。

拓展延伸

题目：一只青蛙一次可以跳1个台阶，也可以跳2个台阶。求该青蛙跳上n级台阶一共有多少种跳法。

  我们可以这样思考，跳n级台阶的跳法有f(n)种，但是他的第一步有两种，一是跳1，二是跳2。如果跳1，则剩余台阶n-1个，跳法有f(n-1)种，如果跳2，则剩余台阶n-2个，跳法有f(n-2)种。两种跳法的种类相加，即是n级台阶的跳法的种类，即f(n)=f(n-1)+f(n-2)。不难看出他就是一个斐波那契数列了，台阶数-跳法：1-1；2-2；3-3；4-5；5-8….