问题遇到的现象和发生背景
问题描述
Fibonacci数列的递推公式为:Fn=Fn-1+Fn-2,其中F1=F2=1。
当n比较大时,Fn也非常大,现在我们想知道,Fn除以10007的余数是多少。
输入格式
输入包含一个整数n。
输出格式
输出一行,包含一个整数,表示Fn除以10007的余数。
**说明:在本题中,答案是要求Fn除以10007的余数,因此我们只要能算出这个余数即可,而不需要先计算出Fn的准确值,再将计算的结果除以10007取余数,直接计算余数往往比先算出原数再取余简单。
**
问题相关代码,请勿粘贴截图
只通过部分用例:
import java.util.*;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int a = 1;
int b = 1;
int c = 0;
if(n == 1||n==2)
c = 1;
else
for(int i = 3;i<=n;i++) {
c = a + b;
a = b;
b = c;
}
System.out.println(c%10007);
}
}
可以通过全部用例:
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int a = 1;
int b = 1;
int c = 0;
if(n == 1||n == 2)
c = 1;
else
for(int i = 3;i<=n;i++) {
c = (a + b)%10007;
a = b%10007;
b = c%10007;
}
System.out.println(c);
}
}
运行结果及报错内容
我的解答思路和尝试过的方法
在遇到本题后首先是想用递归先求出第n个斐波那契数,再对10007取余,但提交后显示运行超时。于是我想到可能是因为递归耗时过多,便采用了非递归,提交后只有部分测试用例通过。之后又仔细看了题目和说明,便直接在求斐波那契数列的过程中求出了该斐波那契数对10007取余的结果,提交后通过全部测试用例。
我想要达到的结果
之后在网上查找看了很多资料,但还是不太明白直接在过程中求余数和先算出斐波那契数在求余有什么区别,麻烦有知道的人解答一下,谢谢!