Cod sursa(job #936784)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 8 aprilie 2013 19:23:02
Problema Algoritmul lui Gauss Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 2.2 kb
#include <stdlib.h>
#include <fstream>
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <string.h>
#include <iomanip>
#include <time.h>
#include <list>
using namespace std;


const string file = "gauss";

const string infile = file + ".in";
const string outfile = file + ".out";


#define MAXN 305

int N;
int M;

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

const double eps = 0.0000001;

void citire()
{
	ifstream fin(infile.c_str());

	fin >> N >> M;

	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < M + 1; j++)
		{
			int x;
			fin >> x;

			A[i][j] = x;
		}
	}

	fin.close();
}

void afisare()
{
	ofstream fout(outfile.c_str());
	fout << fixed << setprecision(8);
	for(int i = 0; i < M; i++)
	{
		fout << X[i] << " ";
	}
	fout << "\n";
	fout.close();
}


void debugPrint()
{
	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < M + 1; j++)
		{
			cout << A[i][j] << " ";
		}
		cout << "\n";
	}
	cout << "\n";
}


void subRow(int p, int r, double multiple, int j)
{
	for(int x = j; x < M + 1; x++)
	{
		A[r][x] -= A[p][x] * multiple;
	}
}


void swapRow(int p, int r, int j)
{
	for(int x = j; x < M + 1; x++)
	{
		swap(A[p][x], A[r][x]);
	}
}

void divideRow(int p, int j)
{
	double val = A[p][j];
	for(int x = j; x < M + 1; x++)
	{
		A[p][x] /= val;
	}
}


void solve()
{
	int i = 0;
	int j = 0;
	int k;
	while( i < N || j < M)
	{
	
		for(k = j; k < N; k++)
		{
			if(abs(A[i][k]) > eps)
				break;
		}
		
		if(k == N)
		{
			j++;
			continue;
		}

		if(k != i)
		{
			swapRow(i, k, j);
		}


		divideRow(i, j);

		for(int x = i + 1; x < N; x++)
		{
			subRow(i, x, A[x][j], j);
		}

//		debugPrint();

		i++;
		j++;
	}


	for(int i = N - 1; i >= 0; i--)
	{
		for(int j = 0; j <= M + 1; j++)
		{
			if(abs(A[i][j]) > eps)
			{
				if(j == M + 1)
				{
					ofstream fout(outfile.c_str());
					fout << "Imposibil\n";
					fout.close();
				}


				X[j] = A[i][M];

				for(int k = j + 1; k < M; k++)
				{
					X[j] -= X[k] * A[i][k];
				}


				break;
			}
		}
	}
	afisare();
	
}



int main()
{
	citire();
	solve();
	
}