Cod sursa(job #2736606)

Utilizator popashtefan10Popa Stefan popashtefan10 Data 3 aprilie 2021 17:45:33
Problema Algoritmul lui Gauss Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.83 kb
#include <iostream>
#include <cstdio>
#include <vector>

#define eps 0.0000000000001

using namespace std;

class Gauss {

  int n, m; /// nr de ecuatii, nr de necunoscute
  vector< vector<double> >  ecuatii;
  vector<int> pivoti;
  vector<double> sol;

public:

  Gauss(int _n, int _m) : n(_n), m(_m) {
    sol.resize(m, 0);
  }

  void read_ec() {
    vector<double> new_ec(m + 1, 0);

    for(int i = 0; i < m + 1; i++)
      scanf("%lf", &new_ec[i]);
    ecuatii.push_back(new_ec);
  }

  void print_ec() {
    for(auto &ecuatie: ecuatii) {
      for(auto &coef: ecuatie)
        printf("%.3f ", coef);
      printf("\n");
    }
    printf("\n");
  }

  void reduce() {
    pivoti.resize(n, -1);
    int ec = 0;

    for(int pivot = 0; pivot < m; pivot++) {
      if(ec == n)
        break;

      /// caut o ecuatie care sa aiba coef[pivot] diferit de 0 ca sa il pot fixa ca pivot
      int ec_piv = ec;
      while(ec_piv < n && ecuatii[ec_piv][pivot] == 0)
        ec_piv++;
      if(ec_piv == n) /// toti coeficientii variabilei corespunzatoare pivotului sunt 0
        continue;

      if(ec != ec_piv)
        swap(ecuatii[ec], ecuatii[ec_piv]); /// vreau ca ecuatia de pe pozitia curenta (ec) sa aiba pivotul
      pivoti[ec] = pivot;

      /// impart toata linia la coeficientul pivotului
      for(int coef = pivot + 1; coef <= m; coef++)
        ecuatii[ec][coef] /= ecuatii[ec][pivot];
      ecuatii[ec][pivot] = 1;

      /// reduc coeficientii de pe coloana pivotului din celelalte ecuatii la 0
      for(int _ec = ec + 1; _ec < n; _ec++) {
        for(int coef = pivot + 1; coef <= m; coef++)
          ecuatii[_ec][coef] -= ecuatii[_ec][pivot] * ecuatii[ec][coef];
        ecuatii[_ec][pivot] = 0;
      }

      ec++;
    }
  }

  bool solve() {
    reduce();

    for(int ec = n - 1; ec >= 0; ec--) {
      /// nu am pivot, deci ecuatia are toti coeficientii 0
      if(pivoti[ec] == -1) {
        /// daca am o ecuatie cu toti coeficientii 0, iar rezultatul ecuatiei e diferit de 0, atunci nu pot gasi solutie
        if(ecuatii[ec][m] > eps)
          return false;
        continue;
      }

      /// calculez variabila de pe pozitia pivotului
      sol[ pivoti[ec] ] = ecuatii[ec][m];
      for(int coef = m - 1; coef > pivoti[ec]; coef--)
        sol[ pivoti[ec] ] -= ecuatii[ec][coef] * sol[coef];
    }

    return true;
  }

  vector<double> get_sol() {
    return sol;
  }

};

int main() {
  freopen("gauss.in", "r", stdin);
  freopen("gauss.out", "w", stdout);
  int n, m;

  scanf("%d %d", &n, &m);
  Gauss gauss(n, m);

  for(int i = 1; i <= n; i++)
    gauss.read_ec();

  if(!gauss.solve())
    printf("Imposibil");
  else {
    vector<double> sol = gauss.get_sol();
    for(double &var: sol)
      printf("%.10f ", var);
  }

  return 0;
}