斐波那契凤尾（Java）

凤尾（Java）"/>

斐波那契凤尾（Java）

牛客链接

斐波那契凤尾

题目

NowCoder号称自己已经记住了1-100000之间所有的斐波那契数。
为了考验他，我们随便出一个数n，让他说出第n个斐波那契数。当然，斐波那契数会很大。因此，如果第n个斐波那契数不到6位，则说出该数；否则只说出最后6位。

输入描述

输入有多组数据。
每组数据一行，包含一个整数n (1≤n≤100000)。

输出描述

对应每一组输入，输出第n个斐波那契数的最后6位。

解题思路

按理说求斐波那契数时，不使用递归的算法的复杂度会低，但是在牛客运行后还是会超时，但是如果提前将1-100000的斐波那契数存储到数组中，直接根据输入的数据查询就可以通过了（可能是因为牛客从输入开始算的复杂度，毕竟查询数组取出数据比计算快），大于六位数的时候直接将后六位存储进去，运算下一个斐波那契数时不影响后六位的值。需要注意的是如果和100000取余后是5位数呢?也就是倒数第六位数刚好是0的情况，例如：假设有一个斐波那契数是1024568，那么和100000取余后的数为24568了，但是如果取后六位则应该补0，所以直接将大于等于6位数的斐波那契数（n >= 29）进行%06d的格式输出即可。

代码实现

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int[] fib = new int[100001];fib[0] = 1;fib[1] = 1;for (int i = 2;i<fib.length;i++) {fib[i] = (fib[i-1] + fib[i-2])%1000000;}while (sc.hasNext()) {int num = sc.nextInt();if (num<29) {System.out.println(fib[num]);}else {System.out.printf("%06d\n",fib[num]);}}}
}