Cod sursa(job #1113282)

Utilizator fhandreiAndrei Hareza fhandrei Data 20 februarie 2014 15:27:34
Problema Algoritmul lui Gauss Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.39 kb
// Include
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

// Constante
const int sz = 303;
const double err = 1e-7;

// Functii
bool notEqualsZero(double x);
template<class T> T ABS(T x);
void lineSwap(double *line1, double *line2);

// Variabile
ifstream in("gauss.in");
ofstream out("gauss.out");

int equations, variables;

double System[sz][sz];
double answer[sz];

// Main
int main()
{
	out << fixed << setprecision(10);
	
	in >> equations >> variables;
	++variables;
	
	for(int i=1 ; i<=equations ; ++i)
		for(int j=1 ; j<=variables ; ++j)
			in >> System[i][j];
	
	int currentEquation=1, currentVariable=1;
	while(currentEquation <= equations && currentVariable < variables)
	{
		int eq;
		// Caut prima ecuatie ce contine variabila curenta
		for(eq=currentEquation ; eq<=equations && !notEqualsZero(System[eq][currentVariable]) ; ++eq);
		
		// Daca nu am gasit nimic, trec la variabila urmatoare
		if(eq == equations+1)
		{
			++currentVariable;
			continue;
		}
		
		// Daca prima ecuatie nu contine variabila curenta, dar exista alta ce-o contine, le schimb intre ele
		if(eq != currentEquation)
			lineSwap(System[currentEquation], System[eq]);
		
		// Simplific ecuatia prin variabila curenta. Variabila curenta va deveni 1
		for(int i=currentVariable+1 ; i<=variables ; ++i)
			System[currentEquation][i] /= System[currentEquation][currentVariable];
		System[currentEquation][currentVariable] = 1;
		
		// Reduc, prin scadere, variabila curenta din toate celelalte ecuatii
		for(int eq=currentEquation+1 ; eq<=equations ; ++eq)
		{
			for(int i=currentVariable+1 ; i<=variables ; ++i)
				System[eq][i] = System[currentEquation][i]*System[eq][currentVariable] - System[eq][i];
			System[eq][currentVariable] = 0;
		}
		
		// Am mai rezolvat o ecuatie, am mai redus o variabila. Trec la urmatoarele
		++currentEquation;		++currentVariable;
	}
	
	// Iau toate ecuatiile de jos in sus, afland pe raspunsurile si
	// inlocuind variabilele nou-aflate in celelalte ecuatii nerezolvate
	for(int currentEquation=equations ; currentEquation ; --currentEquation)
	{
		// Caut prima variabila nenula a ecuatiei
		int currentVariable = find_if(System[currentEquation]+1, System[currentEquation]+variables+1, notEqualsZero) - System[currentEquation];
		
		// In cazul in care ecuatia e de forma (0+0+...+0=0), variabila
		// specifica ei poate lua orice valoare, inclusiv 0, cat va si ramane
		if(currentVariable > variables)
			continue;
		
		// In cazul in care ecuatia e de forma (0+0+...+0=k, k!=0), sistemul nu are solutie
		if(currentVariable == variables)
		{
			out << "Imposibil" << '\n';
			in.close();
			out.close();
			return 0;
		}
		
		// Am gasit variabila specifica ecuatiei curente
		answer[currentVariable] = System[currentEquation][variables];
		
		// Pentru toate ecuatiile nerezolvate, trec in dreapta variabila nou-aflata
		for(int eq=1 ; eq<currentEquation ; ++eq)
			System[eq][variables] -= answer[currentVariable] * System[eq][currentVariable];
	}
	
	for(int i=1 ; i<variables ; ++i)
		out << answer[i] << ' ';
	out << '\n';
	
	in.close();
	out.close();
	return 0;
}

bool notEqualsZero(double x)
{	return ABS(x) > err;	}

template<class T> T ABS(T x)
{   return x<0? -x:x;    }

void lineSwap(double *line1, double *line2)
{
	for(int i=1 ; i<=variables ; ++i)
		swap(line1[i], line2[i]);
}