蓝桥杯 入门训练 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了,代码不必说了。
1import java.util.*;
2
3public class Fibonacci {
4 public static void main(String []args) {
5 int[] fibonacci = new int[1000001];
6
7 int temp;
8
9 fibonacci[0] = 1;
10 fibonacci[1] = 1;
11
12 Scanner in = new Scanner(System.in);
13
14 int n = in.nextInt();
15
16 for (int i = 2; i < n; i++) {
17 fibonacci[i] = (fibonacci[i - 1] + fibonacci[i - 2]) % 10007;
18 }
19
20 System.out.println(fibonacci[n - 1]);
21 }
22}
23
评论 (0)