Java 斐波那契数列

 Java 常见例子

斐波那契项通常表示为F_n。斐波那契项是前两项的总和，以 0 和 1 开头。在数学上，它可以表示为:

F_n = F_n-1 + F_n-2

边界条件:F₀ = 0 和 F₁ = 1

斐波那契数列:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233.. .

方法一:使用递归方法

在下面的示例中，创建了一个名为 fib() 的递归方法来找出斐波那契数的第 n 项

public class MyClass {
  static int fib(int n) {
    if (n == 0)
      return 0;
    else if (n == 1)
      return 1;
    else
      return fib(n-1) + fib(n-2);
  }

  public static void main(String[] args) {
    System.out.println("Fibonacci 5th term: " + fib(5));
    System.out.println("Fibonacci 6th term: " + fib(6));
    System.out.println("Fibonacci 7th term: " + fib(7));
  }
} 

上面的代码将给出以下输出:

Fibonacci 5th term: 5
Fibonacci 6th term: 8
Fibonacci 7th term: 13 

方法 2:使用动态编程

斐波那契项也可以是使用动态规划进行估计。与递归方法相比，它只计算序列的特定项一次。

public class MyClass {
  static int fib(int n) {
    //创建包含斐波那契项的数组
    int[] f = new int[n+1];
    f[0] = 0;
    f[1] = 1;
    for(int i = 2; i <= n ; i++) {
      f[i] = f[i-1] + f[i-2];
    }
    return f[n];
  }

  public static void main(String[] args) {
    System.out.println("Fibonacci 6th term: " + fib(6));
    System.out.println("Fibonacci 7th term: " + fib(7));
    System.out.println("Fibonacci 8th term: " + fib(8));
  }
} 

上面的代码将给出以下输出:

Fibonacci 6th term: 8
Fibonacci 7th term: 13
Fibonacci 8th term: 21 

方法3:使用三元运算符

这也可以使用三元运算符来实现。

public class MyClass {
  static int fib(int n) {
    int y = (n == 0)? 0 : (n == 1) ? 1 : fib(n-1) + fib(n-2);
    return y;
  }

  public static void main(String[] args) {
    System.out.println("Fibonacci 8th term: " + fib(8));
    System.out.println("Fibonacci 9th term: " + fib(9));
    System.out.println("Fibonacci 10th term: " + fib(10));    
  }
} 

上面的代码将给出以下输出:

Fibonacci 8th term: 21
Fibonacci 9th term: 34
Fibonacci 10th term: 55 

方法4 :空间优化方法

在该方法中，仅使用三个变量，这些变量在每次迭代中都会发生变化，最终计算出斐波那契数列的第n项。

public class MyClass {
  static int fib(int n) {
    int a = 0, b = 1, c = 0;

    if (n == 0)
      return a;

    for(int i = 2; i <= n; i++) {
      c = a + b;
      a = b;
      b = c;    
    }
    
    return b;
  }

  public static void main(String[] args) {
    System.out.println("Fibonacci 9th term: " + fib(9));
    System.out.println("Fibonacci 10th term: " + fib(10));    
    System.out.println("Fibonacci 11th term: " + fib(11));
  }
} 

上面的代码将给出以下结果输出:

Fibonacci 9th term: 34
Fibonacci 10th term: 55
Fibonacci 11th term: 89 

方法5:使用矩阵的幂

斐波那契数列项也可以计算为矩阵的幂。斐波那契数列具有以下属性:

计算F_n,计算并A₀₁ 将是 F_n。

public class MyClass {
  static int fib(int n) {
    int[][] initial = {{1,1},{1,0}};
    int[][] Final = {{1,1},{1,0}};
    int a, b, c, d;
    if (n == 0)
      return 0;
    else {      
      for(int i = 1; i < n ; i++){
        a = Final[0][0]*initial[0][0] + Final[0][1]*initial[1][0];
        b = Final[1][0]*initial[0][0] + Final[1][1]*initial[1][0];
        c = Final[0][0]*initial[0][1] + Final[0][1]*initial[1][1];
        d = Final[1][0]*initial[0][1] + Final[1][1]*initial[1][1];
        Final[0][0] = a;
        Final[1][0] = b;
        Final[0][1] = c;
        Final[1][1] = d;           
      }
    }
    return Final[0][1];
  }

  public static void main(String[] args) {
    System.out.println("Fibonacci 10th term: " + fib(10));    
    System.out.println("Fibonacci 11th term: " + fib(11));
    System.out.println("Fibonacci 12th term: " + fib(12));
  }
} 

上面的代码将给出以下输出:

Fibonacci 10th term: 55
Fibonacci 11th term: 89
Fibonacci 12th term: 144