我正在编写一个C程序来计算一个方形数组,该数组被提升到N的幂。
我想在单独的函数中编写它们以保持它的清洁。我有一个功能
arrMult(int M, int R[M][M], int X[M][M], int out[M][M])
这基本上是out = R*X
。为了将它提升到某个N次幂,我写了这个函数:
int arrNthPow(int M, int N, int R[M][M], int out[M][M])
{
// Initialize
arrPrint(M, M, out);
arrMult(M, R, R, out);
for (int i = 1; i < N - 1; i++){
arrPrint(M, M, out);
arrMult(M, R, out, out);
}
return 0;
}
但是,我意识到这并没有给我我期望的结果。相反,如果我这样做
arrMult(M, R, R, out1);
arrMult(M, out1, R, out2);
arrMult(M, out2, R, out3);
out3
得到了我正在寻找的答案。我假设我必须以某种方式使用指针来复制arrMult
之后每个数组输出的值,然后再次使用arrMult
进行下一次迭代,但我不确定如何。
我对指针并不是很熟悉,并且不知道如何在不将值复制到temp
变量并使用额外的for循环的情况下编写它。
您的代码中存在多个问题:
arrMult(int M, int M, int R[M][M], int X[M][M], int out[M][M])
有一个额外的论点out
,N == 0
矩阵应设置为单位矩阵。out
,R
矩阵应该收到N == 1
的副本。out
从R
2开始,但你不太可能将输入和输出相同的矩阵传递给arrMult
。您应该使用临时矩阵来存储结果,并将其复制到out
内或arrMult
内或每次矩阵乘法后。这是一个简单的实现:
void arrIdentity(int M, int out[M][M]) {
/* initialize array to identity matrix. */
for (int i = 0; i < M; i++) {
for (int j = 0; j < M; j++) {
out[i][j] = (i == j);
}
}
}
void arrCopy(int M, const int mat[M][M], int out[M][M]) {
/* copy a matrix. */
for (int i = 0; i < M; i++) {
for (int j = 0; j < M; j++) {
out[i][j] = mat[i][j];
}
}
}
void arrMult(int M, const int R[M][M], const int X[M][M], int out[M][M]) {
/* compute matrix multiplication: out = R * X. */
int temp[M][M];
for (int i = 0; i < M; i++) {
for (int j = 0; j < M; j++) {
int sum = 0;
for (int k = 0; k < M; k++) {
sum += R[i][k] * X[k][j];
}
temp[i][j] = sum;
}
arrCopy(M, temp, out);
}
}
int arrNthPow(int M, int N, const int R[M][M], int out[M][M]) {
/* Naive matrix exponentiation */
if (N < 0)
return -1;
if (N == 0) {
arrIdentity(M, out);
return 0;
} else {
arrCopy(M, R, out);
for (int i = 1; i < N; i++) {
arrMult(M, R, out, out);
}
}
return 0;
}
使用维基百科文章中解释的方法,这是一个更有效的替代方案:
int arrNthPow2(int M, int N, const int R[M][M], int out[M][M]) {
/* Matrix exponentiation by squaring */
int X[M][M];
if (N < 0)
return -1;
if (N == 0) {
arrIdentity(M, out);
return 0;
}
if (N == 1) {
arrCopy(M, R, out);
return 0;
}
if (N == 2) {
arrMult(M, R, R, out);
return 0;
}
arrIdentity(M, out);
arrCopy(M, R, X);
while (N > 1) {
if (N & 1)
arrMult(M, X, out, out);
arrMult(M, X, X, X);
N >>= 1;
}
arrMult(M, X, out, out);
return 0;
}