Cod sursa(job #810731)

Utilizator toranagahVlad Badelita toranagah Data 10 noiembrie 2012 21:28:31
Problema Algoritmul lui Gauss Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream fin("gauss.in");
ofstream fout("gauss.out");

const int MAX_N = 310;
const double epsilon = 1e-9;

double mat[MAX_N][MAX_N];
double solutions[MAX_N];
int N, M;

void read();
void gauss_elimination();
void find_solutions();

int main() {
	read();
	gauss_elimination();
	find_solutions();
}

void read() {
	fin >> N >> M;
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= M + 1; ++j) {
			fin >> mat[i][j];
		}
	}
}

void gauss_elimination() {
	int i = 1, j = 1, k, l;
	while (i <= N && j <= M) {
		for (k = i; k <= N && abs(mat[k][j]) < epsilon; ++k);
		if (k == N + 1) {
			++j;
			continue;
		}
		if (k != i) {
			for (l = 1; l <= M + 1; ++l) {
				swap(mat[i][l], mat[k][l]);
			}
		}
		for (k = j + 1; k <= M + 1; ++k) {
			mat[i][k] /= mat[i][j];
		}
		mat[i][j] = 1;
		for (k = i + 1; k <= N; ++k) {
			for (l = j + 1; l <= M + 1; ++l) {
				mat[k][l] -= mat[i][l] * mat[k][j];
			}
			mat[k][j] = 0;
		}
		++i, ++j;
	}
}

void find_solutions() {
	for (int i = N; i > 0; --i) {
		for (int j = 1; j <= M + 1; ++j) {
			if (abs(mat[i][j]) > epsilon) {
				if (j == M + 1) {
					fout << "Imposibil" << endl;
					return;
				}
				solutions[j] = mat[i][M+1];
				for (int k = j + 1; k <= M; ++k) {
					solutions[j] -= solutions[k] * mat[i][k];
				}
				break;
			}
		}
	}
	fout << setprecision(10);
	for (int i = 1; i <= M; ++i) {
		fout << solutions[i] << ' ';
	}
}