蓝桥杯练习:入门训练 Fibonacci数列

迷南。 2022-07-15 12:20 368阅读 0赞

问题描述

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

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

输入格式

输入包含一个整数n。

输出格式

输出一行,包含一个整数,表示F n除以10007的余数。

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

样例输入

10

样例输出

55

样例输入

22

样例输出

7704

数据规模与约定

1 <= n <= 1,000,000。

  1. import java.util.Scanner;
  2. public class Main
  3. {
  4. public static int Fibonacci(int n)
  5. {
  6. int i;
  7. int [] f = new int[n+2];
  8. if(n==1||n==2)
  9. return 1;
  10. f[1]=f[2]=1;
  11. for(i=3;i<=n;i++)
  12. {
  13. f[i]=(f[i-1]+f[i-2])%10007;
  14. }
  15. return f[--i];
  16. }
  17. public static void main(String[] args)
  18. {
  19. Scanner scanner=new Scanner(System.in);
  20. int n=scanner.nextInt();
  21. int f=Fibonacci(n);
  22. System.out.println(f);
  23. }
  24. }

注意蓝桥杯java中不能带package,而且主类必须是Main,不然就不能通过!

发表评论

表情:
评论列表 (有 0 条评论,368人围观)

还没有评论,来说两句吧...

相关阅读