java编程 斐波拉契数列算法集锦【斐波拉契数列】【上】

斐波那契数列（Fibonacci sequence），又称黄金分割数列，是一个非常经典的递归问题。
斐波那契数列，这是一个广为人知的概念，在数学上定义为这样一个数列：0、1、1、2、3、5、8、13、21、34、……即数列的第一项为0，第二项为1，除了前两项数值以外，任意一项数值都是前两项数值的和。这个数列在自然科学的各个领域都有广泛的应用，如计算机科学、生物学、经济学等。

斐波那契数列是一个经典的数学问题，这个数列的神奇之处，在于它能够以惊人的方式反映自然界的许多现象。

用数学语言表达，斐波那契数列(F(n))可以通过递归公式定义：(F(0)=0, F(1)=1), 对于(n > 1), 有(F(n) = F(n-1) + F(n-2))。
斐波那契数列，通过Java实现可以帮助我们深入理解其原理和应用。在实际应用中，我们应根据具体情况选择合适的实现方式，以达到最优的效果。

在Java中，我们可以有很多种实现方法，效率也各不相同。如使用递归或迭代的方式来实现斐波那契数列等等。

下面，我将演绎各种各样的五花八门的斐波那契数列实现算法。

1. 算法1： 首先给出一个斐波那契数列的递归算法版本

斐波那契数列递归公式： f(n) = f(n-1) + f(n-2)
斐波那契数列递归终结点：f(0)=0，f(1)=1；当n=2时，f(2) = f(1) + f(0) = 1
斐波那契数列的递归方向：n -> 2 （n ≥ 2，n ∈ N*）

Java实现的算法源码如下：

package fibonacci;
/**** @author QiuGen* @description  斐波那契数列的递归算法* @date 2024/8/18* ***/
import java.util.Map;
import java.util.TreeMap;
public class FibonacciA {/***斐波那契数列的递归算法，效率低下，每次递归重复计算较小的值***/public static long fib( int n) { if (n==0) return 0;if (n==1) return 1;return fib(n-1) + fib(n-2);}public static void main(String[] args) {System.out.println("***效率低下的递归算法***");Map<Integer,Long> map = new TreeMap<>();for (int i = 0; i < 20; i++) {map.put(i, fib(i));}map.forEach((k,v)->System.out.println(v));}
}

这个递归算法最直观最简明，但非常耗时，非常耗计算机资源，如计算第六项数值时fib(5)的计算过程如下：

fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
由此可见，这个算法在计算后面的项时需要多次重复计算前面所有的项，因此不是一种高效的算法。实际上，该算法的运算时间是呈指数级增长的；而且对计算机的内存资源也是呈指数级增长的，很容易导致计算机资源不足。
复杂度： 时间复杂度是0(n^2),空间复杂度是0(n);
程序运行结果（斐波那契数列前20项的值）：

2. 算法2： 斐波那契数列的优化后的递归算法版本。
   斐波那契数列的优化后的递归算法版本。
   斐波那契数列递归公式： f(n) = f(n-1) + f(n-2)
   斐波那契数列的递归终结点： 自f(0)=0，f(1)=1，递归计算至f(n)。
   斐波那契数列的递归方向：0 -> n （n ≥ 0，n ∈ N*）

这个递归算法不是很简明，有点不太好理解。算法源代码如下：

package fibonacci;
/**** @author QiuGen* @description  斐波那契数列的优化的递归算法FibonacciB* @date 2024/8/18* ***/
public class FibonacciB {static long getFibItem(int index){return getFibItem(0, 1, 0, index);}static long getFibItem(long curr, long next, int currIndex, int index){if (currIndex == index){return curr;}else{return getFibItem(next, curr + next, currIndex + 1, index);}}public static void main(String[] args) {for (int i = 0; i < 20; i++) { //计算前20项System.out.println(getFibItem(i));}}
}

3. 算法3： 斐波那契数列的优化后的尾递归算法版本。
   斐波那契数列的优化后的尾递归算法版本。
   斐波那契数列递归公式： f(n) = f(n-1) + f(n-2)
   斐波那契数列的递归终结点： 自f(0)=0 或 f(1)=1。
   斐波那契数列的递归方向：n -> 1 （n ≥ 0，n ∈ N*）

这个尾递归算法的效率比较高。
空间复杂度： 递归的深度为0(n)，但是由于是尾递归，优化后的空间复杂度是0(1)
时间复杂度： 时间复杂度是0(n)

package fibonacci;
/**** @author QiuGen* @description 斐波那契数列的尾递归算法FibonacciC* @date 2024/8/18* ***/
public class FibonacciC {public static long fib(int index) {return fib(0,1,index);}public static long fib( long n1,long n2,int index) {if(index == 0) {return n1;}if(index == 1) {return n2;}return fib(n2,n1+n2,index - 1);}public static void main(String[] args) {for (int i = 0; i < 20; i++) { //计算前20项System.out.println(fib(i));}}
}

4. 算法4： 借助一个数组列表ArrayList，前两项是0和1，从n=2项起，每一项是之前两项之和。实际上也是一种迭代算法。
   用Java实现斐波那契数列，最容易想到的方式，是用一个数组列表ArrayList，首两项是0和1，从n=2项起，每一项是之前两项之和，循环依次赋值。这个算法的效率还是可以的。

package fibonacci;
/**** @author QiuGen* @description  斐波那契数列的利用列表的算法* @date 2024/8/18* ***/
import java.util.ArrayList;
public class FibonacciList {static ArrayList<Long> list = new ArrayList<>();public static void fib( int n) { list.add (list.get(n-1) + list.get(n-2) );}public static void main(String[] args) {//赋前两项斐波那契数列的初值list.add(0L);list.add(1L);for (int i = 2; i < 20; i++) { //计算前20项fib(i); //计算第i项值}list.forEach(System.out::println);}
}

5. 算法5： 借助一个数组列表ArrayList，另一种迭代算法版本。
   下面是利用数组列表和迭代算法的版本，效率更高一点。

package fibonacci;
/**** @author QiuGen* @description  斐波那契数列利用列表的迭代算法* @date 2024/8/18* ***/
import java.util.ArrayList;
public class FibonacciIterate {static ArrayList<Long> list = new ArrayList<>();//计算前n项public static void fibonacciIterate(int n) {  long a = 0L;  long b = 1L; long c = 0L;for (int i = 0; i < n; i++) { if (i < 2) {if ( i == 0) {list.add(a);} else if ( i == 1) {list.add(b);}continue;}c = a + b;  list.add(c);  a = b;  b = c;  }  } public static void main(String[] args) {//计算前20项fibonacciIterate(20);//计算前20项list.forEach(System.out::println);}
}

6. 算法6： 斐波那契数列的利用矩阵乘法、快速幂的算法版本。

运算原理：

我们目测计算一下。上面第一个公式，相乘后可得等式左边是向量（Fn+1,Fn），右边也是一个向量（（Fn+Fn-1），Fn）。很明显是正确的，相等的，因为，相当于两个等式：Fn+1=（Fn+Fn-1）和Fn=Fn。
当n=1时，第二个公式，计算结果是 F2=1，F1=1。
当n=0时，第二个公式，矩阵的0次幂是等于单位矩阵，因此可得计算结果F1=1，F0 = 0。非常正确。

斐波那契数列的利用矩阵乘法、快速幂的算法版本的源代码如下：

//利用矩阵乘法、快速幂，计算斐波那契数列。
package fibonacci;
import java.math.BigInteger;
class FibonacciCalculator {static class FibonacciMatrixMultiple {public BigInteger a11;public BigInteger a12;public BigInteger a21;public BigInteger a22;public FibonacciMatrixMultiple(BigInteger p_a11, BigInteger p_a12,BigInteger p_a21, BigInteger p_a22) {this.a11 = p_a11;this.a12 = p_a12;this.a21 = p_a21;this.a22 = p_a22;}}public static FibonacciMatrixMultiple Multiply(FibonacciMatrixMultiple mat1, FibonacciMatrixMultiple mat2) {return new FibonacciMatrixMultiple(mat1.a11.multiply(mat2.a11).add(mat1.a12.multiply(mat2.a21)), mat1.a11.multiply(mat2.a12).add(mat1.a12.multiply(mat2.a22)), mat1.a21.multiply(mat2.a11).add(mat1.a22.multiply(mat2.a21)), mat1.a21.multiply(mat2.a12).add(mat1.a22.multiply(mat2.a22)));}static class FibonacciMatrix {public BigInteger a11;public BigInteger a21;public FibonacciMatrix(BigInteger p_a11, BigInteger p_a21) {this.a11 = p_a11;this.a21 = p_a21;}}public static FibonacciMatrix Multiply2(FibonacciMatrixMultiple mat1,FibonacciMatrix mat2) {return new FibonacciMatrix(mat1.a11.multiply(mat2.a11).add(mat1.a12.multiply(mat2.a21)), mat1.a21.multiply(mat2.a11).add(mat1.a22.multiply(mat2.a21)));}private static FibonacciMatrix getFibonacciMatrix(int n) {FibonacciMatrix resultMatrix = new FibonacciMatrix(BigInteger.valueOf(1), BigInteger.valueOf(1));FibonacciMatrixMultiple multiple = new FibonacciMatrixMultiple(BigInteger.valueOf(1), BigInteger.valueOf(1),BigInteger.valueOf(1), BigInteger.valueOf(0));while (n > 0) {if ((n & 1) == 1)resultMatrix = Multiply2(multiple, resultMatrix);n >>= 1;if (n > 0)multiple = Multiply(multiple, multiple);}return resultMatrix;}public static BigInteger getFibonacci(int index) {if (index < 1)return BigInteger.valueOf(0);if (index == 1)return BigInteger.valueOf(1);return getFibonacciMatrix(index - 2).a11;}public static void main(String[] args) {for (int i = 0; i < 20; i++) { //计算前20项System.out.println(getFibonacci(i));}}
}

利用矩阵乘法、快速幂的计算斐波那契数列效率是很高的。尤其当计算较大项（index大于65535）时，所花费的时间要比前面的方法花费的时间少至少一个数量级。