Cod sursa(job #811050)

Utilizator rvnzphrvnzph rvnzph Data 11 noiembrie 2012 14:05:44
Problema Algoritmul lui Gauss Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.87 kb
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <stdlib.h>

#define MLen 301
#define NLen 302

#define EPS 0.001

using namespace std;

double A[MLen][NLen];

double x[NLen];

int main()
{
	freopen("gauss.in","r",stdin);
	freopen("gauss.out","w",stdout);

	int M,N;
	cin>>M>>N;	// M ecuatii, N necunoscute

	++N;	// in matricea A memorez pe coloana N vectorul de solutii B

	for(int i=1;i<=M;++i)
		for(int j=1;j<=N;++j)
			cin>>A[i][j];

	/* schimb forma lui A intr-una care ma ajuta sa calculez mai usor vectorul x
	 * iau num(i) = numarul de elem nule consecutive incepand cu coloana 1 de pe linia i
	 *
	 * A' (matricea A modificata) va avea urmatoarea proprietate:
	 *		num(1) < num(2) < num(3) < .. < num(M)
	 *
	 * OBSERVATIE 0:	Daca M(numar ecuatii) < N(numar necunoscute) nu inseamna ca nu am solutie.
	 *					Pot exista variabile libere si N(devine numarul variabilelor fixe necunoscute) poate ajunge <= M.
	 */

	for(int R=1,C=1;R<=M&&C<N;)	// R-row, C-column
	{
		// caut un element nenul pe coloana C
		// daca acest element nu exista atunci x[C] este o variabila libera

		if(A[R][C]==0)	// daca A[R][C] = 0 caut o alta linie care are A[i][C] nenul, unde R < i <= M
		{
			int nR=0;

			for(int i=R+1;i<=M;++i)
				if(A[i][C])
				{
					nR=i;
					break;
				}

			if(nR==0)	// nu am gasit o linie cu elementul de pe coloana C nenul => x[C] este variabila libera
			{
				++C;
				continue;
			}
			else
				for(int j=C;j<=N;++j)	// interschimb 2 linii
					swap(A[R][j],A[nR][j]);
		}

		for(int j=C+1;j<=N;++j) A[R][j]/=A[R][C];	// vreau ca linia R sa aiba forma (0, 0, .. 0, 1, ...)
		A[R][C]=1;

		// reduc celelate linii a.i  A[i][C] = 0, unde R < i <= M
		// ma folosesc de linia R pe care o inmultesc cu A[i][C] si o scad din linia i
		// A[R][C] = 1

		for(int i=R+1;i<=M;++i)
			if(A[i][R]!=0)
			{
				for(int j=C+1;j<=N;++j)
					A[i][j]-=A[i][C]*A[R][j];
				A[i][C]=0;
			}

		++R, ++C;
	}

	/* caut solutiile parcurgand matricea A' de jos in sus
	 *
	 * fie linia i care are forma (0, 0, .., 0, 1, d[j+1], d[j+2], .. ,d[N-1]), cu num(i) 0-uri in fata
	 * eu voi calcula x[j] = d[N] - suma(x[k] * d[k]),	j < k < N
	 *
	 * cum num(i) < num(orice linie cu indicele > i) si j=num(i) + 1 atunci inseamna ca eu deja stiu x[k]
	 *
	 * OBSERVATIE 1: Daca am o linie de forma (0, 0, .., 0, z), z != 0 , atunci NU am solutie la sistem
	 * OBSERVATIE 2: Variabilele libere pot avea orice valoare (aici vor fi 71)
	 */

	for(int i=1;i<N;++i) x[i]=71;

	for(int R=M;R>0;--R)
	{
		int C=1;
		while(A[R][C]==0&&C<N) ++C;

		if(C==N&&abs(A[R][N])>EPS)	// vezi OBSERVATIA 1
		{
			cout<<"Imposibil\n";
			return 0;
		}

		x[C]=A[R][N];	// calculez x[C]
		for(int j=C+1;j<N;++j)
			x[C]-=x[j]*A[R][j];
	}

	// afisare
	for(int i=1;i<N;++i) printf("%.10lf ",x[i]);
	cout<<'\n';

	return 0;
}