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

斐波那契数列余数非递归算法
因为这题是求斐波那契数列的余数,不必考虑第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);
		}
	}
}