蓝桥杯 入门训练 Fibonacci数列
很早写好了一直没写笔记,其实算法是个很微妙的数学问题,简单的题还是难得题基本上感觉都是数学不过关……
Fibonacci数列的递推公式为:Fn=Fn-1+Fn-2,其中F1=F2=1。
当n比较大时,Fn也非常大,现在我们想知道,Fn除以10007的余数是多少。
以前用C语言也写过斐波那契数列,不过内容不同,如果不知道斐波那契是什么的话,可以看看:http://codesky.me/archives/c-fibonacci-series.wind
事实证明,用直接递归求的方法确实不现实,但是人家有提示嘛:
在本题中,答案是要求Fn除以10007的余数,因此我们只要能算出这个余数即可,而不需要先计算出Fn的准确值,再将计算的结果除以10007取余数,直接计算余数往往比先算出原数再取余简单。
由于在下的数学实在是一团糟,所以根本不知道发生了什么。
然而实际上,数学上有个东西叫做:
和的余数等于余数的和。
数学很神奇,马上就OK了,代码不必说了。
import java.util.*;
public class Fibonacci {
public static void main(String []args) {
int[] fibonacci = new int[1000001];
int temp;
fibonacci[0] = 1;
fibonacci[1] = 1;
Scanner in = new Scanner(System.in);
int n = in.nextInt();
for (int i = 2; i < n; i++) {
fibonacci[i] = (fibonacci[i - 1] + fibonacci[i - 2]) % 10007;
}
System.out.println(fibonacci[n - 1]);
}
}
植入部分
如果您觉得文章不错,可以通过赞助支持我。
如果您不希望打赏,也可以通过关闭广告屏蔽插件的形式帮助网站运作。