快速幂/矩阵快速幂实现斐波那契数列 Java

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了快速幂/矩阵快速幂实现斐波那契数列 Java，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1290字，纯文字阅读大概需要2分钟。

内容图文

参考：斐波那契数列为什么那么重要，所有关于数学的书几乎都会提到？

快速幂

1.快速幂

快速幂算法的核心思想就是每一步都把指数分成两半，而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变。

int Qpow( int a,int n){
	int ans = 1;
	while(n){
		if(n&1) ans*=a ;
		a *= a ;
		n>>= 1;
	}
	return ans;
}

2.矩阵快速幂实现斐波那契数列

1.Description

求斐波那契数列第n项模1000000007的值，其中f(1)=f(2)=1，fib(n)=fib(n-1)+fib(n-2)(n>2)。
输入
一个数 n，保证n在longlong范围内。

输出
一个数，斐波那契数列第n项模1000000007。

2.Example

样例输入
4

样例输出
3

3.Solution

因为数特别多，超过long，而且一个一个加超时，因此需要用其他的方法。

import java.util.*;
public class Main {    
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	long n = sc.nextLong();
    	System.out.println(fast_mod(n));
    }
    
    public static long[][] multi(long[][] ans,long[][] base){
    	long[][] temp = new long[2][2];
    	for(int i=0;i<2;i++) {
    		for(int j=0;j<2;j++) {
    			for(int k=0;k<2;k++) {
    				temp[i][j] = (temp[i][j]+(ans[i][k]*base[k][j])%1000000007)%1000000007;
    			}
    		}
    	}
    	return temp;
    }
    
    public static long fast_mod(long n ) {
    	long[][] base = {{1,1},{1,0}};
    	long[][] ans = {{1,0},{0,1}};//单位矩阵
    	while(n>0) {
    		if((n&1)==1) {
    			ans  = multi(ans, base);
    		}
    		base = multi(base, base);
    		n >>= 1;
    	}
    	return ans[0][1];
    }
}

内容总结

以上是互联网集市为您收集整理的快速幂/矩阵快速幂实现斐波那契数列 Java全部内容，希望文章能够帮你解决快速幂/矩阵快速幂实现斐波那契数列 Java所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端