ts实现

  1. function fib(n: number): number {
  2.   if (n <= 1) return n
  3.   return fib(n - 1) + fib(n - 2)
  4. }

java实现

  1. class Solution {
  2.     // TODO: for循环实现
  3.     public int fib(int N) {
  4.         if (N <= 1) return N;
  5.         int first = 0;
  6.         int second = 1;
  7.         for (int i = 0; i < N - 1; i++) {
  8.             int sum = first + second;
  9.             first = second;
  10.             second = sum;
  11.         }
  12.         return second;
  13.     }
  14. //    // TODO: 递归实现O(2^n)
  15. //    public int fib1(int n) {
  16. //        if (n <= 1) return n;
  17. //        return fib1(n - 1) + fib1(n - 2);
  18. //    }
  19. //    // TODO: 首尾实现
  20. //    public int fib3(int n) {
  21. //        if (n <= 1) return n;
  22. //        int first = 0;
  23. //        int second = 1;
  24. //        while (n-- > 1) {
  25. //            second += first;
  26. //            first = second - first;
  27. //        }
  28. //        return second;
  29. //    }
  30. }

C++实现

  1. // 递归：O(2^n)
  2. public static int fib1(int n) {
  3.     if (n <= 1) return n;
  4.     return fib1(n - 1) + fib1(n - 2);
  5. }
  7. // for循环：O(n)
  8. public static int fib2(int n) {
  9.     if (n <= 1) return n;
  10.     int first = 0;
  11.     int second = 1;
  12.     for (int i = 0; i < n - 1; i++) {
  13.         int sum = first + second;
  14.         first = second;
  15.         second = sum;
  16.     }
  17.     return second;
  18. }
  19. // 首尾法
  20. public static int fib3(int n) {
  21.     if (n <= 1) return n;
  23.     int first = 0;
  24.     int second = 1;
  25.     while (n-- > 1) {
  26.         second += first;
  27.         first = second - first;
  28.     }
  29.     return second;
  30. }
  31. // 特征方程解法：O（1）
  32. public static int fib4(int n) {
  33.     double c = Math.sqrt(5);
  34.     return (int) (Math.pow((1+c) / 2, n) - Math.pow((1-c) / 2, c));
  35. }