Cod sursa(job #1364649)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 27 februarie 2015 19:22:20
Problema Algoritmul lui Gauss Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 kb
#include<cstdio>
#include<string>
#include<cmath>

using namespace std;

#ifdef HOME
const string inputFile = "input.txt";
const string outputFile = "output.txt";
#else
const string problemName = "gauss";
const string inputFile = problemName + ".in";
const string outputFile = problemName + ".out";
#endif

const int NMAX = 300 + 5;
const double EPS = 1e-10;

int N, M;
double A[NMAX][NMAX];
double B[NMAX];
double sol[NMAX];

void gauss() {
    int i, j, k, l;

    for(j = 1; j <= M; j++) {
        for(i = j; i <= N; i++)
            if(fabs(A[i][j]) > EPS)
                break;

        if(i > N)
            continue;

        for(k = 1; k <= M; k++)
            swap(A[i][k], A[j][k]);

        swap(B[i], B[j]);

        for(k = i + 1; k <= N; k++) {
            B[k] -= B[j] * A[k][j] / A[j][j];
            for(l = M; l >= j; l--)
                A[k][l] -= A[j][l] * A[k][j] / A[j][j];
        }

        B[j] /= A[j][j];
        for(k = M; k >= j; k--)
            A[j][k] /= A[j][j];
    }
}

int solve() {
    int i, j, k;

    for(i = N; i >= 1; i--) {
        for(k = i; k <= M; k++)
            if(fabs(A[i][k]) > EPS)
                break;

        for(j = M; j >= k + 1; j--)
            B[i] -= sol[j] * A[i][j];

        if(fabs(A[i][k]) < EPS && fabs(B[i]) > EPS)
            return 0;

        sol[k] = B[i] / A[i][k];
    }

    return 1;
}

int main() {
    int i, j, x;

    freopen(inputFile.c_str(), "r", stdin);
    freopen(outputFile.c_str(), "w", stdout);

    scanf("%d%d", &N, &M);

    for(i = 1; i <= N; i++) {
        for(j = 1; j <= M; j++) {
            scanf("%d", &x);
            A[i][j] = x;
        }
        scanf("%d", &x);
        B[i] = x;
    }

    gauss();

    if(solve())
        for(i = 1; i <= M; i++)
            printf("%.10f ", B[i]);
    else
        printf("Imposibil\n");

    return 0;
}