Cod sursa(job #1750291)

Utilizator retrogradLucian Bicsi retrograd Data 29 august 2016 21:07:05
Problema Algoritmul lui Gauss Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 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 res = Gauss::ToRowEchelon(M);
	vector<double> solution(res.size());

	for(int i = 0; i < solution.size(); ++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 - M[i][m]) > kEps) {
			cout << "Imposibil\n";
			return 0;
		} 
	}

	cout << fixed << setprecision(12);
	for(auto x : solution)
		cout << x << " ";
	cout << endl;

	return 0;
}