我在想出一种使该算法起作用的方法时遇到了麻烦，因为我无法弄清楚如何解决问题的中间部分。到目前为止，这是我的代码：
int det(int matrixSize, int matrix[][matrixSize]){
int determinant = 0, matrixValues[matrixSize * matrixSize], matrixFirstRowValues[matrixSize * matrixSize];
for(int i = matrixSize; i > 2; i--){
for(int row = 0; row < matrixSize; row++){
for(int col = 0; col < matrixSize; col++){
matrixFirstRowValues[row + (matrixSize - i)] = matrix[1][col + (matrixSize - i)];
//copies the first row values for an array until we have a 2x2 matrix
}
}
}
//multiply the values in matrix Values by their respective matrix without
//the row and column of these values times -1^row+col
determinant += (matrix[matrixSize-1][matrixSize-1] * matrix[matrixSize-2][matrixSize-2])
- (matrix[matrixSize-1][matrixSize-2] * matrix[matrixSize-2][matrixSize-1]);
return determinant;
}
是矩阵，它是一个具有matrixSize大小的二维数组，我对其进行迭代，直到剩下2x2矩阵，然后将第一行的每个值复制到一个新数组中。
这些值必须乘以我删除该值所在的行和列时剩下的矩阵。
这是拉普拉斯展开的原理。给我带来麻烦的部分是通过删除行和列来获取剩余的矩阵，因为我希望它适用于nxn矩阵。
然后，最后求和到2x2矩阵的总和。
如何使用当前设置来处理中间部分（注释在哪里？
我试图使用递归方法解决拉普拉斯展开式。可能对您有帮助
代码：
#include <stdio.h>
int determinant(int size,int det[][4]) // size & row of the square matrix
{
int temp[4][4],a=0,b=0,i,j,k;
int sum=0,sign; /* sum will hold value of determinant of the current matrix */
if(size==2)
return (det[0][0]*det[1][1]-det[1][0]*det[0][1]);
sign=1;
for(i=0;i<size;i++) // note that 'i' will indicate column no.
{
a=0;
b=0;
// copy into submatrix and recurse
for(j=1;j<size;j++) // should start from the next row !!
{
for(k=0;k<size;k++)
{
if(k==i) continue;
temp[a][b++]=det[j][k];
}
a++;
b=0;
}
sum+=sign*det[0][i]*determinant(size-1,temp); // increnting row & decrementing size
sign*=-1;
}
return sum;
}
//Main function
int main()
{
int i,j;
int det[4][4] = {{1, 0, 2, -1},
{3, 0, 0, 5},
{2, 1, 4, -3},
{1, 0, 5, 0}
};
printf("%d",determinant(4,det));
}
干杯！
这些值必须乘以我留下的矩阵删除该值所在的行和列。
您必须乘以其因子为删除第i行和第j列时剩下的矩阵的determinants的辅因子矩阵。
自然，这是递归算法的设置，因为较大矩阵的行列式是用较小矩阵的行列式表示的：如果A = (a_{ij})是矩阵，则det(A) = sum j = 1..n: a_{ij} * det(M_{ij})，其中M_{ij}是删除固定i的第j行和第i列时从A产生的次矩阵。基本情况是2×2矩阵，也可能是3×3矩阵。
[出现的问题是n-by-n矩阵生成大小为n的M_{ij}矩阵(n-1)-by-(n-1)，每个矩阵生成的大小都小于一个的n-1矩阵，依此类推，直到达到基本情况为止，在您必须跟踪n!/2矩阵。 （在这一点上，很明显，拉普拉斯扩展是一种成本很高的算法，任何基于高斯消去的算法都将效率更高。但这只是一个旁听，因为我们正在讨论拉普拉斯扩展。）如果以迭代方式进行，这必须手动完成，递归算法将具有通过堆栈框架进行簿记的隐式方法。
您的方法
让我们看一下您提供的代码。它使我难以理解您正在努力实现的目标。例如，在最内层循环中的语句遍历col：
matrixFirstRowValues[row + (matrixSize - i)] = matrix[1][col + (matrixSize - i)];
只要最内层循环中的col发生变化，row和i都是固定的，所以您正在（显然）从matrix的第二行分配和重新分配给matrixFirstRowValues的同一条目]。不仅如此，您还可以从超出列范围的索引范围(matrixSize-i) .. (2*matrixSize - (i+1))进行赋值，除非i == matrixSize，这仅适用于i的第一个值。
正如我之前提到的，最后，您得到的不是仅一个2×2矩阵，而是n!/2。
正在复制第i行和第j列之外的副本
查看删除了第i行和第j列的矩阵，最后得到四个子矩阵（其中一些可能为空）。限制自己沿第一行扩展，然后您只需要处理两个子矩阵（其中一些可能仍然是空的）。您可以使用两个循环，一个循环用于第j列左侧和右边的矩阵-或者，如上一个答案中所建议-选择使用j跳过第continue列以循环循环而不更新目标列索引。如果col标记要删除的当前列（当前行始终为0），则在所有行上迭代r，并在所有列上迭代c，并在c == col处将列循环分成两段。假设目标矩阵称为minor，则它看起来像这样：
// expand along first row for(col = 0; col < matrix_size; col++) { // copy into minor matrix, left side then right side for(r = 1; r < matrix_size; r++) { for(c = 0; c < col; c++) { minor[r-1][c] = matrix[r][c]; } for(c = col+1; c < matrix_size; c++) { minor[r-1][c-1] = matrix[r][c]; } } // use "minor" matrix at this point to calculte // its determinant }索引移位
r-1是由于删除了第一行。
完整的递归拉普拉斯展开式
正如我之前提到的那样，行列式的拉普拉斯展开自然适合于递归算法。我将对您的设置进行一些更改，我将不使用堆栈分配的可变长度数组，而是使用堆分配的内存。由于扩展（如果不重新使用该空间）具有指数空间要求，因此对于中等大小的矩阵，堆栈可能已经很快耗尽。因此，我将需要一个附加参数来通过我称为is_valid的intent out参数报告回内存分配失败。
您将认识到上面的矩阵复制过程，它的名称略有不同，并且还有一个额外的指针取消引用，因为我在堆上使用n×n矩阵进行操作。我希望它不会导致过多的混乱。
#include <stdio.h> #include <stdlib.h> #define SQR(x) ((x)*(x)) int laplace_det(int matrix_size, const int (*mat)[][matrix_size], int *is_valid) { // base cases if(matrix_size == 1) return (*mat)[0][0]; if(matrix_size == 2) return (*mat)[0][0] * (*mat)[1][1] - (*mat)[1][0] * (*mat)[0][1]; // recusive case, matrix_size > 2 // expansion indiscriminately along the first row // // minor matrix with i-th row and j-th column // removed for the purpose of calculating // the minor. // r, c row and column index variables // col current column in expansion // d determinant accumulator // int r, c, col, d = 0; int (*minor)[matrix_size-1][matrix_size-1] = calloc(SQR(matrix_size-1), sizeof(int)); if(!minor) { *is_valid = 0; return 0; } // expand along first row for(col = 0; col < matrix_size; col++) { // copy into minor matrix, left side then right side for(r = 1; r < matrix_size; r++) { for(c = 0; c < col; c++) { (*minor)[r-1][c] = (*mat)[r][c]; } for(c = col+1; c < matrix_size; c++) { (*minor)[r-1][c-1] = (*mat)[r][c]; } } // calculate minor int temp_d = laplace_det(matrix_size-1, minor, is_valid); if(!is_valid) { free(minor); return 0; } d += (col & 1 ? -1 : 1) * (*mat)[0][col] * temp_d; } // free resources free(minor); return d; }示例驱动程序：
int main(void) { int is_valid = 1; int matrix[3][3] = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} }; int det_m = laplace_det(3, &matrix, &is_valid); if(is_valid) { printf("determinant %d\n", det_m); } }迭代方法
如果要迭代地执行相同的操作，则需要为所有较小尺寸的n-1子矩阵提供空间。如递归情况所示，您可以为same大小的所有子矩阵重用相同的空间，但是不能将空间用于较小大小的矩阵，因为每个矩阵都必须生成所有大小较小的子矩阵，而每个子矩阵必须生成较小的子矩阵。每列。
由于矩阵的原始大小是未知的，因此很难以一般方式遍历所有这些矩阵，并且需要大量记账，在递归的情况下，我们免费获得这些值在其各自的堆栈帧中。但是我想将当前的列选择器保持在大小为matrixSize的数组以及指向子矩阵的指针的数组中，就可以迭代地重写它。