文章目錄

• 題目
• 解題思路
• 代碼

題目

牛客

解題思路

本題的基本意思就是給你給定一個矩陣：$\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)$，然后一個數n，n表示矩陣$\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)$的n次方，這個n代表一個數也就是解密的結果，即為$\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)$ⁿ的結果的（也是一個矩陣）的左上角數字。
如果該數字小于4就用0補充，如果大于4就只輸出最后4位

同時矩陣的乘法公式如下：

所以先代入前幾個數，可以發現如下規律

當n=1時，左上角值=1

$\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)$

當n=2時，左上角值=2

$\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)$ * $\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)$ =$\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)$

當n=3時，左上角值=3

$\left(\begin{array}{cc}2& 1\\ 1& 1\end{array}\right)$ * $\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)$ = $\left(\begin{array}{cc}3& 2\\ 2& 1\end{array}\right)$

當n=4時，左上角值=4

$\left(\begin{array}{cc}3& 2\\ 2& 1\end{array}\right)$ * $\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)$ = $\left(\begin{array}{cc}5& 3\\ 3& 2\end{array}\right)$

當n=5時，左上角的值=8

$\left(\begin{array}{cc}5& 3\\ 3& 2\end{array}\right)$ * $\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)$ = $\left(\begin{array}{cc}8& 5\\ 5& 3\end{array}\right)$

當n=6時，左上角的值=?

····
····
····

可以發現是很明顯的斐波那契數列

代碼

// write your code here cpp #include <iostream> #include <vector> #include <cstdio> using namespace std;void Fib(vector<int>& fib) {for(int i=2 ;i < 10001;i++){fib.push_back((fib[i-1]+fib[i-2])%10000);} } int main() {int number=0;//數據個數vector<int> fib={1,1};//斐波那契數列Fib(fib);//初始化while(cin >> number){int temp;while(number--){cin >> temp;printf("%04d",fib[temp]);}cout<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的基础编程题之牛客网星际密码的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。