Cod sursa(job #610508)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 27 august 2011 16:16:43
Problema Algoritmul lui Gauss Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.97 kb
#include <fstream>
#include <iostream>
#include <string.h>

#define MAXN 303
#define EPS 0.0000001

using namespace std;

double A[MAXN][MAXN];
double X[MAXN];

inline double abs(const double val)
{
	return (val < 0) ? (-1*val) : val;
}

bool GaussElimination(const int n, const int m, double x[])
{
	int i=0, j=0, k;
	int maxi;
	double aux[MAXN];
	
	while (i<n && j<m)
	{
		maxi = i;
		for (k=i; k<n; ++k)
		{
			if (abs(A[k][j]) > abs(A[maxi][j]))//A[k][j]<-EPS || A[k][j]>EPS)//
			{
				maxi = k;
				break;
			}
		}
		
		if (A[maxi][j]<-EPS || A[maxi][j]>EPS)// && (k<n)//
		{
			if (maxi != i)
			{
				const double var1 = A[maxi][j], var2 = A[i][j];
				// swap lines
				memcpy(aux, A[maxi], (m+1)*sizeof(double));
				memcpy(A[maxi], A[i], (m+1)*sizeof(double));
				memcpy(A[i], aux, (m+1)*sizeof(double));
				
				A[maxi][j] = var2;
				A[i][j] = var1;
			}
			
			for (int l = j+1; l <= m; ++l)
				A[i][l] /= A[i][j];
			A[i][j] = 1;
			
			for (int u = i+1; u<n; ++u)
			{
				for (int l = j+1; l<=m; ++l)
					A[u][l] -= (A[u][j] * A[i][l]);
				A[u][j] = 0;
			}

			i++;
		}

		j++;
	}
	
	for (i = n-1; i>=0; --i)
	{
		for (j = 0; j <= m; ++j)
		{
			if (A[i][j]>EPS || A[i][j]<-EPS)
			{
				if (j == m)
				{
					return false;
				}
				
				x[j] = A[i][m];
				for(k = j+1; k < m; ++k)
					x[j] -= (x[k] * A[i][k]);
				
				break;
			}
		}
	}
	
	return true;
}

int main()
{
	int n, m;
	fstream fin("gauss.in", fstream::in);
	fstream fout("gauss.out", fstream::out);
	
	fin >> n >> m;
	//cout << n << " " << m << endl;
	
	for (int i=0; i<n; ++i)
	{
		for (int j=0; j<=m; ++j)
		{
			fin >> A[i][j];
			//cout << A[i][j] << " ";
		}
		//cout << endl;
	}
	
	fout.precision(8);
	if (GaussElimination(n, m, X))
	{
		for (int i=0; i<m; ++i)
			fout << fixed << X[i] << " ";
		fout << "\n";
	}
	else
	{
		fout <<"Imposibil\n";
	}
	
	fin.close();
	fout.close();
	return 0;
}