Cod sursa(job #2791042)

Utilizator popashtefan10Popa Stefan popashtefan10 Data 29 octombrie 2021 23:55:31
Problema Algoritmul lui Gauss Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 6.86 kb
#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

class Ecuatie {

private:
    int nr_necunoscute;
    vector<double> coeficienti;

public:
    Ecuatie();
    Ecuatie(int _nr_necunoscute);
    Ecuatie(int _nr_necunoscute, double _coeficienti[]);
    ~Ecuatie();

    int get_nr_necunoscute();
    int get_rezultat();

    Ecuatie operator * (double k);
    Ecuatie operator *= (double k);
    Ecuatie operator += (Ecuatie rhs);
    double operator [] (int i); // Intoarce al i-lea coeficient

    void print();
};

Ecuatie::Ecuatie() {
    nr_necunoscute = 0;
}

Ecuatie::Ecuatie(int _nr_necunoscute) : nr_necunoscute(_nr_necunoscute) {
    coeficienti.resize(nr_necunoscute + 1, 0);
}

Ecuatie::Ecuatie(int _nr_necunoscute, double _coeficienti[]) : nr_necunoscute(_nr_necunoscute) {
    coeficienti.resize(nr_necunoscute + 1, 0);
    for(int i = 0; i <= nr_necunoscute; i++) 
        coeficienti[i] = _coeficienti[i];
}

Ecuatie::~Ecuatie() {}

int Ecuatie::get_nr_necunoscute() {
    return nr_necunoscute;
}

int Ecuatie::get_rezultat() {
    return coeficienti[nr_necunoscute];
}

Ecuatie Ecuatie::operator * (double k) {
    Ecuatie rez(nr_necunoscute);

    for(int i = 0; i <= nr_necunoscute; i++)
        rez.coeficienti[i] = coeficienti[i] * k;

    return rez;
}

Ecuatie Ecuatie::operator *= (double k) {
    for(double &coeficient: coeficienti)
        coeficient *= k;

    return *this;
}

Ecuatie Ecuatie::operator += (Ecuatie rhs) {
    assert(rhs.nr_necunoscute == nr_necunoscute);

    for(int i = 0; i <= nr_necunoscute; i++)
        coeficienti[i] += rhs.coeficienti[i];

    return *this;
}

double Ecuatie::operator [] (int poz) {
    assert(poz <= nr_necunoscute + 1);
    return coeficienti[poz];
}

void Ecuatie::print() {
    for(double coeficient: coeficienti)
        printf("%f ", coeficient);
    printf("\n");
}

class Gauss {

private:
    int nr_ecuatii;
    int nr_necunoscute;
    int last_added;
    bool se_poate_rezolva;

    vector<Ecuatie> ecuatii;
    vector<double> necunoscute; // Valorile necunoscutelor
    vector<int> pivoti; // Pozitiile pivotilor
    vector<bool> libera; // Daca o variabila este libera sau nu

    // Intoarce linia pe care se afla primul element nenul de pe coloana, cu linia >= decat linia data ca parametru
    int get_pivot(int linie, int coloana);
    // Inmulteste ecuatia cu o constanta a.i. pivotul sa devina 1
    void reduce_pivot(int linie, int coloana);
    // Reduce elementul de sub pivot din ecuatia ecuatie cu pivotul din ecuatia ecuatie_pivot
    void reduce_ecuatie(int ecuatie, int ecuatie_pivot, int pivot_coloana);

public:
    Gauss(int _nr_ecuatii, int _nr_necunoscute);
    ~Gauss();

    // Adauga o ecuatie la lista de ecuatii
    void adauga_ecuatie(Ecuatie ecuatie);
    void afla_necunonscute();
    void solve();
    void print_necunoscute();

    void print();
};

Gauss::Gauss(int _nr_ecuatii, int _nr_necunoscute) :
    nr_ecuatii(_nr_ecuatii), nr_necunoscute(_nr_necunoscute), last_added(-1) {
    ecuatii.resize(nr_ecuatii);
    necunoscute.resize(nr_necunoscute, 0);
    // Initial fiecare pivot are valoarea m + 1
    // In final daca vreun  pivot ramane asa inseamna ca ecuatia e de forma
    // 0*x1 + 0*x2 + ... + 0*xm = b
    pivoti.resize(nr_ecuatii, nr_necunoscute);
    // Initial presupunem ca toate necunoscutele sunt variabile libere
    libera.resize(nr_necunoscute, true);

    se_poate_rezolva = true;
}

Gauss::~Gauss() {}

int Gauss::get_pivot(int linie, int coloana) {
    for(int ecuatie_idx = linie; ecuatie_idx < nr_ecuatii; ecuatie_idx++)
        if(ecuatii[ecuatie_idx][coloana] != 0)
            return ecuatie_idx;
    return -1; // Nu am gasit niciun pivot
}

void Gauss::reduce_pivot(int linie, int coloana) {
    ecuatii[linie] *= 1.0 / ecuatii[linie][coloana];
}

void Gauss::adauga_ecuatie(Ecuatie ecuatie) {
    last_added++;
    assert(last_added < nr_ecuatii);
    assert(ecuatie.get_nr_necunoscute() == nr_necunoscute);
    ecuatii[last_added] = ecuatie;
}

void Gauss::reduce_ecuatie(int ecuatie_idx, int ecuatie_pivot_idx, int pivot_coloana) {
    double k = -ecuatii[ecuatie_idx][pivot_coloana] / ecuatii[ecuatie_pivot_idx][pivot_coloana];
    ecuatii[ecuatie_idx] += ecuatii[ecuatie_pivot_idx] * k;
}

void Gauss::afla_necunonscute() {
    for(int linie = nr_ecuatii - 1; linie >= 0; linie--)
        if(pivoti[linie] == nr_necunoscute) {
            // Avem ecuatia 0*x1 + ... + 0*xm = b
            if(ecuatii[linie].get_rezultat() != 0) {
                se_poate_rezolva = false;
                break;
            }
        }
        else {
            int necunoscuta = pivoti[linie];
            necunoscute[necunoscuta] = ecuatii[linie].get_rezultat();
            libera[necunoscuta] = false;

            // calculez valoarea necunoscutei
            for(int necunoscuta_gasita = nr_necunoscute - 1; necunoscuta_gasita > necunoscuta; necunoscuta_gasita--) {
                if(libera[necunoscuta_gasita]) { // fixam variabila libera daca e cazul
                    necunoscute[necunoscuta_gasita] = 0;
                    libera[necunoscuta_gasita] = false;
                }
                necunoscute[necunoscuta] -= ecuatii[linie][necunoscuta_gasita] * necunoscute[necunoscuta_gasita];
            }
        }
}

void Gauss::print_necunoscute() {
    if(se_poate_rezolva)
        for(int i = 0; i < nr_necunoscute; i++)
            printf("%.10f ", necunoscute[i]);
    else
        printf("Imposibil");
}

void Gauss::print() {
    for(int i = 0; i < nr_ecuatii; i++)
        ecuatii[i].print();
    printf("\n");
}

void Gauss::solve() {
    int linie = 0;
    int coloana = 0;

    while(linie < nr_ecuatii && coloana < nr_necunoscute) {
        int pivot_linie = get_pivot(linie, coloana);

        if(pivot_linie == -1) { // Nu am gasit pivot
            libera[coloana] = true;
            coloana++;
        }
        else {
            if(pivot_linie != linie) // Aduc ecuatia cu pivotul pe linia curenta
                swap(ecuatii[linie], ecuatii[pivot_linie]);
            pivoti[linie] = coloana;

            reduce_pivot(linie, coloana);
            for(int linie2 = linie + 1; linie2 < nr_ecuatii; linie2++)
                reduce_ecuatie(linie2, linie, coloana);

            linie++;
            coloana++;
        }
    }

    afla_necunonscute();
}

double coeficienti[305];

int main() {
    freopen("gauss.in", "r", stdin);
    freopen("gauss.out", "w", stdout);

    int n, m;
    scanf("%d %d", &n, &m);
    Gauss gauss(n, m);

    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < m + 1; j++)
            scanf("%lf", &coeficienti[j]);
        gauss.adauga_ecuatie(Ecuatie(m, coeficienti));
    }

    gauss.solve();
    gauss.print_necunoscute();

    return 0;
}