Wyznaczanie wyznacznika macierzy rekurencyjnie
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zarejestruj się!

Wyznaczanie wyznacznika macierzy rekurencyjnie

AutorWiadomość
Temat założony przez niniejszego użytkownika
Wyznaczanie wyznacznika macierzy rekurencyjnie
» 2019-11-23 11:03:48
Witam,
Próbuję napisać rekurencyjny program określajacy wyznacznik macierzy. Mam takie coś
C/C++
#include <iostream>

const int N = 6;

int wyzn( int tab[ N ][ N ], int pos = 0, unsigned skiprows = 0 ) {
    if( pos == N - 2 ) { //obliczanie wyznacznika macierzy kwadratowej
        int s1[ 2 ], s2[ 2 ];
        bool s1done = false;
        for( unsigned i = 0; i < N; i++ ) {
            if( skiprows &( 1 << i ) ) //jeśli dany wiersz ma być pominięty
                 continue;
            else {
                if( s1done ) {
                    s2[ 0 ] = tab[ i ][ N - 2 ];
                    s2[ 1 ] = tab[ i ][ N - 1 ];
                    break;
                }
                else {
                    s1[ 0 ] = tab[ i ][ N - 2 ]; //pierwszy napotkany wiersz
                    s1[ 1 ] = tab[ i ][ N - 1 ];
                    s1done = true;
                }
            }
        }
        return s1[ 0 ] * s2[ 1 ] - s1[ 1 ] * s2[ 0 ];
    }
    int sum = 0;
    for( unsigned i = 0; i < N; i++ ) {
        if(( skiprows &( 0x01 << i ) ) == 0 ) {
            int r = tab[ i ][ pos ] * wyzn( tab, pos + 1, skiprows |( 1 << i ) ); //element o indeksie i, pos * minor mu odpowiadajcy;
            if(( i + 1 ) % 2 != 0 ) // jeśli i+j jest nieparzyste - wynik przeciwny, relatywnie do poczatku tablicy numer kolumny jest zawsze rowny 1
                 r *= - 1;
           
            sum += r;
        }
    }
    return sum;
}

int maci[ N ][ N ] = {
    { 1, 2, 4, 5, 6, 3 },
    { 5, - 2, 1, 6, 2, 1 },
    { 9, - 4, 2, 7, 9, 4 },
    { 0, 2, 4, 5, 2, 5 },
    { 9, 4, 2, 5, 9, 2 },
    { 2, 4, 5, 2, 1, - 7 }
};

int main() {
    std::cout << wyzn( maci ) << std::endl;
}
Niestety, program nie zwraca poprawnej wartości. Działa on tak, że wykreśla po każdym elemencie z 1-wszej kolumny i liczy wyznacznik macierzy bez tej kolumny i bez tego wiersza.
Zawsze wykreślana jest pierwsza kolumna, a numer aktualnie wykreślanej kolumny jest określony w zmiennej pos. Skiprows to maska bitowa zawierająca indeksy wykreślonych wierszy.
Jeśli rozmiar otrzymanej macierzy jest równy 2, to jej wyznacznik jest liczony ze wzoru.

Niestety, program zwraca złą wartość, nie mam pojęcia dlaczego, szukam od dwóch godzin i nie mogę znaleźć, może ktoś rzuci okiem?
P-175646
» 2019-11-23 15:46:57
Próbowałeś wypisywać macierze i ich wyznaczniki? Sprawdzając z teorią wyniki pośrednie poszłoby szybciej niż 2h bez rezultatu.

C/C++
if(( i + 1 ) % 2 != 0 ) // jeśli i+j jest nieparzyste - wynik przeciwny, relatywnie do poczatku tablicy numer kolumny jest zawsze rowny 1
Więc i też powinno być równe 1 dla pierwszego rzędu.
P-175647
Temat założony przez niniejszego użytkownika
» 2019-11-23 19:54:04
Zmieniłem i+1 na zwykłe i - bo rzędy są liczone od zera - więc +1 na każdy rząd, i pierwsza kolumna - więc +1. Robię modulo dwa, więc dwójki nie mają znaczenia - niestety błąd wciąż ten sam
P-175648
» 2019-11-23 20:23:28
Ta sama linia. i numeruje wiersze razem z pominiętymi.
P-175649
Temat założony przez niniejszego użytkownika
» 2019-11-25 00:19:02
dzięki @pekfos, poprawka załatwiła sprawę :)
C/C++
#include <iostream>

const int N = 6;

int wyzn( int tab[ N ][ N ], int pos = 0, unsigned skiprows = 0 ) {
    if( pos == N - 2 ) { //obliczanie wyznacznika macierzy kwadratowej
        int s1[ 2 ], s2[ 2 ];
        bool s1done = false;
        for( unsigned i = 0; i < N; i++ ) {
            if( skiprows &( 1 << i ) ) //jeśli dany wiersz ma być pominięty
                 continue;
            else {
                if( s1done ) {
                    s2[ 0 ] = tab[ i ][ N - 2 ];
                    s2[ 1 ] = tab[ i ][ N - 1 ];
                    break;
                }
                else {
                    s1[ 0 ] = tab[ i ][ N - 2 ]; //pierwszy napotkany wiersz
                    s1[ 1 ] = tab[ i ][ N - 1 ];
                    s1done = true;
                }
            }
        }
        return s1[ 0 ] * s2[ 1 ] - s1[ 1 ] * s2[ 0 ];
    }
    int sum = 0;
    int absi = 0;
    for( unsigned i = 0; i < N; i++ ) {
        if(( skiprows &( 1 << i ) ) ) {
            continue;
        }
        int r = tab[ i ][ pos ] * wyzn( tab, pos + 1, skiprows |( 1 << i ) );
        if(( absi ) % 2 != 0 )
             r *= - 1;
       
        sum += r;
        absi++;
    }
    return sum;
}

int maci[ N ][ N ] = {
    { 1, 2, 4, 5, 6, 3 },
    { 5, - 2, 1, 6, 2, 1 },
    { 9, - 4, 2, 7, 9, 4 },
    { 0, 2, 4, 5, 2, 5 },
    { 9, 4, 2, 5, 9, 2 },
    { 2, 4, 5, 2, 1, - 7 }
};

int main() {
    std::cout << wyzn( maci ) << std::endl;
}
P-175659
« 1 »
 Strona 1 z 1