Cod sursa(job #2783055)

Utilizator NeacsuMihaiNeacsu Mihai NeacsuMihai Data 13 octombrie 2021 18:24:57
Problema Algoritmul lui Gauss Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.99 kb
#include <iostream>
#include <fstream>
#include <iomanip> //input output manipulator

#define NMAX 300
#define MMAX 300

using namespace std;

ifstream fin ("gauss.in");
ofstream fout ("gauss.out");

int N, M;
long double v[NMAX + 1][MMAX + 2];
long double eps = 1e-8;
long double raspuns[NMAX + 1];
int first[NMAX + 1];

void read(){
    fin >> N >> M;

    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M + 1; j++){
            fin >> v[i][j];
        }
    }
}

int esteZero(long double val){
    return (-eps < val && val < eps);
}

void simplificLinia(int k, long double factor, int lin){
    //k -= factor * lin

    for(int j = 1; j <= M + 1; j++){
        v[k][j] -= factor * v[lin][j];
    }
}

void solve(){
    for(int lin = 1; lin <= N; lin++){
        int firstColNenul = 1;
        while( firstColNenul <= M + 1 && esteZero(v[lin][firstColNenul]) ){
            firstColNenul++;
        }

        if(firstColNenul == M + 1){
            fout << "Imposibil";
            /*
                Pentru ca am 0 + 0 + ... + 0 = x
                unde x este nenul
            */
            return;
        }

        if(firstColNenul != M + 2){
            /*
                Adica daca nu am toata linia plina de zero-uri
            */

            first[lin] = firstColNenul;

            /*
                Acum vreau ca pe coloana firstColNenul sa am 0-uri peste tot, mai putin pe linia 'lin'
                asa ca iau fiecare linie K, si simplific cu factor * 'lin'
            */
            for(int k = 1; k <= N; k++){
                if(k != lin){
                    //adica nu o simplific pe cea curenta
                    /*
                        Cand simplific linia K cu 'factor' * 'lin'
                        fac pt fiecare element din linie v[K][ct] -= factor * v[lin][ct]
                    */
                    /*
                        Factorul il aleg astfel incat v[k][ first[lin] ] sa devina 0
                        adica
                        v[k][ first[lin] ] = v[k][ first[lin] ] - factor * v[lin][ first[lin] ] = 0
                        => factor = v[k][ first[lin] ] / v[lin][ first[lin] ]
                    */
                    long double factor = v[k][ first[lin] ] / v[lin][ first[lin] ];
                    simplificLinia(k, factor, lin);
                }
            }

        }
    }

    for(int i = 1; i <= N; i++){
        if(first[i] != 0){
            raspuns[ first[i] ] = v[i][M + 1] / v[i][ first[i] ]; //adica asta e singurul coeficient ramas pe acea linie
            //deci 0 + 0 + 0 + ... + 0 + coeficient_variabila * valoare_variabila + 0 + ... + 0 = v[i][M + 1];
            //unde coeficient_variabila = v[i][ first[i] ]
            //valoare_variabila = raspuns[ first[i] ]
        }
    }

    fout << setprecision(10) << fixed;
    for(int i = 1; i <= M; i++){
        fout << raspuns[i] << ' ';
    }
}

int main()
{
    read();
    solve();
    return 0;
}