Cod sursa(job #2785412)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 18 octombrie 2021 17:35:54
Problema Algoritmul lui Gauss Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.37 kb
#include <fstream>
#include <vector>
#include <iomanip>

using namespace std;

const int NMAX = 300;
const double EPS = 1e-12;

bool NotNull(double x) { return x < -EPS || x > EPS; }

vector<double> res;
vector<bool> determined, considered;
vector<int> auto_assigned; ///auto-assigned to 0 in order to make the system "work"
bool inconsistent; ///system is inconsistent

void solveGauss(int N, int M, vector<vector<double>> sys) {
    res.resize(M + 1, 0);
    determined.resize(M + 1, true);
    considered.resize(M + 1, false);
    auto_assigned.clear();
    inconsistent = false;
    int rank = 1;
    for (int col = 1; col <= M && rank <= N; col++) {
        for (int i = rank; i <= N; i++) {
            if (NotNull(sys[i][col])) {
                swap(sys[rank], sys[i]);
                break;
            }
        }
        if (NotNull(sys[rank][col]) == false) {
            considered[col] = true; ///we are assigning 0 by default...
            auto_assigned.push_back(col);
            continue;
        }
        considered[col] = true;
        long double ct = sys[rank][col];
        for (int j = rank; j <= M + 1; j++) {
            sys[rank][j] /= ct;
        }
        for (int i = 1; i <= N; i++) {
            if (NotNull(sys[i][col]) == false || i == rank) {
                continue;
            }
            long double ct = sys[i][col] / sys[rank][col];
            for (int j = rank; j <= M + 1; j++) {
                sys[i][j] -= ct * sys[rank][j];
            }
        }
        rank++;
    }
    for (int i = rank; i <= N; i++) { ///system is inconsistent <=> 0 * x1 + 0 * x2 + ... + 0 * xm != 0
        if (NotNull(sys[i][M + 1])) {
            inconsistent = true;
        }
    }
    for (int i = 1; i <= M; i++) {
        if (!considered[i]) {
            ///again...if there are more unknowns than there are equations, let`s hope we can set all the remaining unknowns to 0 and make the "system" work
            auto_assigned.push_back(i);
        }
    }
    for (int i = 1; i < rank; i++) {
        for (int j : auto_assigned) {
            sys[i][j] = 0; ///changed j`s coef to 0, since it is auto-assigned 0 anyways...
        }
    }
    for (int i = 1; i < rank; i++) {
        int f = 0, l = M;
        for (; f <= M; f++) {
            if (NotNull(sys[i][f])) {
                break;
            }
        }
        for (; l >= 1; l--) {
            if (NotNull(sys[i][l])) {
                break;
            }
        }
        if (f == l) {
            res[f] = sys[i][M + 1];
        } else {
            determined[f] = false; ///we cannot determine f, but we can determine some of the other unknowns...
        }
    }
}

int main() {
    ifstream f("gauss.in");
    ofstream g("gauss.out");
    int N, M;
    f >> N >> M;
    vector<vector<double>> sys(N + 1, vector<double>(M + 2));
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M + 1; j++) {
            f >> sys[i][j];
        }
    }
    solveGauss(N, M, sys);
    bool all_unknowns_determined = true;
    for (int i = 1; i <= M; i++) {
        all_unknowns_determined &= determined[i];
    }
    if (!all_unknowns_determined || inconsistent) {
        g << "Imposibil\n";
    } else {
        for (int i = 1; i <= M; i++) {
            g << fixed << setprecision(10) << res[i] << ' ';
        }
    }
    return 0;
}