凤尾"/>
斐波那契凤尾
斐波那契凤尾
- 斐波那契凤尾
- 坑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++;}}
}
更多推荐
斐波那契凤尾
发布评论