Fibonacci数列----蓝桥杯（一题多解）

Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。 当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。 输入格式： 输入包含一个整数n。 输出格式： 输出一行，包含一个整数，表示Fn除以10007的余数。 样例输入 10 样例输出 55

题解

1、解题思路： （1）递归解题----但是，本题会超时

因为递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1 也就意味着，递归调用的出口是有两个的: 因为递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1 n == 1，n == 2 因此，可以对题目这样理解： 当n == 1 || n == 2时， 到达对贵的出口，直接return 1 其它情况下, 都是遵循 斐波那契数列的特性： Fn=Fn-1+Fn-2 代码表示为：return fib(n-1)+ fib(n-2); 但是，针对这道题，求解的是 解题利用的一点是： Fn除以10007的余数 由于这道题，数据的范围较大， 数据规模与约定 1 <= n <= 1,000,000。 所以，为了防止直接返回Fn导致超出int表示的范围， 采用： 求模运算， 代码实现为： return fib(n-1)%10007 + fib(n-2)%10007 由于这道题，数据的范围较大， 数据规模与约定 1 <= n <= 1,000,000。 所以，运用递归还是可能会引起 超时，所以采用递归不合适

确实，提交以后，提醒：采用递归，部分测试数据超时了

（2）采用迭代的方法

由于斐波那契数列的递推公式为： * Fn=Fn-1+Fn-2，其中F1=F2=1， * 而且这道题目要求的是：Fn除以10007的余数是多少 * 可以得到，Fn除以10007的余数的迭代公式为： * Fn % 10007=（Fn-1）%10007 + （Fn-2)%10007 * 所以，可以采用迭代的思路来解题， * 每次迭代的过程中，只需要记录当前所求的Fn的前两位数：Fn-1、Fn-2即可

2、代码实现：

import java.util.Scanner;
public class Main {
          
   

	public static void main(String[] args) {
          
   
		//因为 fib方法是非静态的，所以应该将该类实例化之后，才可以调用fib方法
//		Main mainconut = new Main();
		
		Scanner scan = new Scanner(System.in);
		int n ;
		n = scan.nextInt();
		
		System.out.println(fib(n));
		
	}
	//解决方法1：利用递归，但是会超时
//	public static int fib(int n) {
          
   
//		/*
//		 * 因为递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1
//		 * 也就意味着，递归调用的出口是有两个的
//		 * n == 1，n == 2
//		 */
//		if(n==1) {
          
   
//			return 1;
//		}else if(n==2) {
          
   
//			return 1;
//		}else {
          
   
//			/*
//			 * 解题利用的一点是：求模运算，满足“结合律”，
//			 * 即：（m+n)%p = m%p +n%p
//			 */
//			return fib(n-1)%10007 + fib(n-2)%10007;
//		}
	
	//解决方法2：利用迭代的方法
	public static int fib(int n) {
          
   
		/*
		 * 由于斐波那契数列的递推公式为：
		 * Fn=Fn-1+Fn-2，其中F1=F2=1，
		 * 而且这道题目要求的是：Fn除以10007的余数是多少
		 * 可以得到，Fn除以10007的余数的迭代公式为：
		 * Fn % 10007=（Fn-1）%10007 + （Fn-2)%10007
		 * 所以，可以采用迭代的思路来解题，
		 * 每次迭代的过程中，只需要记录所求的Fn的前两位数：Fn-1、Fn-2即可
		 */
		//f1、f2的初始值为1。在迭代的过程中，使用f1、f2来记录 当前所求的fn（用f3来表示）的前两个数的值
		if(n<=2) {
          
   
			return 1;
		}else {
          
   
			int f1=1,f2=1,f3=0;
			//迭代的过程
			for(int i=3;i<=n;i++) {
          
   
				f3 = (f1+f2)%10007;
				f1 = f2;
				f2 = f3;
			}
			return f3;
		}	
	}
	
}

行百里者半九十，坚持下去，才可以走到最后。 加油！