Pagini recente » Cod sursa (job #2901312) | Cod sursa (job #1226163) | Cod sursa (job #3030583) | Cod sursa (job #12410) | Cod sursa (job #2791047)
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
class Ecuatie {
private:
int nr_necunoscute;
vector<double> coeficienti;
public:
Ecuatie();
Ecuatie(int _nr_necunoscute);
Ecuatie(int _nr_necunoscute, double _coeficienti[]);
~Ecuatie();
int get_nr_necunoscute();
double get_rezultat();
Ecuatie operator * (double k);
Ecuatie operator *= (double k);
Ecuatie operator += (Ecuatie rhs);
double operator [] (int i); // Intoarce al i-lea coeficient
void print();
};
Ecuatie::Ecuatie() {
nr_necunoscute = 0;
}
Ecuatie::Ecuatie(int _nr_necunoscute) : nr_necunoscute(_nr_necunoscute) {
coeficienti.resize(nr_necunoscute + 1, 0);
}
Ecuatie::Ecuatie(int _nr_necunoscute, double _coeficienti[]) : nr_necunoscute(_nr_necunoscute) {
coeficienti.resize(nr_necunoscute + 1, 0);
for(int i = 0; i <= nr_necunoscute; i++)
coeficienti[i] = _coeficienti[i];
}
Ecuatie::~Ecuatie() {}
int Ecuatie::get_nr_necunoscute() {
return nr_necunoscute;
}
double Ecuatie::get_rezultat() {
return coeficienti[nr_necunoscute];
}
Ecuatie Ecuatie::operator * (double k) {
Ecuatie rez(nr_necunoscute);
for(int i = 0; i <= nr_necunoscute; i++)
rez.coeficienti[i] = coeficienti[i] * k;
return rez;
}
Ecuatie Ecuatie::operator *= (double k) {
for(double &coeficient: coeficienti)
coeficient *= k;
return *this;
}
Ecuatie Ecuatie::operator += (Ecuatie rhs) {
assert(rhs.nr_necunoscute == nr_necunoscute);
for(int i = 0; i <= nr_necunoscute; i++)
coeficienti[i] += rhs.coeficienti[i];
return *this;
}
double Ecuatie::operator [] (int poz) {
assert(poz <= nr_necunoscute + 1);
return coeficienti[poz];
}
void Ecuatie::print() {
for(double coeficient: coeficienti)
printf("%f ", coeficient);
printf("\n");
}
class Gauss {
private:
int nr_ecuatii;
int nr_necunoscute;
int last_added;
bool se_poate_rezolva;
vector<Ecuatie> ecuatii;
vector<double> necunoscute; // Valorile necunoscutelor
vector<int> pivoti; // Pozitiile pivotilor
vector<bool> libera; // Daca o variabila este libera sau nu
// Intoarce linia pe care se afla primul element nenul de pe coloana, cu linia >= decat linia data ca parametru
int get_pivot(int linie, int coloana);
// Inmulteste ecuatia cu o constanta a.i. pivotul sa devina 1
void reduce_pivot(int linie, int coloana);
// Reduce elementul de sub pivot din ecuatia ecuatie cu pivotul din ecuatia ecuatie_pivot
void reduce_ecuatie(int ecuatie, int ecuatie_pivot, int pivot_coloana);
public:
Gauss(int _nr_ecuatii, int _nr_necunoscute);
~Gauss();
// Adauga o ecuatie la lista de ecuatii
void adauga_ecuatie(Ecuatie ecuatie);
void afla_necunonscute();
void solve();
void print_necunoscute();
void print();
};
Gauss::Gauss(int _nr_ecuatii, int _nr_necunoscute) :
nr_ecuatii(_nr_ecuatii), nr_necunoscute(_nr_necunoscute), last_added(-1) {
ecuatii.resize(nr_ecuatii);
necunoscute.resize(nr_necunoscute, 0);
// Initial fiecare pivot are valoarea m + 1
// In final daca vreun pivot ramane asa inseamna ca ecuatia e de forma
// 0*x1 + 0*x2 + ... + 0*xm = b
pivoti.resize(nr_ecuatii, nr_necunoscute);
// Initial presupunem ca toate necunoscutele sunt variabile libere
libera.resize(nr_necunoscute, true);
se_poate_rezolva = true;
}
Gauss::~Gauss() {}
int Gauss::get_pivot(int linie, int coloana) {
for(int ecuatie_idx = linie; ecuatie_idx < nr_ecuatii; ecuatie_idx++)
if(ecuatii[ecuatie_idx][coloana] != 0)
return ecuatie_idx;
return -1; // Nu am gasit niciun pivot
}
void Gauss::reduce_pivot(int linie, int coloana) {
ecuatii[linie] *= 1.0 / ecuatii[linie][coloana];
}
void Gauss::adauga_ecuatie(Ecuatie ecuatie) {
last_added++;
assert(last_added < nr_ecuatii);
assert(ecuatie.get_nr_necunoscute() == nr_necunoscute);
ecuatii[last_added] = ecuatie;
}
void Gauss::reduce_ecuatie(int ecuatie_idx, int ecuatie_pivot_idx, int pivot_coloana) {
double k = -ecuatii[ecuatie_idx][pivot_coloana] / ecuatii[ecuatie_pivot_idx][pivot_coloana];
ecuatii[ecuatie_idx] += ecuatii[ecuatie_pivot_idx] * k;
}
void Gauss::afla_necunonscute() {
for(int linie = nr_ecuatii - 1; linie >= 0; linie--)
if(pivoti[linie] == nr_necunoscute) {
// Avem ecuatia 0*x1 + ... + 0*xm = b
if(ecuatii[linie].get_rezultat() != 0) {
se_poate_rezolva = false;
break;
}
}
else {
int necunoscuta = pivoti[linie];
necunoscute[necunoscuta] = ecuatii[linie].get_rezultat();
libera[necunoscuta] = false;
// calculez valoarea necunoscutei
for(int necunoscuta_gasita = nr_necunoscute - 1; necunoscuta_gasita > necunoscuta; necunoscuta_gasita--) {
if(libera[necunoscuta_gasita]) { // fixam variabila libera daca e cazul
necunoscute[necunoscuta_gasita] = 0;
libera[necunoscuta_gasita] = false;
}
necunoscute[necunoscuta] -= ecuatii[linie][necunoscuta_gasita] * necunoscute[necunoscuta_gasita];
}
}
}
void Gauss::print_necunoscute() {
if(se_poate_rezolva)
for(int i = 0; i < nr_necunoscute; i++)
printf("%.10f ", necunoscute[i]);
else
printf("Imposibil");
}
void Gauss::print() {
for(int i = 0; i < nr_ecuatii; i++)
ecuatii[i].print();
printf("\n");
}
void Gauss::solve() {
int linie = 0;
int coloana = 0;
while(linie < nr_ecuatii && coloana < nr_necunoscute) {
int pivot_linie = get_pivot(linie, coloana);
if(pivot_linie == -1) { // Nu am gasit pivot
libera[coloana] = true;
coloana++;
}
else {
if(pivot_linie != linie) // Aduc ecuatia cu pivotul pe linia curenta
swap(ecuatii[linie], ecuatii[pivot_linie]);
pivoti[linie] = coloana;
reduce_pivot(linie, coloana);
for(int linie2 = linie + 1; linie2 < nr_ecuatii; linie2++)
reduce_ecuatie(linie2, linie, coloana);
linie++;
coloana++;
}
}
afla_necunonscute();
}
double coeficienti[305];
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++) {
for(int j = 0; j < m + 1; j++)
scanf("%lf", &coeficienti[j]);
gauss.adauga_ecuatie(Ecuatie(m, coeficienti));
}
gauss.solve();
gauss.print_necunoscute();
return 0;
}