凤尾(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]);}}}
}
更多推荐
斐波那契凤尾(Java)
发布评论