斐波那契数列余数非递归算法

因为这题是求斐波那契数列的余数，不必考虑第n项斐波那契数列的具体数值（n较大的时候，整型数就存储不了斐波那契数列）。而结果mod10007的话就不必考虑存储问题了。（此处了解一下模p运算，用斐波那契数列的余数计算余数也是正确的）

然后就是时间要求，如果用递归来算的，时间复杂度是O（2^n），而题目要求时间是1s，我开始上传的是递归算法的代码，结果只得到了30分，因为当n仅仅达到了十位数，就会超时了。

最终采用非递归算法，定义三个整型变量backOne,backTwo,now分别表示前一项余数、前两项余数、当前余数。用一for循环，不断更新这三项的值即可，时间复杂度是O(n)。

import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int backOne=1,backTwo=1,now=1;
		if(n<3)
			System.out.println(1);
		else
		{
			for(int i=3;i<=n;i++)
			{
				backTwo=backOne;
				backOne=now;
				now=(backOne+backTwo)%10007;
			}
			System.out.println(now);
		}
	}
}

版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/weixin_42416780/article/details/85331475
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。

发表于 2020-02-13 13:50:14
阅读 ( 1008 )
分类：算法

斐波那契数列余数非递归算法

你可能感兴趣的文章

精选的优质文章

0 条评论

官方社群

GO教程

推荐文章

猜你喜欢

随便看看