Определитель матрицы по гауссовскому исключению Переполнение стека
Я пытался найти код для определения определителя квадратной матрицы, и я наткнулся на этот код.
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]); операция?
Заранее спасибо.
Решение
В вашем коде есть странная логика, объясняющая тот факт, что вы выполняете вычисления с использованием целочисленной арифметики.
Скажем, у вас есть матрица 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;
}
Другие решения