Cod sursa(job #1877661)

Utilizator andrei.arnautuAndi Arnautu andrei.arnautu Data 13 februarie 2017 17:26:19
Problema Algoritmul lui Gauss Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.55 kb
/**
  *  Worg
  */
#include <cstdio>
#include <algorithm>

FILE *fin = freopen("gauss.in", "r", stdin);
FILE *fout = freopen("gauss.out", "w", stdout);

const int MAX_N = 1 + 300 + 1;
const double eps = 1e-10;

/*-------- Input data --------*/
int N, M;
double A[MAX_N][MAX_N];
/*-------- Gauss --------*/
double x[MAX_N];
/*-------- --------*/

void ReadInput() {
    scanf("%d%d", &N, &M);
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= M + 1; j++) {
            scanf("%lf", &A[i][j]);
        }
    }
}

bool GaussAlgorithm() {
    int i = 1, j = 1;

    while(i <= N && j <= M) {
        //  Cautam o linie cu A[line][j] != 0. EPS are rolul de a elimina greselile de calcul
        int line;
        for(line = i; line <= N; ++line) {
            if(A[line][j] < -eps || A[line][j] > eps) {
                break;
            }
        }

        if(line != N + 1) {  //  Avem o linie ok
            for(int col = 1; col <= M + 1; col ++) {  //  Interschimbam coloanele
                std::swap(A[i][col], A[line][col]);
            }
            for(int col = j + 1; col <= M + 1; col++) {  //  Impartim toate elementele de pe linia curenta la A[i][j], acesta devenind 1
                A[i][col] /= A[i][j];
            }
            A[i][j] = 1;

            for(line = i + 1; line <= N; line++) {      //  Toate elementele de pe linia line si coloana <= j devin 0
                for(int col = j + 1; col <= M + 1; col++) {
                    A[line][col] -= A[line][j] * A[i][col];
                }
                A[line][j] = 0;
            }

            ++i; ++j;
        } else {  //  Necunoscuta libera
            ++j;
        }
    }

    //  Obtinem vectorul cu necunoscute in ordine inversa
    for(int i = N; i >= 1; i--) {
        for(int j = 1; j <= M + 1; j++) {
            if(A[i][j] < -eps || A[i][j] > eps) {
                if(j == M + 1) {  //  Daca singura valoare nenula de pe linia i este rezultatul, atunci sistemul nu are solutie
                    return false;
                }

                x[j] = A[i][M + 1];
                for(int col = j + 1; col <= M; col++) {
                    x[j] -= x[col] * A[i][col];
                }

                break;
            }
        }
    }

    return true;
}

void WriteOutput() {
    for(int i = 1; i <= M; i++) {
        printf("%.10f ", x[i]);
    }
}

int main() {
    ReadInput();
    if(GaussAlgorithm()) {
        WriteOutput();
    } else {
        printf("Imposibil\n");
    }
    return 0;
}