斐波那契凤尾

凤尾"/>

斐波那契凤尾

斐波那契凤尾

• • 斐波那契凤尾
  • 坑1
  • 解决坑1
  • 坑2
  • 解决坑2
  • 完整代码

斐波那契凤尾

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

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

输出描述:
对应每一组输入，输出第n个斐波那契数的最后6位。
示例1
输入
1
2
3
4
100000
输出
1
2
3
5
537501

链接：
来源：牛客网

坑1

这个是我觉得没啥问题的代码

import java.util.*;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);while(in.hasNext()) {int n = in.nextInt();int a = 1;int b = 2;int count = 2;int c = 0;if(n == 1) {System.out.println(1);}else if(n == 2) {System.out.println(2);}else {while(count < n) {c = (a+b)%1000000;a = b;b = c;count++;}System.out.println(c);}}}
}

这个代码是会运行超时的

原因就是测试用例太对，每次都要执行这个大的循环

解决坑1

对于这样类似的题目,最好的方式是进行预处理,把要计算的数值进行第一次计算的时候存储下来,然后剩下的测试用例只进行查找即可，因为查找比计算更加高效，再加上一次运算总比次次运算要快。不要担心第一次计算那么大数值时候回超时，因为这个数量级的运算还是很快的。

import java.util.*;public class Main {public static int[] fid = new int[100001];public static void main(String[] args) {Scanner in = new Scanner(System.in);fiding(fid.length);while(in.hasNext()) {int n = in.nextInt();System.out.println(fid[n]);}}public static void fiding(int n) {fid[0] = 1;fid[1] = 1;int i = 2;while(i < n) {fid[i] = (fid[i-1] + fid[i-2])%1000000;i++;}}
}

坑2

这里比如 n = 37这个测试用例，预期输出应该是 088169 ，但是这个代码输出是 88169，因为是取余的，所以 0 会没有，所以我们需要对输出进行处理

解决坑2

如果大的数字，需要给前面补0，则可以这么写String.format("%06d",fid[n])

这样保证6位数，不到6位数前面补0

完整代码

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