1.题目

斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

  1. F(0) = 0，F(1) = 1
  2. F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给你 n ，请计算 F(n) 。

示例：

  1. 输入：2
  2. 输出：1
  3. 解释：F(2) = F(1) + F(0) = 1 + 0 = 1
  5. 输入：3
  6. 输出：2
  7. 解释：F(3) = F(2) + F(1) = 1 + 1 = 2
  9. 输入：4
  10. 输出：3
  11. 解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

  • 0 <= n <= 30

2.思路

找规律，如若n小于2，则n为多少，f(n)就为多少；若n大于等于2，根据公式可知，为前面两项数的和，那么我们引入一个中间量来记录该和，一直累加即可

  1.     public int fib(int n) {
  2.         if (n < 2) {
  3.             return n;
  4.         }
  5.         int p = 0, q = 0, r = 1;
  6.         for (int i = 2; i <= n; ++i) {
  7.             p = q; 
  8.             q = r; 
  9.             r = p + q;
  10.         }
  11.         return r;
  12.     }

当然既然是斐波那契数，那么就有通项公式，这里直接列出来：

509. 斐波那契数 - 图1%3D%5Cfrac%7B1%7D%7B%5Csqrt5%7D%5B(%5Cfrac%7B1%2B%5Csqrt5%7D%7B2%7D)%5En-(%5Cfrac%7B1-%5Csqrt5%7D%7B2%7D)%5En%5D%0A#card=math&code=F%28n%29%3D%5Cfrac%7B1%7D%7B%5Csqrt5%7D%5B%28%5Cfrac%7B1%2B%5Csqrt5%7D%7B2%7D%29%5En-%28%5Cfrac%7B1-%5Csqrt5%7D%7B2%7D%29%5En%5D%0A&id=iXTDY)

  1.     public int fib(int n) {
  2.         double sqrt5 = Math.sqrt(5);
  3.         double fibN = Math.pow((1 + sqrt5) / 2, n) - Math.pow((1 - sqrt5) / 2, n);
  4.         return (int) Math.round(fibN / sqrt5);
  5.     }