Cod sursa(job #1115602)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 21 februarie 2014 21:59:25
Problema Algoritmul lui Gauss Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.23 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>

using namespace std;

const double EPS = 1e-8;

int N, M;
vector< vector<double> > Coefficients;
vector<double> Solutions;
bool Compatible;

void Gauss(vector< vector<double> > coefficients, vector<double> &solutions, bool &compatible) {
    int n = int(coefficients.size()), m = int(coefficients[0].size() - 1), fixedVariables = 0;
    for (int i = 0, j = 0; i < n && j < m; ++i, ++j) {
        int k = i;
        for (; abs(coefficients[k][j]) < EPS; ++k);
        if (k == n) {
            --i;
            continue;
        }
        ++fixedVariables;
        swap(coefficients[i], coefficients[k]);
        for (k = 0; k < n; ++k) {
            if (k != i) {
                double ratio = coefficients[k][j] / coefficients[i][j];
                for (int l = 0; l <= m; ++l)
                    coefficients[k][l] -= coefficients[i][l] * ratio;
                coefficients[k][j] = 0;
            }
        }
    }
    compatible = true;
    solutions = vector<double>(m, 0);
    for (int i = n - 1, j; i >= 0; --i) {
        for (j = 0; j <= m && abs(coefficients[i][j]) <= EPS; ++j);
        if (j == m) {
            compatible = false;
            return;
        }
        if (j < m) {
            solutions[j] = coefficients[i][m] / coefficients[i][j];
            for (int k = 0; k < i; ++k) {
                coefficients[k][m] -= coefficients[k][j] * solutions[j];
                coefficients[k][j] = 0;
            }
        }
    }
}

void Solve() {
    Gauss(Coefficients, Solutions, Compatible);
}

void Read() {
    ifstream cin("gauss.in");
    cin >> N >> M;
    Coefficients = vector< vector<double> >(N, vector<double>(M + 1));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j <= M; ++j)
            cin >> Coefficients[i][j];
    cin.close();
}

void Print() {
    ofstream cout("gauss.out");
    if (!Compatible) {
        cout << "Imposibil\n";
    } else {
        for (int i = 0; i < M; ++i)
            cout << fixed << setprecision(10) << Solutions[i] << " ";
        cout << "\n";
    }
    cout.close();
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}