Cod sursa(job #1454243)

Utilizator GilgodRobert B Gilgod Data 25 iunie 2015 21:17:33
Problema Algoritmul lui Gauss Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.14 kb
#include <iostream>
#include <fstream>
#include <assert.h>
#include <cmath>

const int NMAX = 301;
const char IN[] = "gauss.in", OUT[] = "gauss.out";
const float EPS = 0.000001f;

using namespace std;

bool is_null(double x) { 
	return x > -EPS && x < EPS; 
}

double A[NMAX][NMAX];
double X[NMAX];
int N, M;

inline void read_data() {
	assert(freopen(IN, "r", stdin));
	assert(scanf("%d %d", &N, &M));
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j <= M; ++j) {
			assert(scanf("%lf", &A[i][j]));
		}
	}
	fclose(stdin);
}

inline void gauss_elimination() {
	int i = 0, j = 0, x;
	while (i < N && j < M) {
		//cautam linia x pentru care A[x][j] != 0
		for (x = i; x < N; ++x) {
			if (!is_null(A[x][j])) break;
		}

		//forma libera
		if (x == N) { ++j;  continue; }

		//interschimba liniile i si x
		for (int k = 0; i != x && k <= M; ++k) {
			double aux = A[i][k];
			A[i][k] = A[x][k];
			A[x][k] = aux;
		}

		//se imparte toata linia i la A[i][j]
		double aux = A[i][j];
		for (int k = j+1; k <= M; ++k) A[i][k] /= aux;
		A[i][j] = 1;

		//se reduc coeficientii pentru j in celalte ecuatii la 0
		//doar liniile si coloanele ce urmeaza, celelate sunt egalate
		for (int l = i + 1; l < N; ++l) {
			for (int k = j + 1; k <= M; ++k) {
				A[l][k] -= A[l][j] * A[i][k];
			}
			A[l][j] = 0;
		}

		++i, ++j;
	}
}

inline void compute_solutions() {
	assert(freopen(OUT, "w", stdout));
	//calculul necunoscutelor - backwards substitution
	for (int i = N-1; i >= 0; --i){
		for (int j = 0; j <= M; ++j) {
			if (!is_null(A[i][j])) {
				//daca am ajuns pe coloana y-cilor insemana ca nu se poate
				//rezolva(nu exista coeficient nenul => x poate fi oricat
				if (j == M) {
					printf("Imposibil\n");
					fclose(stdout);
					return;
				}
				double s = 0;
				for (int k = j + 1; k < M; ++k) {
					s += A[i][k] * X[k];
				}
				X[j] = (A[i][M] - s) / (is_null(A[i][j]))?1.0f:A[i][j];
				break;
			}
		}
	}
	for (int i = 0; i < M; ++i) {
		printf("%lf ", X[i]);
	}
	printf("\n");
	fclose(stdout);
}

int main() {
	read_data();
	gauss_elimination();
	compute_solutions();
	return 0;
}