算法 - 斐波那契数列

  • 作者:Moilk
  • 最后编辑:2016年03月18日
  • 标签: 算法

  斐波那契数列中每个数都是其两个直接前项的和,其生成规则如下所示:

.

指数算法

  要求斐波那契数列的第n项值一种简单的方法就是使用递归

function fib(n)
if n=0: return 0;
if n=1: return 1;
return fib(n-1)+fib(n-2);

  但是使用递归来计算第n项,它消耗的资源是指数级增长的。如下图所示,一个fib(n)会触发一连串的递归操作,而这些操作中有很多步骤是重复的。因此,这个算法虽然正确,但是效率太低。
指数算法

多项式算法

  递归的方法对资源的消耗太大,更合理的方法是使用循环来完成,随时保存中间结果。

function fib(n)
if n=0: return 0;
create an array f[0…n]
f[0]=0,f[1]=1
for i=2…n:
 f[i]=f[i-1]+f[i-2]
return f[n]

矩阵算法

  首先,对于数列的初始条件对应以下的矩阵运算

  更一般化地,有

  所以,可以得到:

  综上所述,要的出斐波那契数列的第n项,实际上就是对一个二维矩阵求n次幂。采用矩阵的快速幂算法,操作次数优化为O(log n)。

以下为java实现的三种计算斐波那契数列第n项算法:

import java.util.Scanner;

public class Fibonacci {
	public static void main(String argv[]) {
		// 输入
		System.out.print("请输入一个整数:");
		Scanner x = new Scanner(System.in);
		int n = x.nextInt();

		// 运算
		Fibonacci fib = new Fibonacci();
		long fibn = fib.fib3(n);

		// 结果显示
		System.out.println("fib(n)=" + fibn);
	}

	/**
	 * 指数算法 n大于40延时就明显了
	 * @param n
	 * @return
	 */
	public long fib1(int n) {
		if (n == 0) {
			return 0;
		}
		if (n == 1) {
			return 1;
		}
		return fib1(n - 1) + fib1(n - 2);
	}

	/**
	 * 多项式算法 由于long的范围限制,结果在n属于[0,92]正确。
	 * 当n为8个9时有明显延迟(已溢出)
	 * @param n
	 * @return
	 */
	public long fib2(int n) {
		if (n == 0)
			return 0;

		long[] f = new long[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];
	}
	
	/**
	 * 矩阵算法 n在[0,92]内结果正确
	 * 当n为9个9时仍然无明显延迟(已溢出)
	 * @param n
	 * @return
	 */
	public long fib3(int n) {
		Matrix2 m=new Matrix2(0,1,1,1);
		m=m.fastPower(n);
		
		return m.getMatrix()[0][1];
	}
}

/**
 * 二维矩阵类
 * 功能实现:矩阵乘法;快速求幂;
 * @author Moilk
 *
 */
class Matrix2 {
	private long[][] pmatrix;

	public Matrix2() {
		pmatrix = new long[2][2];
	}

	public Matrix2(long a, long b, long c, long d) {
		setMatrix(new long[][] { { a, b }, { c, d } });
	}

	/**
	 * 快速幂
	 * @param n 幂
	 * @return 运算结果
	 */
	public Matrix2 fastPower(int n){
		Matrix2 result=new Matrix2(1,0,1,0);	//初始化为单位矩阵
		Matrix2 tmp=this;
		while(n!=0){
			if((n&1)==1){
				result=multi(result,tmp);
			}
			tmp=multi(tmp,tmp);
			n>>=1;
		}
		
		return result;
	}
	
	/**
	 * 矩阵乘法
	 * @param m1 矩阵1
	 * @param m2 矩阵2
	 * @return 乘积
	 */
	public Matrix2 multi(Matrix2 m1,Matrix2 m2) {

		Matrix2 tmp = new Matrix2();
		tmp.getMatrix()[0][0] = m1.getMatrix()[0][0] * m2.getMatrix()[0][0] + m1.getMatrix()[0][1] * m2.getMatrix()[1][0];
		tmp.getMatrix()[0][1] = m1.getMatrix()[0][0] * m2.getMatrix()[0][1] + m1.getMatrix()[0][1] * m2.getMatrix()[1][1];
		tmp.getMatrix()[1][0] = m1.getMatrix()[1][0] * m2.getMatrix()[0][0] + m1.getMatrix()[1][1] * m2.getMatrix()[1][0];
		tmp.getMatrix()[1][1] = m1.getMatrix()[1][0] * m2.getMatrix()[0][1] + m1.getMatrix()[1][1] * m2.getMatrix()[1][1];

		return tmp;
	}

	public long[][] getMatrix() {
		return pmatrix;
	}

	public void setMatrix(long[][] pmatrix) {
		this.pmatrix = pmatrix;
	}
}