Вычислить определитель матрицы с помощью итерационного метода
Я написал C ++ коды, которые вычисляют определитель матрицы, используя рекурсивный метод.
Теперь я хотел бы переписать этот рекурсивный метод с использованием итеративного метода. Но я не могу понять, как этого добиться.
Вопрос в том: Как переписать конкретный рекурсивный метод (Определитель int (int *&, const int)) в итерационный метод?
Вот мои C ++ коды:
// Determinant C++
#include <iostream>
#include <ctime>
using namespace std;
void RandInitArray(int *, const int, int = 0, int = 20);
void Display(int *, const int);
int CalculateDeterminant(int *&, const int);
int Determinant(int *&, const int);
int main()
{
start = clock();
srand((unsigned int)time(NULL));
int N = 12; // Size of matrix
int * S = new int[N * N];
int a(-10), b(10), det;
RandInitArray(S, N, a, b);
cout.precision(4);
Display(S, N);
det = CalculateDeterminant(S, N);
cout << "\nDeterminant = " << det << "\n\n";
cin.get();
return 0;
}
void RandInitArray(int * arr, const int N, int a, int b)
{
for (int i = 0; i < N * N; i++)
arr[i] = rand() % (b - a + 1) + a;
}
void Display(int *arr, const int N)
{
for (int i = 0; i < N * N; i++)
cout << arr[i] << ((i + 1) % N ? "\t" : "\n");
}
int CalculateDeterminant(int *& S, const int N)
{
int rez;
if (N < 1)
cout << "Size of matrix must be positive\n";
else if (N == 1)
rez = *S;
else if (N == 2)
rez = S[0] * S[3] - S[1] * S[2];
else if (N == 3)
rez = S[0] * S[4] * S[8] + S[1] * S[5] * S[6] + S[2] * S[3] * S[7] -
S[2] * S[4] * S[6] - S[1] * S[3] * S[8] - S[0] * S[5] * S[7];
else
rez = Determinant(S, N);
return rez;
}
int Determinant(int *& S, const int N)
{
int sign(1), det(0), res, M(N - 1);
int * _S;
for (int k = 0; k < N; k++)
{
_S = new int[M * M];
int ind = 0;
for (int i = N; i < N * N; i++)
{
if (i % N != k)
_S[ind++] = S[i];
}
if (M == 3)
{
res = S[k] == 0 ? 0 : _S[0] * _S[4] * _S[8] + _S[1] * _S[5] * _S[6] + _S[2] * _S[3] * _S[7] -
_S[2] * _S[4] * _S[6] - _S[1] * _S[3] * _S[8] - _S[0] * _S[5] * _S[7];
delete[] _S;
}
else
res = S[k] == 0 ? 0 : Determinant(_S, N - 1);
det += S[k] * sign * res;
sign *= -1;
}
delete[] S;
return det;
}
Я знаю, что это не самый умный способ вычислить определитель большой матрицы. Я могу упростить матрицу, используя матричные преобразования, и значительно ускорить вычисления.
Несмотря на это, любая помощь или подсказка будет принята с благодарностью.
Решение
Используя два факта о детерминантах, приведенных ниже, вы можете вычислить детерминант без какой-либо рекурсии, а также это значительно быстрее для больших матриц.
1) Добавление скалярного кратного одной строки в другую не меняет определителя.
2) Чередование двух строк сводит на нет определитель
Это реализация с вашими кодами:
// Determinant C++
#include <iostream>
#include <stdio.h>
#include <ctime>
using namespace std;
void RandInitArray(int *, const int, int = 0, int = 20);
void Display(int *, const int);
int CalculateDeterminant(int *&, const int);
int Determinant(int *&, const int);
long long DeterminantIterative(int *&, const int);
int ResolveRows(int **, const int, int, int);
void Display(int **, const int);
bool RECURSIVE = true;
bool ShowCalculation = true;
int main()
{
srand((unsigned int)time(NULL));
int N = 6; // Size of matrix
int * S = new int[N * N];
int a(-10), b(10), det;
RandInitArray(S, N, a, b);
if (N < 12)
{
cout << " ======== Recursive ========\n\n";
Display(S, N);
det = CalculateDeterminant(S, N);
cout << "\nDeterminant = " << det << "\n\n";
}
cout << " ======== Iterative ========\n";
RECURSIVE = false;
det = CalculateDeterminant(S, N);
cout << "\nDeterminant = " << det << "\n\n";
cin.get();
return 0;
}
void RandInitArray(int * arr, const int N, int a, int b)
{
for (int i = 0; i < N * N; i++)
arr[i] = rand() % (b - a + 1) + a;
}
void Display(int *arr, const int N)
{
for (int i = 0; i < N * N; i++)
cout << arr[i] << ((i + 1) % N ? "\t" : "\n");
}
int CalculateDeterminant(int *& S, const int N)
{
int rez;
if (N < 1)
cout << "Size of matrix must be positive\n";
else if (N == 1)
rez = *S;
else if (N == 2)
rez = S[0] * S[3] - S[1] * S[2];
else if (N == 3)
rez = S[0] * S[4] * S[8] + S[1] * S[5] * S[6] + S[2] * S[3] * S[7] -
S[2] * S[4] * S[6] - S[1] * S[3] * S[8] - S[0] * S[5] * S[7];
else
rez = RECURSIVE ? Determinant(S, N) : (int)DeterminantIterative(S, N);
return rez;
}
int Determinant(int *& S, const int N)
{
int sign(1), det(0), res, M(N - 1);
int * _S;
for (int k = 0; k < N; k++)
{
_S = new int[M * M];
int ind = 0;
for (int i = N; i < N * N; i++)
{
if (i % N != k)
_S[ind++] = S[i];
}
if (M == 3)
{
res = S[k] == 0 ? 0 : _S[0] * _S[4] * _S[8] + _S[1] * _S[5] * _S[6] + _S[2] * _S[3] * _S[7] -
_S[2] * _S[4] * _S[6] - _S[1] * _S[3] * _S[8] - _S[0] * _S[5] * _S[7];
delete[] _S;
}
else
res = S[k] == 0 ? 0 : Determinant(_S, N - 1);det += S[k] * sign * res;
sign *= -1;
}
//delete[] S;
return det;
}
long long DeterminantIterative(int *& S, const int N)
{
int ** M = new int*[N];
for (int i = 0; i < N; i++)
M[i] = new int[N];
for (int i = 0; i < N * N; i++)
M[i / N][i % N] = S[i];
cout << "\n\n Initial Matrix\n\n";
Display(M, N);
long determinant = 1;
for (int i = 0; i < N - 1; i++)
for (int j = i + 1; j < N; j++)
while (M[j][i] != 0)
{
determinant *= ResolveRows(M, N, i, j);
if (determinant == 0)
return 0;
}
for (int i = 0; i < N; i++)
determinant *= M[i][i];
for (int i = 0; i < N; i++)
delete[] M[i];
delete[] M;
delete[] S;
return determinant;
}
int ResolveRows(int ** M, const int N, int f, int s)
{
if (ShowCalculation)
printf("\n\n f[%d][%d] = %d,\ts[%d][%d] = %d \n",
f, f, M[f][f], s, f, M[s][f] );
int sign = 1;
int NonZeroRowIndex = s;
while (M[f][f] == 0)
{
sign *= -1;
if (ShowCalculation)
printf(" Swap Row[%d] and Row[%d] and change the sign\n", f, s);
int * tmp = M[NonZeroRowIndex];
M[NonZeroRowIndex] = M[f];
M[f] = tmp;
NonZeroRowIndex++;
if (M[f][f] != 0)
return sign;
if (NonZeroRowIndex == N && M[f][f] == 0)
return 0;
}
if (fabs(M[f][f]) > fabs(M[s][f]))
{
sign *= -1;
int * tmp = M[s];
M[s] = M[f];
M[f] = tmp;
if (ShowCalculation)
printf(" Swap Row[%d] and Row[%d] and change the sign\n", f, s);
}
int k = M[f][f] == 0 ? 1 : -M[s][f] / M[f][f];
if (ShowCalculation)
printf(" Multiply Row[%d] by %d and add to the Row[%d]\n\n", f, k, s);
for (int i = 0; i < N; i++)
M[s][i] += k * M[f][i];
if (ShowCalculation)
{
Display(M, N);
cin.get();
}
return sign;
}
void Display(int ** M, const int N)
{
cout << " ";
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
cout << M[i][j] << (j < N - 1 ? "\t" : "\n ");
}
Другие решения
Вы должны подвести итог всего N! слагаемые произведения, каждый из которых является уникальным произведением. N элементов, ни один из которых не находится ни в одной строке, ни в столбце: при сортировке по порядку строк индексы столбца являются перестановками диапазона [1 · N], причем нечетные перестановки сводятся на нет. Ты можешь использовать std::next_permutation рассчитать перестановку и инвертировать знак за итерацию.