题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。n<=39

解题思路

我们知道斐波那契数列计算公式为 剑指Offer7 - 斐波那契数列 - 图1。又知道 n 的取值范围，所以有两种做法

  1. 根据公式进行递归计算，直到 n==0 或者 n==1 的情况直接返回对应值。
  2. 根据公式进行递推处理，预处理出 n 范围内的所有的值。

    代码实现

    ```java import java.util.Scanner;

public class Problem7 { public static int Fibonacci(int n) { int[] a = new int[45]; a[0] = 0; a[1] = 1; for(int i = 2;i <= n;i ++) a[i] = a[i-1] + a[i-2]; return a[n]; }

  1. public static int Fibonacci2(int n) {
  2.     if (n == 0)
  3.         return 0;
  4.     if (n == 1)
  5.         return 1;
  6.     return Fibonacci2(n-1) + Fibonacci2(n - 2);
  7. }
  9. public static void main(String[] args) {
  10.     Scanner cin = new Scanner(System.in);
  11.     int n = cin.nextInt();
  12.     System.out.println(Fibonacci(n));
  13. }

}

```