Question

一道蓝桥杯斐波那契数列题 数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。 当n比较大时，Fn也非常大

问题描述
Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。
当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。

public void solve2(int a){
int [] arr=new int[a+1];
arr[1]=arr[2]=1;
for(int i=3;i<arr.length;i++){
arr[i]=(arr[i-1]+arr[i-2])%10007;//对每一个斐波那契数列进行取余数
}
System.out.println(arr[a]);
}
我想问一下 arr[i]=(arr[i-1]+arr[i-2])%10007 对每一斐波那契数列进行取余是什么意思 如何理解
我是这样理解的 例如 当i=4时 余数为 i=3的余数加i=2的余数 再除以10007取余 这样对吗 为什么等于先求值再取余

Answer 1

我觉得应该是因为，斐波那契数列在n不是很大的时候，数列的每一项除以10007的余数都是它本身，所以可以这么加。。
你可以在java里试一下 System.out.println(55%10007);
输出的结果就是55

Answer 2

就是余数相加
因为除去的内个部分正好是10007的倍数
所以余数和原数除以10007的余数是一样的
就像7%4=3
而3%4=3的道理一样
不影响的

Answer 3

#include<stdio.h>

int main(void)
{
int x,y,z,i,n;
x = 0;
y = 0;
z = 1;
i = 0;
scanf("%d",&n);

while(i<n)
{
x=y;
y=z;
z=x+y;
i +=1;
}
y=y%10007;
printf("%d",y);
return 0;
}

Answer 4

显然分别取余有可能余数的和大于10007。