`

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

 
阅读更多
参考了网上的思路,写了个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;
	}
}



分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics