矩阵行列式算法 C++

Question

我是新手程序员，我想找一种方法来求矩阵的行列式。我在网上找到了这段代码，但我不太理解其中的算法。我对于递归的基础没有问题，但是循环和主要过程我有点难以理解。非常感谢任何能够向我解释算法的人。

int determ(int a[MAX][MAX],int n) {
  int det=0, p, h, k, i, j, temp[MAX][MAX];
  if(n==1) {
    return a[0][0];
  } else if(n==2) {
    det=(a[0][0]*a[1][1]-a[0][1]*a[1][0]);
    return det;
  } else {
    for(p=0;p<n;p++) {
      h = 0;
      k = 0;
      for(i=1;i<n;i++) {
        for( j=0;j<n;j++) {
          if(j==p) {
            continue;
          }
          temp[h][k] = a[i][j];
          k++;
          if(k==n-1) {
            h++;
            k = 0;
          }
        }
      }
      det=det+a[0][p]*pow(-1,p)*determ(temp,n-1);
    }
    return det;
  }
}

- user3144334

---

它通过计算矩阵的子式来计算行列式。内部循环在temp中生成子式。此方法计算行列式的方式非常糟糕。 - Joker_vD

@user3144334，这里的子式都是去掉第一行得到的矩阵。如果要去掉第p列，你需要在从a复制元素到temp时跳过该列。其中，子式是指去掉某些行和列后剩余元素所组成的矩阵。 - Joker_vD

计算行列式的超指数复杂度，干得好...甚至使用pow(-1,p)一眼就能看出代码有多好... - Marc Glisse

Answer 1

这个算法使用分治法来解决问题（找到N*N矩阵的行列式）。

该算法使用递归模式，这是分治方法之一。通过注意到算法在第三个条件语句中调用自身，您可以了解到这一点。

每个递归算法都有一个退出条件，这是代码中的第一个if语句。它们还包含一个部分，这个部分是处理最方便的问题或主要大问题的原子问题的解决方案，而这些问题本来很难解决。原子问题或最分裂的问题可以轻松解决，就像您代码中的第二个if语句所展示的那样。在您的情况下，它实际上解决了2*2矩阵的行列式。

你需要理解并且有点具有挑战性的是代码中进行分割的部分（也是递归的！）。这部分拥有征服问题的关键。通过做一些回溯和数值例子，您可以找到答案。

det = det + a[0][p] * pow(-1,p) * determ(temp,n-1);

对于最终建议，请尝试一个3*3矩阵，它只需要一个分割线。祝你好运。

这本书是学习和理解算法的不错选择

- Novin Shahroudi

---

非常感谢。我只想问一下 continue 语句是做什么的？如果 j == p，那么你会直接跳过到 det=det+a[0][p]*pow(-1,p)*determ(temp,n-1); 还是其他什么操作？ - user3144334

@user3144334哦，你只是不知道continue的作用... for (...) { if (x) { continue; } b; c; }等同于for (...) { if (!x) { b; c; } }。 - Joker_vD

它将继续执行一次“for”循环。请查看此链接：http://www.cplusplus.com/doc/tutorial/control/ - continue可用于所有具有条件的语句：http://www.tutorialspoint.com/cplusplus/cpp_continue_statement.htm - Novin Shahroudi

Answer 2

#include <iostream>

using std::cin;
using std::cout;
using std::endl;

int **submatrix(int **matrix, unsigned int n, unsigned int x, unsigned int y) {
    int **submatrix = new int *[n - 1];
    int subi = 0;
    for (int i = 0; i < n; i++) {
        submatrix[subi] = new int[n - 1];
        int subj = 0;
        if (i == y) {
            continue;
        }
        for (int j = 0; j < n; j++) {
            if (j == x) {
                continue;
            }
            submatrix[subi][subj] = matrix[i][j];
            subj++;
        }
        subi++;
    }
    return submatrix;
}

int determinant(int **matrix, unsigned int n) {
    int det = 0;
    if (n == 2) {
        return matrix[0][0] * matrix[1][1] - matrix[1][0] * matrix[0][1];
    }
    for (int x = 0; x < n; ++x) {
        det += ((x % 2 == 0 ? 1 : -1) * matrix[0][x] * determinant(submatrix(matrix, n, x, 0), n - 1));
    }

    return det;
}

int main() {
    int n;
    cin >> n;
    int **matrix = new int *[n];
    for (int i = 0; i < n; ++i) {
        matrix[i] = new int[n];
        for (int j = 0; j < n; ++j) {
            cin >> matrix[i][j];
        }
    }

    cout << determinant(matrix, n);

    return 0;
}

- sav0I