Вычислить определитель матрицы с помощью итерационного метода - PullRequest
Новая
       50

Вычислить определитель матрицы с помощью итерационного метода

0 голосов
/ 10 июня 2018

Я написал 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;
}

Я знаю, что это не самый умный способ вычисления определителя большой матрицы.Я могу упростить матрицу, используя матричные преобразования, и значительно ускорить вычисления.

Несмотря на то, что любая помощь или подсказка будет принята с благодарностью.

Ответы [ 2 ]

0 голосов
/ 17 июня 2018

Вы должны суммировать в общей сложности N!слагаемые произведения, каждый из которых является уникальным произведением. N элементов, ни один из которых не находится ни в одной строке, ни в столбце: при сортировке по порядку строк индексы столбца являются перестановками диапазона [1 · N], причем нечетные перестановки сводятся на нет.Вы можете использовать std::next_permutation для вычисления перестановки и инвертировать знак за итерацию.

0 голосов
/ 16 июня 2018

Используя два факта о детерминантах, приведенных ниже, вы можете вычислить детерминант без какой-либо рекурсии, а также это значительно быстрее для больших матриц.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  ");
}
...