@蓝桥杯javaB组习题集入门（4）第四题：Fibonacci数列

女爷i 2023-07-03 02:45 13阅读 0赞

## @蓝桥杯javaB组习题集入门（4）第四题：Fibonacci数列 ##

## 关键字：数列、取模 ##

## 问题描述 ##

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。

## 代码： ##

import java.util.Scanner;
    public class Fibonacci {
        
        public static void main(String[]args) {
        //定义 main方法
            Scanner s = new Scanner(System.in);// new 一个 Scanner 类的对象，用来读取键盘输入
            
            int n = s.nextInt();//键盘录入 n 的值
            
            int[] arr = new int[n];//定义一个数组 arr，用以存放
            
            if (1 <= n && n <= 1000000) {
        //筛选排除不在区间的输入 n
                 if (n == 1 || n == 2) {
        //当 n 等于1或2时：第一位和第二位值为1
                	 arr[n - 1] = 1;
                 }else {
        //当 n 的值不为 1 时，进入 for 循环
                	//用 for 循环来存放计算 Fibonacci 数列在该位置上的值（取模存放）
                    for (int i = 2;i < n;i++) {
        
                    	arr[0] = 1;//第一位值为1
                    	arr[1] = 1;//第二位值为1
                    	//每一位的值都等于其前两位值相加，因一个取过模的数对某个数重复取模不会改变其值，
                    	//且结果输出为对 10007 取模的结果，而该结果数列的前后位置又都是动态关联的，
                    	//故可取模存放每一位的值。
                    	arr[i] =(arr[i - 1] + arr[i - 2]) % 10007;
                     }
                 }
            }
            System.out.println(arr[n - 1]);//打印输出第 n 位 arr 数列中的值（也就是我们所求的结果）
        }
    }
    }