fibonacci数列c语言蓝桥杯(fibonacci数列c语言)

问题描述

Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。

当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。

说明：在本题中，答案是要求Fn除以10007的余数，因此我们只要能算出这个余数即可，而不需要先计算出Fn的准确值，再将计算的结果除以10007取余数，直接计算余数往往比先算出原数再取余数简单。

人家的这个说明还是比较重要的，因为在第一遍做的时候我就出现了报内存不够的错误，第一遍代码就是典型的Fibonacci数列算法。

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Double n = sc.nextDouble();
		Double N = fibonacii(n);
		System.out.print((int) (N % 10007));

	}

	public static Double fibonacii(Double n) {
		if (n == 1 || n == 0) {
			return 1.0;
		} else {
			return fibonacii(n - 1) + fibonacii(n - 2);
		}
	}
}

当时在跑代码时，输入30以内的数字时并没有明显的卡顿，但当输入40以上时就出现明显的卡顿现象，说明这种方法是非常耗时的。所以就另想思路......

想的思路就是定义一个数组，用数组来保存对10007的余数，这样就会节省大量内存空间：

import java.util.Scanner;

public class FibonaciiShuLie1 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] numArray = new int[n + 2];// 这里的numArray[0]不再使用
		// 之所以n+2是因为当输入的是n1时防止出现数组索引越界的情况，还有就是numArray[2]=1的赋值问题
		numArray[1] = 1;
		numArray[2] = 1;
		if (n > 2) {
			for (int i = 3; i < n + 1; i++) {// n+1的原因是为了使最大时numArray[i]赋上值
				numArray[i] = (numArray[i - 1] + numArray[i - 2]) % 10007;
			}
		}
		System.out.print(numArray[n]);

	}

}

这里的代码需要注意的问题已经写在注释里了，大家可以仔细想一想这里面的逻辑。