【找规律】星际密码

大家好，欢迎来到IT知识分享网。

1. 题目

题目描述：

• 星际战争开展了100年之后，NowCoder终于破译了外星人的密码！他们的密码是一串整数，通过一张表里的信息映射成最终4位密码。表的规则是：n对应的值是矩阵X的n次方的左上角，如果这个数不足4位则用0填充，如果大于4位的则只输出最后4位。

  |1 1|^n => |Xn ..| |1 0| |.. ..| 例如n=2时， |1 1|^2 => |1 1| * |1 1| => |2 1| |1 0| |1 0| |1 0| |1 1| 即2对应的数是“0002”。 

输入描述：

• 输入有多组数据。
• 每组数据两行：第一行包含一个整数n (1≤n≤100)；第二行包含n个正整数Xi (1≤Xi≤10000)

输出描述：对应每一组输入，输出一行相应的密码。

示例：

输入：6 18 15 21 13 25 27 5 1 10 100 1000 10000 输出：11 000017501 

2. 矩阵相乘

想做出这道题首先我们要先会矩阵相乘，矩阵相乘规则如下：

维度要求：要进行矩阵乘法，矩阵 $A$ 的列数必须等于矩阵 $B$ 的行数。即如果矩阵 $A$ 的维度是 $m\times n$，矩阵 $B$ 的维度必须是 $n\times p$。乘积矩阵 $C=AB$ 的维度将是 $m\times p$。

元素计算：矩阵 $C$ 中的元素 $c_{ij}$ 是通过将矩阵 $A$ 的第 $i$ 行与矩阵 $B$ 的第 $j$ 列对应元素相乘后求和得到的。公式表示为：

$$c_{ij}=\sum _{k=1}^n{a}_{ik}{b}_{kj}$$

其中，$a_{ik}$ 是矩阵 $A$ 的第 $i$ 行第 $k$ 列的元素，$b_{kj}$ 是矩阵 $B$ 的第 $k$ 行第 $j$ 列的元素。

示例：假设有两个矩阵 $A$ 和 $B$：矩阵 $A=\left(\begin{array}{cc}1& 2\\ 3& 4\end{array}\right)$，矩阵 $B=\left(\begin{array}{cc}5& 6\\ 7& 8\end{array}\right)$，计算矩阵 $C=AB$：

1. $c_{11}$ 的计算：$c_{11}=1\cdot 5+2\cdot 7=5+14=19$
2. $c_{12}$ 的计算：$c_{12}=1\cdot 6+2\cdot 8=6+16=22$
3. $c_{21}$ 的计算：$c_{21}=3\cdot 5+4\cdot 7=15+28=43$
4. $c_{22}$ 的计算：$c_{22}=3\cdot 6+4\cdot 8=18+32=50$

最终，矩阵 $C=\left(\begin{array}{cc}19& 22\\ 43& 50\end{array}\right)$

注意事项：

• 矩阵乘法不满足交换律，即 $AB\ne BA$（在绝大多数情况下）。
• 矩阵乘法满足结合律，即 $(AB)C=A(BC)$。
• 矩阵乘法满足分配律，即 $A(B+C)=AB+AC$。

3. 找规律

找规律可以发现，这道题的题解其实就是斐波那契数列！

下面我们分析一下：

当 n = 1 时： |1 1| 左上角值 = 1 |1 0| 当 n = 2 时： |1 1|*|1 1|=|2 1| 左上角值 = 2 |1 0| |1 0| |1 1| 当 n = 3 时： |2 1|*|1 1|=|3 2| 左上角值 = 3 |1 1| |1 0| |2 1| 当 n = 4 时： |3 2|*|1 1|=|5 3| 左上角值 = 5 |2 1| |1 0| |3 2| 当 n = 5 时： |5 3|*|1 1|=|8 5| 左上角值 = 8 |3 2| |1 0| |5 3| 

1, 2, 3, 5, 8, ... 这正是一个斐波那契数列（少了第一个 1，不过影响不大），所以对这道题的求解就变成了对斐波那契数列的求解，即：后一个数等于前两个数之和！

4. 注意

题目要求 如果这个数不足 4 位则用 0 填充，如果大于 4 位的则只输出最后 4 位，如何解决？

• 如果不足 4 位用 0 填充，可以在输出时使用 printf("%04d", result); 解决；
• 如果大于 4 位只输出最后 4 位，可以在计算时把 result % 10000 ，即可得到后 4 位。

5. 题解

#include <iostream> #include <vector> using namespace std; void Fibonacci(vector<int>& fib) { 
    for (int i = 2; i <= 10000; i++) { 
    fib.push_back((fib[i - 1] + fib[i - 2]) % 10000); } } int main() { 
    // 找规律发现密码数列就是一个斐波那契数列 vector<int> fib = { 
    1, 1 }; Fibonacci(fib); int n = 0; while (cin >> n) { 
    int num = 0; for (int i = 0; i < n; i++) { 
    cin >> num; printf("%04d", fib[num]); } printf("\n"); } return 0; }