Mai intai trebuie sa te autentifici.
Cod sursa(job #1750293)
Utilizator | Data | 29 august 2016 21:10:46 | |
---|---|---|---|
Problema | Algoritmul lui Gauss | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.81 kb |
#include <bits/stdc++.h>
using namespace std;
const double kEps = 1e-9;
namespace Gauss {
// Transforms a matrix into its row echelon form
// Returns a vector of pivots (for each variable)
// or -1 if free variable
// The bool returns true if system has solution
vector<int> ToRowEchelon(vector<vector<double>> &M) {
int cons = M.size();
int vars = M[0].size() - 1;
vector<int> pivot(vars, -1);
int cur = 0;
for(int var = 0; var < vars; ++var) {
if(cur >= cons) continue;
if(abs(M[cur][var] < kEps)) {
for(int con = cur + 1; con < cons; ++con) {
if(M[con][var] != 0) {
swap(M[con], M[cur]);
break;
}
}
}
if(abs(M[cur][var]) > kEps) {
pivot[var] = cur;
double aux = M[cur][var];
for(int i = 0; i <= vars; ++i)
M[cur][i] /= aux;
for(int con = 0; con < cons; ++con) {
if(con != cur) {
double mul = M[con][var];
for(int i = 0; i <= vars; ++i) {
M[con][i] -= mul * M[cur][i];
}
assert(M[con][var] < kEps);
}
}
++cur;
}
}
return pivot;
}
};
int main() {
freopen("gauss.in", "r", stdin);
freopen("gauss.out", "w", stdout);
int n, m;
cin >> n >> m;
vector<vector<double>> M(n, vector<double>(m + 1));
for(int i = 0; i < n; ++i)
for(int j = 0; j <= m; ++j)
cin >> M[i][j];
auto save = M;
vector<int> res = Gauss::ToRowEchelon(M);
vector<double> solution(res.size());
for(int i = 0; i < m; ++i) {
if(res[i] == -1) solution[i] = 0.0;
else solution[i] = M[res[i]][m];
}
// Check
for(int i = 0; i < n; ++i) {
double res = 0.0;
for(int j = 0; j < m; ++j)
res += M[i][j] * solution[j];
if(abs(res - save[i][m]) > 0.00001) {
cout << "Imposibil\n";
return 0;
}
}
cout << fixed << setprecision(12);
for(auto x : solution)
cout << x << " ";
cout << endl;
return 0;
}