用c++写一个矩阵快速幂的代码
时间: 2023-09-03 15:25:17 浏览: 162
C++实现的快速幂算法-Pow(x,n),本算法实现了迭代和递归两个版本
### 回答1:
下面是用 C 语言实现矩阵快速幂的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXN 10
typedef struct matrix {
int m[MAXN][MAXN];
} Matrix;
Matrix mul(Matrix a, Matrix b, int n) {
Matrix c;
int i, j, k;
for (i = 0; i < n; ++i) {
for (j = 0; j < n; ++j) {
c.m[i][j] = 0;
for (k = 0; k < n; ++k) {
c.m[i][j] += a.m[i][k] * b.m[k][j];
}
}
}
return c;
}
Matrix pow(Matrix a, int n, int k) {
Matrix res;
int i, j;
for (i = 0; i < n; ++i) {
for (j = 0; j < n; ++j) {
res.m[i][j] = (i == j) ? k : 0;
}
}
while (n > 0) {
if (n & 1) {
res = mul(res, a, k);
}
a = mul(a, a, k);
n >>= 1;
}
return res;
}
int main() {
int n, k, i, j;
Matrix a;
printf("请输入矩阵的大小n和幂次k:");
scanf("%d%d", &n, &k);
printf("请输入矩阵A:\n");
for (i = 0; i < n; ++i) {
for (j = 0; j < n; ++j) {
scanf("%d", &a.m[i][j]);
}
}
Matrix res = pow(a, k, n);
printf("矩阵A的%d次幂为:\n", k);
for (i = 0; i < n; ++i) {
for (j = 0; j < n; ++j) {
printf("%d ", res.m[i][j]);
}
printf("\n");
}
return 0;
}
```
该代码中,`Matrix` 结构体表示一个矩阵,`mul()` 函数实现了矩阵的乘法,`pow()` 函数实现了矩阵的快速幂。在 `main()` 函数中,先输入矩阵的大小和幂次,然后输入矩阵 A,最后输出 A 的 k 次幂。
### 回答2:
矩阵快速幂是一种快速计算矩阵乘法的方法,可以在 O(log n) 的时间复杂度内计算一个矩阵的 n 次方。下面是用 C 语言编写一个矩阵快速幂的代码示例:
```c
#include <stdio.h>
#define N 2 // 矩阵的大小
// 矩阵乘法
void multiplyMatrix(int a[N][N], int b[N][N], int result[N][N]) {
int i, j, k;
int temp[N][N];
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
temp[i][j] = 0;
for (k = 0; k < N; k++) {
temp[i][j] += a[i][k] * b[k][j];
}
}
}
// 将结果复制到 result 矩阵中
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
result[i][j] = temp[i][j];
}
}
}
// 矩阵快速幂
void matrixPower(int base[N][N], int exponent, int result[N][N]) {
int i;
int temp[N][N];
// 初始化结果矩阵为单位矩阵
for (i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (i == j) {
result[i][j] = 1;
} else {
result[i][j] = 0;
}
}
}
while (exponent > 0) {
if (exponent % 2 == 1) {
multiplyMatrix(result, base, temp);
// 将结果复制到 result 矩阵中
for (i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
result[i][j] = temp[i][j];
}
}
}
multiplyMatrix(base, base, temp);
// 将结果复制到 base 矩阵中
for (i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
base[i][j] = temp[i][j];
}
}
exponent /= 2;
}
}
// 打印矩阵
void printMatrix(int matrix[N][N]) {
int i, j;
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
printf("%d ", matrix[i][j]);
}
printf("\n");
}
}
int main() {
int base[N][N] = {{1, 1}, {1, 0}};
int exponent = 5;
int result[N][N];
matrixPower(base, exponent, result);
printMatrix(result);
return 0;
}
```
以上代码演示了如何使用 C 语言编写一个矩阵快速幂的程序。程序中先定义了一个矩阵乘法函数 `multiplyMatrix`,用于计算两个矩阵相乘的结果。然后实现了矩阵快速幂函数 `matrixPower`,用于计算一个矩阵的指数次方。最后在 `main` 函数中使用示例矩阵和指数调用 `matrixPower` 函数,并通过 `printMatrix` 函数打印结果。
### 回答3:
矩阵快速幂是指将一个矩阵求幂的运算使用快速幂算法进行优化,以提高计算的效率。下面是用C语言编写的一个矩阵快速幂算法的示例代码:
```c
#include <stdio.h>
// 定义矩阵的最大维度
#define MAX_SIZE 10
// 矩阵相乘函数
void matrix_multiply(int n, int a[][MAX_SIZE], int b[][MAX_SIZE], int c[][MAX_SIZE]) {
int i, j, k;
for(i=0; i<n; i++) {
for(j=0; j<n; j++) {
c[i][j] = 0;
for(k=0; k<n; k++) {
c[i][j] += a[i][k] * b[k][j];
}
}
}
}
// 矩阵快速幂函数
void matrix_power(int n, int a[][MAX_SIZE], int m, int b[][MAX_SIZE]) {
int i, j;
// 初始化结果矩阵为单位矩阵
for(i=0; i<n; i++) {
for(j=0; j<n; j++) {
if(i == j) {
b[i][j] = 1;
} else {
b[i][j] = 0;
}
}
}
// 进行快速幂运算
while(m > 0) {
if(m % 2 == 1) {
int c[MAX_SIZE][MAX_SIZE];
matrix_multiply(n, b, a, c);
for(i=0; i<n; i++) {
for(j=0; j<n; j++) {
b[i][j] = c[i][j];
}
}
}
int c[MAX_SIZE][MAX_SIZE];
matrix_multiply(n, a, a, c);
for(i=0; i<n; i++) {
for(j=0; j<n; j++) {
a[i][j] = c[i][j];
}
}
m = m / 2;
}
}
int main() {
int n = 3; // 矩阵维度
int a[MAX_SIZE][MAX_SIZE] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; // 输入矩阵
int m = 3; // 幂指数
int b[MAX_SIZE][MAX_SIZE]; // 结果矩阵
matrix_power(n, a, m, b);
// 输出结果矩阵
int i, j;
for(i=0; i<n; i++) {
for(j=0; j<n; j++) {
printf("%d ", b[i][j]);
}
printf("\n");
}
return 0;
}
```
以上代码实现了一个矩阵快速幂算法,其中`matrix_multiply`函数用于计算两个矩阵的乘积,`matrix_power`函数用于进行矩阵的快速幂运算。在`main`函数中,我们可以自定义输入矩阵维度、矩阵内容以及幂指数,并输出矩阵求幂的结果。
阅读全文