題目描述：

給定一個n*n的矩陣，求該矩陣的k次冪，即P^k

?

思路

1. 和求解整數(shù)冪的思路相同, 使用分治策略, 代碼的框架是

int pow(a, b) {

　　c = pow(a, b/2)

　　c*= c;

　　if(b 為奇數(shù))

　　　　c *= a;

　　return c

}

?

2. 這道題求的是矩陣, 上面的框架不太好用, 畢竟返回一個矩陣是有點不靠譜. 既然顯式的返回矩陣不行, 那就玩?zhèn)€把戲, 隱式返回.

將矩陣設(shè)置為全局變量, 使得遞歸函數(shù)里對矩陣的操作全局有效, 就不需要顯式返回矩陣了

?

3. 嘗試僅使用兩個矩陣得出結(jié)果, 但失敗了, 計算矩陣乘法, 至少需要三個矩陣的空間吧

?

代碼

#include <iostream> #include <stdio.h> using namespace std;int matrix1[12][12]; int matrix2[12][12]; int matrix3[12][12];int n, k;void multimatrix(int x) {if(x == 1)return;multimatrix(x/2);for(int i = 0; i < n; i ++) {for(int j = 0; j < n; j ++) {int grid = 0;for(int k = 0; k < n; k ++) {grid += matrix2[i][k]*matrix2[k][j];}matrix3[i][j] = grid;}}for(int i = 0; i < n; i ++) {for(int j = 0; j < n; j ++) {matrix2[i][j] = matrix3[i][j];}}if(x&1) {for(int i = 0; i < n; i ++) {for(int j = 0; j < n; j ++) {int grid = 0;for(int k = 0; k < n; k ++) {grid += matrix2[i][k]*matrix1[k][j];}matrix3[i][j] = grid;}}for(int i = 0; i < n; i ++) {for(int j = 0; j < n; j ++) {matrix2[i][j] = matrix3[i][j];}}} }int main() {int t;scanf("%d", &t);for(int i = 0; i < t; i ++) {scanf("%d%d", &n, &k);for(int i = 0; i < n; i ++) {for(int j = 0; j < n; j ++) {scanf("%d", &matrix1[i][j]);matrix2[i][j] = matrix1[i][j];}}multimatrix(k);for(int i = 0; i < n; i ++) {printf("%d", matrix2[i][0]);for(int j = 1; j < n; j ++) {printf(" %d", matrix2[i][j]);}printf("\n");}}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/xinsheng/p/3586815.html

總結(jié)

以上是生活随笔為你收集整理的九度 1474：矩阵幂(二分法)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。