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

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

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

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

- L_J

---

你认为所有这些代码都与问题相关吗？请创建一个最小的示例。 - DeiDei

@DeiDei 没错。只有 *int Determinant(int & S, const int N) - 这个方法是重要的。 - L_J

如何重写 - 不要重写，只需根据需要实现它。 - mentallurg

不建议使用(ptr, cnt)接口。建议您使用一对迭代器或使用特定的类（例如C++20中的span）。 - L. F.

Answer 1

你需要总结N！个乘积项，每个乘积项都是N个元素的唯一乘积，这些元素不驻留在同一行或列上：按行顺序排序，列索引是范围[1··N)的排列，奇排列被取反。您可以使用std::next_permutation计算排列并在每次迭代中反转符号。

- Red.Wave