Fibonacci 取余问题

前言

记蓝桥入门训练第一题… 很简单的还折腾了2、3天。最后是找的学长来帮忙。感谢！
做题过程总体分为3个阶段。

先上题目：

问题描述：
Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。
当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。
输入格式
输入包含一个整数n。
输出格式
输出一行，包含一个整数，表示Fn除以10007的余数。
说明：在本题中，答案是要求Fn除以10007的余数，因此我们只要能算出这个余数即可，而不需要先计算出Fn的准确值，再将计算的结果除以10007取余数，直接计算余数往往比先算出原数再取余简单。

第一阶段：

第一次提交是最简单的递归写法，结果出来是运行超时

第二阶段：

之后网上找了参考写法，按自己的思路写出来，结果是10个数据里只有8个正确，2个错误。
上代码：

import java.util.Scanner;
public class Main{
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] numbers = new int[10008];
		 
		numbers[1] = 1;
		numbers[2] = 1;
		 
		for(int i = 3; i <= 10007; i++) {
			numbers[i] = (numbers[i - 1] + numbers[i - 2]) % 10007;
		}
		
		int n = sc.nextInt();
		if( n >= 1 || n <= 1000000) {
			n = n % 10008;
			System.out.println( numbers[n] );
		}else {
			System.out.println(0);
		}
		
	} 
}

因为前面都是正确的，只有最后2个是错，就认为这个测试数据很大，以为int类型不够装，换成了long类型，结果还是一样的。
这里提下long和int的区别：

早期的操作系统是16位系统，
int用二字节表示，范围是-32768~32767；
long用4字节表示，范围是-2147483648~2147483647。
后来发展到32位操作系统，
int 用4字节表示，与long相同。
目前的操作系统已发展到64位操作系统，但因程序编译工艺的不同，两者表现出不同的差别：
32位编译系统：int占四字节，与long相同。
64位编译系统：int占四字节，long占8字节，
　　　　　　　 long数据范围变为：-2^63 ~ 2^63-1

错误原因：

循环放数组时，不能只放前10007个（或10008个），之后的数字还是会不一样的，题目给的提示只是放键盘输入的前n个数。

第三阶段：

正确写法：

import java.util.Scanner;
public class Main{
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] numbers = new int[n];
		if(n==1)  // 后面输出 numbers 下标 会越界
		{
			System.out.print(1);
			return;
		}
		numbers[0] = 1;
		numbers[1] = 1;
		
		for(int i = 2; i < n; i++) 
		{
			numbers[i] = (numbers[i - 1]  + numbers[i - 2]) % 10007;
			//检测 取余 有没有分配率...
//			System.out.print( ((numbers[i - 1]  + numbers[i - 2]) % 10007)+" ");
//			System.out.println( (numbers[i - 1]% 10007  + numbers[i - 2]% 10007 ) );
		}
		System.out.println( numbers[n-1] );
		
	} 
}

先提交的long型，后面改成int型也可以AC
这里也解决了一个疑惑点： 取余没有分配率的！！！
简单证明一下：
（a+b）% c 的结果肯定比c要小
a%c + b%c 的结果有可能比c大呀~