c++ - 使用迭代方法计算矩阵的行列式

Question

我编写了 C++ 代码，使用递归方法计算矩阵的行列式。

现在，我想使用迭代方法重写该递归方法。但我无法弄清楚如何实现这一目标。

问题是:具体的递归方法(int Determinant(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;
}

我知道这不是计算大型矩阵行列式的最明智方法。我可以使用矩阵变换简化矩阵并显着加快计算速度。

尽管如有任何帮助或提示，我们将不胜感激。

Answer 1

你应该总共总结N个!乘积项，每个都是唯一的乘积 N 个元素，它们都不在同一行或同一列:按行顺序排序，列索引是范围 [1··N) 的排列，奇数排列取反。您可以使用 std::next_permutation 计算每次迭代的排列和反转符号。