当前位置:首页 > 开发 > 编程语言 > 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

    震惊

    震惊

编辑推荐
题目:http://codeforces.com/contest/392/problem/C 题意:给定Fibonacci数列F[],令,求的值。 分
#!/bin/bash # Program--fib.sh # Use loop to calculate fibonacci at n # History: # 2013/05/24
一:递归实现   使用公式f[n]=f[n-1]+f[n-2],依次递归计算,递归结束条件是f[1]=1,f[2]=1。 二
/* * Copyright (c) 2013, 烟台大学计算机学院 * All rights reserved. * 作 者:马广明 * 完成日期
我们知道Fibonacci数列的第n个数为F(n) = F(n-1) + F(n-2), F(0) = 0, F(1) = 1。这里,我们数组的
用递归的方式求斐波那契数列的第n个数。 用非递归的方式求斐波那契数列的第n个数。 定义: 斐波那契
斐波纳契数列(Fibonacci Sequence),又称黄金分割数列。 意大利的数学家列昂那多·斐波那契在1202
/* * Copyright (c)2012, 烟台大学计算机学院 * All rightsreserved. * 作 者:荆世琛 * 完成日期:20
1. * 2. * Copyright (c) 2012, 烟台大学计算机学院 3. * All rights reserved. 4. * 作 者: 吕建
/* *Copyright (c)2013,烟台大学计算机学院 *All rights reserved. *文件名称:test.cpp *作者:孙
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号