当前位置:首页 > 开发 > 编程语言 > Java > 正文

java--19.用矩阵求Fibonacci数列的第N项

发表于: 2011-12-12   作者:bylijinnan   来源:转载   浏览:
摘要: 参考了网上的思路,写了个Java版的: public class Fibonacci { final static int[] A={1,1,1,0}; public static void main(String[] args) { int n=7; for(int i=0;i<=n;i++){ int f=fibonac
参考了网上的思路,写了个Java版的:



public class Fibonacci {

	final  static int[] A={1,1,1,0};
	
	
	public static void main(String[] args) {
		int n=7;
		for(int i=0;i<=n;i++){
			int f=fibonacci(i);
			System.out.print(f+" ");
		}
	}

	static int fibonacci(int n){
		if(n==0)return 0;
		if(n==1)return 1;
		if(n>1){
			int[] re=power(n-1);
			return re[0];//矩阵乘积的第00项为所求
		}
		return -1;
	}
	
	//a^n=a^(n/2)*a^(n/2)	or   a^n=a^(n/2)*a^(n/2)*a
	static int[] power(int n){
		int[] a=new int[4];
		if(n==1){
			a=A;
		}
		else if(n%2==0){
			a=matixMultiply(power(n/2),power(n/2));
		}else if(n%2==1){
			int[] temp=matixMultiply(power(n/2),power(n/2));
			a=matixMultiply(A,temp);
		}
		return a;
	}
	
	//矩阵乘法
	// return A*B
	static int[] matixMultiply(int[] a,int [] b){
		int[] re=new int[4];
		re[0]=a[0]*b[0]+a[1]*b[2];
		re[1]=a[0]*b[1]+a[1]*b[3];
		re[2]=a[2]*b[0]+a[3]*b[2];
		re[3]=a[2]*b[1]+a[3]*b[3];
		return re;
	}
}



java--19.用矩阵求Fibonacci数列的第N项

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号