fibonacci.java

来自「PKU中一些数据结构基本算法题的java实现」· Java 代码 · 共 66 行

package PKU;
import java.math.*;
import java.util.*;
/**
 * @author yhm
 * PKU ID 3070
 */
public class Fibonacci {


	/**
	 * @param args
	 */
	public static void main(String[] args) {

		//System.out.println(FibonacciSolve(100).n0);
		Scanner cin = new Scanner(System.in);
		while(true){
			int n = cin.nextInt();
			if(n==-1) break;
			System.out.println(FibonacciSolve1(n)[1][0]);
		}
		

	}
	
	static int[][] FibonacciSolve1(int n){
		int[][] result = new int[2][2];
		int[][] temp;
		//System.out.println(n);
		if(n==0){
			result[0][0]=1;
			result[0][1]=0;
			result[1][0]=0;
			result[1][1]=1;
		}
		else if(n==1){
			result[0][0]=0;
			result[0][1]=1;
			result[1][0]=1;
			result[1][1]=1;
		}
		else if(n%2==0){
			temp = FibonacciSolve1(n/2);
			result = Mul(temp,temp);
		}
		else{
			temp = FibonacciSolve1((n-1)/2);
			temp = Mul(temp,temp);
			result = Mul(FibonacciSolve1(1),temp);
		}
		//System.out.println(n);
		return result;
	}
	static int[][] Mul(int[][] n1, int[][] n2){
		int[][] result = new int[2][2];
		result[0][0]=(n1[0][0]*n2[0][0]+n1[0][1]*n2[1][0])%10000;
		result[0][1]=(n1[0][1]*n2[1][1]+n1[0][0]*n2[0][1])%10000;
		result[1][0]=(n1[1][1]*n2[1][0]+n1[1][0]*n2[0][0])%10000;
		result[1][1]=(n1[1][1]*n2[1][1]+n1[1][0]*n2[0][1])%10000;
		return result;
	}
	

}