0

我试图找到找到方阵行列式的代码，我遇到了这个代码。

    int det(vector<vector<int> > mat) {
        int n = mat.size();


        for(int col = 0; col < n; ++col) {
            bool found = false;
            for(int row = col; row < n; ++row) {
                if(mat[row][col]) {
                    mat[row].swap(mat[col]);
                    found = true;
                    break;
                }
            }
            if(!found) {
                return 0;
            }
            for(int row = col + 1; row < n; ++row) {
                while(true) {
                    int del = mat[row][col] / mat[col][col];
                    for (int j = col; j < n; ++j) {
                        mat[row][j] -= del * mat[col][j];
                    }
                    if (mat[row][col] == 0)
                        break;
                    else
                        mat[row].swap(mat[col]);
                }
            }
        }

        li res = 1;

        for(int i = 0; i < n; ++i) {
            res *= mat[i][i];
        }
        return abs(res);
    }

但我无法理解第 20-29 行，即从另一行的多个行中减去行的位置。我的意思是为什么这里需要while循环？当我减去 quotient*dividend 时，它应该始终为 0 ，对吗？所以我认为它应该只是一次迭代。那么，为什么我们需要执行这个mat[row].swap(mat[col]);操作呢？提前致谢。

4

1 回答 1

1

您的代码中有一些奇怪的逻辑来解释您使用整数算术执行计算的事实。

假设您有一个 3x3 矩阵，其中前两行是：

4 6 5
1 2 3

当你计算del和col=0时row=1，你会得到：

del = 1/4 = 0

这样，当您计算时：

mat[row][j] -= del * mat[col][j];

mat[row][j]根本没有改变。

为了解决这个问题，您交换了行。现在前两行是：

1 2 3
4 6 5

像这样交换行后，del值为4/1 = 4。现在这一行：

mat[row][j] -= del * mat[col][j];

确实有所作为。的值mat[1][0]最终为零，这是您所需要的。所以你跳出while循环。

这是您的函数的检测版本，它产生大量调试输出，带有打印矩阵的辅助函数和测试代码的主函数。

#include <iostream>
#include <vector>
#include <stdlib.h>

using namespace std;

void printMatrix(vector<vector<int> > const& mat)
{
   int n = mat.size();
   for(int row = 0; row < n; ++row) {
      for(int col = 0; col < n; ++col) {
         cout << mat[row][col] << " ";
      }
      cout << "\n";
   }
   cout << "\n";
}

int det(vector<vector<int> > mat) {
   int n = mat.size();

   for(int col = 0; col < n; ++col) {
      cout << "Column: " << col << "\n";
      printMatrix(mat);
      bool found = false;
      for(int row = col; row < n; ++row) {
         if(mat[row][col]) {
            cout << "Got non-zero value for row " << row << " and col " << col << "\n";
            if ( row != col )
            {
               cout << "(1) Swapping rows " << col << " and " << row << "\n";
               mat[row].swap(mat[col]);
               printMatrix(mat);
            }
            else
            {
               cout << "Not swapping rows\n";
            }
            found = true;
            break;
         }
      }

      if(!found) {
         cout << "Did not find a non-zero row. Column: " << col << "\n";
         return 0;
      }

      for(int row = col + 1; row < n; ++row) {
         while(true) {
            int del = mat[row][col] / mat[col][col];
            cout << "del: " << del << "\n";
            for (int j = col; j < n; ++j) {
               mat[row][j] -= del * mat[col][j];
            }
            if (mat[row][col] == 0)
            {
               break;
            }
            else
            {
               cout << "(2) Swapping rows " << col << " and " << row << "\n";
               mat[row].swap(mat[col]);
               printMatrix(mat);
            }
         }
      }
   }

   printMatrix(mat);
   long res = 1;

   for(int i = 0; i < n; ++i) {
      res *= mat[i][i];
   }
   return abs(res);
}

int main()
{
   vector<vector<int> > mat = { {4, 6, 5}, {1, 2, 3}, {8, 10, 9} };
   int r = det(mat);
   cout << "Determinant: " << r << endl;
   return 0;
}
于 2014-09-03T18:18:21.363 回答