蓝桥杯（1）斐波拉契数列问题

古城微笑少年丶 2022-06-04 10:08 136阅读 0赞

package com.lanqiaobei.model1;
    
    import java.util.Scanner;
    
    /*问题描述
    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。*/
    //模加公式  ：(A+B) Mod N = (A Mod N + B Mod N) Mod N，所以Fn的余数可以由F(n-1) Mod N + F(n-2) Mod N求出
    public class Main4 {
    		
    		public static int MAX = 10007;  
    	    public static void main(String[] agrs)  
    	    {  
    	        Scanner scanner = new Scanner(System.in);  
    	        int n = scanner.nextInt();  
    	        int f1,f2,f3;  
    	        f1 = f2 = 1;  
    	        f3 = 1;  
    	        for(int i = 3; i <= n; i++)  
    	        {  
    	        	
    	            f3 = (f2%MAX + f1%MAX)%MAX;  
    	            f1 = f2;  
    	            f2 = f3;  
    	        }  
    	        System.out.println(f3); 
    	}
    
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI5MzQzMjU_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI5MzQzMjU_size_16_color_FFFFFF_t_70]: /images/20220604/8e4dcd5daff54067ba393efe09641438.png