首页 > 试题广场 >

斐波拉契加强版

[编程题]斐波拉契加强版

热度指数：7390 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

对于斐波拉契经典问题，我们都非常熟悉，通过递推公式F(n) = F(n - 1) + F(n - 2)，我们可以在线性时间内求出第n项F(n)，现在考虑斐波拉契的加强版，我们要求的项数n的范围为int范围内的非负整数，请设计一个高效算法，计算第n项F(n-1)。第一个斐波拉契数为F(0) = 1。

给定一个非负整数，请返回斐波拉契数列的第n项，为了防止溢出，请将结果Mod 1000000007。

测试样例：

返回：2

算法知识视频讲解

Java

johna

import java.util.*;

public class Fibonacci {

	public static final int mod = 1000000007;
	public int getNthNumber(int n ){
		long[][] res = {{1, 1}, {1, 0}};
		long[][] surplus = {{1,0},{0,1}};
		
		while(n>1){
			if(n % 2 == 1){
				surplus = mutiply(surplus, res);
			}
			res = mutiply(res, res);
			n = n/2;
		}
		res = mutiply(res, surplus);
		return res[0][0] % 1000000007;
	}
	public int[][] mutiply(int[][] a, int[][] b) {
		long[][] temp = {{0,0},{0,0}};
		for(int i = 0; i < 2; i++ ){
			for(int j = 0; j < 2; j++){
				for(int k = 0; k < 2; k++){
					temp[i][j]+=a[i][k]*b[k][j]%1000000007;
				}
			}
		}
		return temp;
	}	
}

快要疯掉啦，弄了一个下午还是错的，完全是按照第一个答案的思路改编的，为啥结果会这样，宝宝很不开心