問題描述 給定一個N階矩陣A,輸出A的M次幂(M是非負整數)
例如:
A =
1 2
3 4
A的2次幂
7 10
15 22 輸入格式 第一行是一個正整數N、M(1<=N<=30, 0<=M<=5),表示矩陣A的階數和要求的幂數
接下來N行,每行N個絕對值不超過10的非負整數,描述矩陣A的值 輸出格式 輸出共N行,每行N個整數,表示A的M次幂所對應的矩陣。相鄰的數之間用一個空格隔開 樣例輸入 2 2
1 2
3 4 樣例輸出 7 10
15 22
題目分析:題意明确,矩陣乘法
算法分析:反思一下,矩陣乘法都會乘,但是通用公式呢,能信手拈來嗎,思路不清晰的盡早百度百科好好複習為上策。否則光一個乘法公式都需要慢慢推導是真的費時費力了。另外,題目中還有一個注意點,就是M是非負整數,矩陣的零次幂是機關陣,不能忘!
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsICM38CXlZHbvN3cpR2Lc1TPB10QGtWUCpEMJ9CXsxWam9CXwADNvwVZ6l2c052bm9CXUJDT1wkNhVzLcRnbvZ2LctmVHpFb1cVY0pEWalWOyMmdRhlW1VTaitmTzkVdjJjYzpkMMZ3bENGMShUYvwFd4VGdvwlMvw1ayFWbyVGdhd3P5EzNwITMxITMxIDM4EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
算法設計:
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
long[][] a = new long[N][N];
long[][] b = new long[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
b[i][j] = a[i][j] = sc.nextLong();
}
}
sc.close();
// 矩陣的0次幂為機關陣
if (M == 0) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (i == j)
System.out.print(1 + " ");
else
System.out.print(0 + " ");
}
System.out.println();
}
} else if (M == 1) { // 矩陣的1次幂為本身
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print(a[i][j] + " ");
System.out.println();
}
}
} else {
for (int x = 1; x < M; x++) {
long[][] temp = new long[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
long result = 0;
for (int k = 0; k < N; k++) {
result += a[i][k] * b[k][j]; // 矩陣乘法
}
temp[i][j] = result;
}
}
b = temp;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print(b[i][j] + " ");
}
System.out.println();
}
}
}
}