前言
牛客网PAT乙级训练1006
题目描述
星际战争开展了100年之后，NowCoder终于破译了外星人的密码！他们的密码是一串整数，通过一张表里的信息映射成最终4位密码。表的规则是：n对应的值是矩阵X的n次方的左上角，如果这个数不足4位则用0填充，如果大于4位的则只输出最后4位。
矩阵
例如n=2时，
n=2时的矩阵
即2对应的数是“0002”。
输入描述
输入有多组数据。
每组数据两行：第一行包含一个整数n (1≤n≤100)；第二行包含n个正整数Xi (1≤Xi≤10000)
输出描述
对应每一组输入，输出一行相应的密码。
输入例子
6
18 15 21 13 25 27
5
1 10 100 1000 10000
输出例子
418109877711037713937811
00010089410135017501
解析
其实这是一道找规律的题目，找出递归函数后发现这是一个斐波拉契数列。
a[i] = a[i-1] + a[i-2];
本题的难点有两个：
- 斐波拉契数列当项数超过40之后结果就会变得非常大，会导致内存溢出，如何避免？
- 最后的结果怎么判断是几位数并且如何添0？
解决方案
问题一
针对第一个问题，斐波拉契数列的项数超过40之后，他的值就会变得非常非常庞大，但是那么庞大的数字都是我们所需要的吗？
答案当然是否的，仔细看题，最后一句话
如果这个数不足4位则用0填充，如果大于4位的则只输出最后4位。
题目其实已经告诉我们了，最后只需要4位，而在进行庞大的数字运算的时候，前面的数字对于后四位来说根本就无关紧要，反正最终的结果也只是需要后4位。所以接下来的判断就变得尤为重要。
if (a[i] > 9999)
a[i] = a[i] % 10000;
通过这一步，将万位和万位之前的就全部舍去了。避免了超大数字的直接运算。
问题二
接下来就是第二个问题了，如何判断最后的结果是几位数，怎么添加0？
其实到这里的时候就更要感叹一下第一步的那个判断了，通过那个判断很直接的就将最后的结果锁定在4位数以内了，接下来只要一一判断最后的结果的字符串的长度就好了，添加0需要用到StringBuilder类中的append()方法，如下：
int n = sc.nextInt();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
int num = sc.nextInt();
if (String.valueOf(a[num]).length() == 1)
sb.append("000" + a[num]);
else if (String.valueOf(a[num]).length() == 2)
sb.append("00" + a[num]);
else if (String.valueOf(a[num]).length() == 3)
sb.append("0" + a[num]);
else if (String.valueOf(a[num]).length() == 4)
sb.append("" + a[num]);
}
最后再输出结果就好了
System.out.println(sb.toString());
源码
import java.util.Scanner;
public class Main {
public static int a[] = new int[10002];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
a[1] = 1;
a[2] = 2;
for (int i = 3; i < 10001; i++) {
a[i] = a[i - 1] + a[i - 2];
if (a[i] > 9999)
a[i] = a[i] % 10000;
}
while (sc.hasNext()) {
int n = sc.nextInt();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
int num = sc.nextInt();
if (String.valueOf(a[num]).length() == 1)
sb.append("000" + a[num]);
else if (String.valueOf(a[num]).length() == 2)
sb.append("00" + a[num]);
else if (String.valueOf(a[num]).length() == 3)
sb.append("0" + a[num]);
else if (String.valueOf(a[num]).length() == 4)
sb.append("" + a[num]);
}
System.out.println(sb.toString());
}
}
}
