java斐波那契凤尾

凤尾"/>

java斐波那契凤尾

文章目录

• 题目描述
• 代码如下

题目描述

NowCoder号称自己已经记住了1-100000之间所有的斐波那契数。

为了考验他，我们随便出一个数n，让他说出第n个斐波那契数。当然，斐波那契数会很大。因此，如果第n个斐波那契数不到6位，则说出该数；否则只说出最后6位。

eg:

输入：
1
2
3
4
100000

输出：
1
2
3
5
537501

以下是本篇文章正文内容，下面案例可供参考

代码如下

import java.util.*;public class Main {public static void main(String[] args) {int border = -1;long[] ans = new long[100000];ans[0] = 1;ans[1] = 2;for(int i = 2; i< 100000; i++) {long next = ans[i-1] + ans[i-2];if(border == -1 && next >= 100000){border = i+1;}ans[i] = next % 1000000;}Scanner sc = new Scanner(System.in);while(sc.hasNext()) {int n = sc.nextInt();long f = ans[n-1];if(n<border){System.out.printf("%d\n",f);}else{System.out.printf("%06d\n",f);}}}
}