Fn除以10007的余数是多少
算余数的算法,这样可以数据防止越界
- //原理:
- //(a + b) mod m = ((a mod m) + (b mod m)) mod m
- //(a*b) mod m = ((a mod m) * (b mod m)) mod m
问题描述
Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。
当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int n;
int m=10007;
Scanner in = new Scanner(System.in);
n = in.nextInt();
int f[] = new int[n+2];//存放余数
f[1]=f[2]=1;
for (int i = 3; i <= n; i++) {
f[i] = (f[i-1] % m +f[i-2] % m) % m;
}
System.out.println(f[n]);
in .close();
}
}
自我反思：
1.java的语法：输入（最后要关闭资源），创建数组（动态）
2.逻辑上：求余的公式代换，不直接求余数，因为这个数可能超出范围，所以分解求余
利用数组存放于余数
越界问题：n=1是最小的输入，数组在初始化的时候初始化到了n=2(下标从0开始),所以数组长度应该是n+2,
下一篇：
C语言二分法查找详解