二零一四年蓝桥杯JAVA试题

2014年蓝桥杯JAVA试题
1.问题描述 
Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。 
当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。 输入格式 
输入包含一个整数n。 输出格式 
输出一行，包含一个整数，表示Fn除以10007的余数。  
说明：在本题中，答案是要求Fn除以10007的余数，因此我们只要能算出这个余数即可，而不需要先计算出Fn的准确值，再将计算的结果除以10007取余数，直接计算余数往往比先算出原数再取余简单。 样例输入 10 
样例输出 55 
样例输入 22 
样例输出 7704 
数据规模与约定 1 <= n <= 1,000,000。  
使用数组来保存F序列，只保存除10007的余数。
请大家仔细考虑，给出最优答案（模运算的性质？）。
------解决思路----------------------

引用:

由于上班期间没多少时间 目前的思路是Fn+3的余数是通过Fn+1与Fn+2的余数来计算出 具体怎么算有点为难（正忙那）

楼上强人 。。。我还在想 怎么把Fn算出来。。。 

package com.test;

import java.io.ObjectInputStream.GetField;

public class Fibonacci
{
	//除数
	public static final int DIVISOR = 10007;
	//测试输入数（省略了输入的操作）
	public static int in = 22;
	
	/**
	 * 获取下一个数除以除数的余数
	 * @param i
	 * @param j
	 * @return 下一个数的余数
	 */
	public static int getNextRemainder(int i,int j)
	{
		int nextRemainder = i + j;
		if(nextRemainder >= DIVISOR)
		{
			nextRemainder = nextRemainder - DIVISOR;
		}
		return nextRemainder;
	}
	
	public static void main(String[] args)
	{
		//fn+1 与fn+2
		int fn1 = 1;
		int fn2 = 1;
		int fn3 = 0;
		for(int i = 0 ; i < (in -2); i++ )
		{
			fn3 = getNextRemainder(fn1,fn2);
			fn1 = fn2;
			fn2 = fn3; 
		}
		System.out.println(fn3);
	}

}

------解决思路----------------------

public class FibonacciMod10007 {

    public static void main(String[] args) {
        int[] fibonacciMod10007Array = new int[1000001];
        fibonacciMod10007Array[1] = 1;
        fibonacciMod10007Array[2] = 1;
        for (int n = 3; n <= 1000000; n++) {
            fibonacciMod10007Array[n] = (fibonacciMod10007Array[n - 1] % 10007 + fibonacciMod10007Array[n - 2] % 10007) % 10007;
            System.out.println(n + ":" + fibonacciMod10007Array[n]);
        }
    }
}