Cod sursa(job #1947931)

Utilizator andrei.arnautuAndi Arnautu andrei.arnautu Data 31 martie 2017 15:22:46
Problema Algoritmul lui Gauss Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.71 kb
/**
  *  Worg
  */
#include <cstdio>
#include <algorithm>

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

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

/*-------- Input data --------*/
int N, M;
double sys[kMaxN][kMaxN];  //  Sistemul
/*-------- Gaussian Elimination --------*/
double x[kMaxN];  //  Necunoscutele
/*-------- --------*/

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

bool OkGaussianElimination() {
    int i = 1, j = 1;
    while(i <= N && j <= M) {
        int line;
        for(line = i; line <= N; line ++) {  //  Cautam o linie pe care necunoscuta j are coeficient nenul
            if(sys[line][j] < -eps || eps < sys[line][j]) {
                break;
            }
        }

        if(line == N + 1) {  //  Avem o necunoscuta libera
            j ++;
        } else {
            for(int col = 1; col <= M + 1; col ++) {  //  Interschimbam liniile intre ele -> aducem totul pe linia i
                std::swap(sys[i][col], sys[line][col]);
            }
            //  Nota : ne intereseaza doar elementele de pe linia curenta si col >= j
            for(int col = j + 1; col <= M + 1; col ++) {  //  Impartim toate elementele la sys[i][j], aceasta devenind 1.
                sys[i][col] /= sys[i][j];
            }
            sys[i][j] = 1;
            for(line = i + 1; line <= N; line ++) {  //  Din toate ecuatiile u > i se scade ecuatia i inmultita cu sys[u][j]
                for(int col = j + 1; col <= M + 1; col ++) {
                    sys[line][col] -= sys[line][j] * sys[i][col];
                }
                sys[line][j] = 0;
            }
            i ++; j ++;
        }
    }

    //  Acum ramane doar sa obtinem necunoscutele. O vom face in ordine inversa
    for(i = N; i >= 1; i--) {
        for(j = 1; j <= M + 1; j++) {
            if(sys[i][j] < -eps || eps < sys[i][j]) {
                if(j == M + 1) {  //  Daca singura necunoscuta nenula este rezultatul, atunci sistemul nu are solutie.
                    return false;
                }
                x[j] = sys[i][M + 1];
                for(int col = j + 1; col <= M; col++) {
                    x[j] -= x[col] * sys[i][col];
                }
                break;
            }
        }
    }

    return true;
}

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

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