Cod sursa(job #2464578)

Utilizator ApostolIlieDanielApostol Daniel ApostolIlieDaniel Data 28 septembrie 2019 17:01:08
Problema Algoritmul lui Gauss Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.51 kb
#include <bits/stdc++.h>

using namespace std;

#define get_here cerr << "-1"

const double EPS = 0.000000001;

struct Gauss {
    vector <vector <double>> a;
    int n, m;

    Gauss (vector <vector <double>> _a, int _n, int _m) {
        a = _a;
        n = _n;
        m = _m;
    }

    vector <double> solve () {
        vector <double> ans (m);

        int i = 0, j = 0;

        while (i < n && j < m) {
            int k = i;
            while (k < n && (a[k][j] < EPS && a[k][j] > -EPS)) /// cautam o ec cu a j-lea coef nenul
                k++;
            if (k == n) {
                j++; /// nu exista -> putem ignora variabila
                continue;
            }
            if (i != k)
                for (int l = 0; l < m + 1; l++) /// aducem cea mai buna ec (nenula) sus
                    swap (a[i][l], a[k][l]);

            for (int l = j + 1; l < m + 1; l++) /// impartim ec la a[i][j]
                a[i][l] /= a[i][j];
            a[i][j] = 1;

            for (int k = i + 1; k < n; k++) {
                for (int l = j + 1; l < m + 1; l++)
                    a[k][l] -= a[k][j] * a[i][l]; /// scadem relatiile
                a[k][j] = 0; /// se reduce al j-lea coef
            }
            i++; j++;
        }

        for (int i = n - 1; i >= 0; i--) { /// de la n - 1 la 0 pt ca in ordinea inversa le-am redus
            int j = 0;
            while (j < m && a[i][j] < EPS && a[i][j] > -EPS)
                j++;
            if (j == m) {
                /// 0 == ceva -> imposibil
                return {};
            }
            ans[j] = a[i][m]; /// stim valorile de la j + 1 la m - 1 deci putem afla si j
            for (int k = j + 1; k < m; k++)
                ans[j] -= ans[k] * a[i][k];
        }
        return ans;
    }
};

#define pb push_back

int main () {

    freopen ("gauss.in", "r", stdin);
    freopen ("gauss.out", "w", stdout);

    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);

    int n, m;
    cin >> n >> m;
    vector <vector <double>> ec;
    for (int i = 1; i <= n; i++) {
        vector <double> v;
        int x;
        for (int i = 0; i <= m; i++)
            cin >> x, v.pb (x);
        ec.pb (v);
    }

    Gauss sistem (ec, n, m);
    vector <double> ans = sistem.solve ();

    if (ans.size () == 0) {
        cout << "Imposibil\n";
        return 0;
    }

    for (auto x : ans)
        cout << fixed << setprecision (10) << x << " ";
    cout << "\n";

    return 0;
}