高斯消元矩陣的行列式C++

Question

我試圖找到尋找方矩陣行列式的代碼，並且我遇到了這個代碼。

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循環？因爲我是 減去商*分紅，它應該總是0，對嗎？所以我認爲它應該只是一個迭代。那麼，爲什麼我們需要執行這個mat[row].swap(mat[col]);操作？ 在此先感謝。

Answer 1

您的代碼中存在一些奇怪的邏輯來說明您正在使用整數算術執行計算的事實。

假設你有一個3×3矩陣中的前兩行分別是：

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; 
}