Cod sursa(job #1093835)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 28 ianuarie 2014 17:45:22
Problema Algoritmul lui Gauss Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.86 kb
#include <iostream>
#include <fstream>
#include <iomanip>

using namespace std;

const int N_EQ = 300;
const int N_NE = 300;

const long double EPS = 0.00000000001;

long double A[N_EQ + 1][N_NE + 1];
long double SOL[N_NE + 1];

int N, M;

const int DIM_BUFF = ( 1 << 20 );

char buffer[DIM_BUFF];
int position = DIM_BUFF;

char GetChar()
{
    if ( position == DIM_BUFF )
    {
        fread( buffer, 1, DIM_BUFF, stdin );
        position = 0;
    }

    return buffer[ position++ ];
}

int rd()
{
    int nr = 0;
    int sgn = 1;
    char c;

    do
    {
        c = GetChar();
        if ( c == '-' ){
                c = GetChar();
                sgn = -1;
                break;
        }

    } while ( !isdigit( c ) );

    do
    {
        nr = nr * 10 + ( c - '0' );
        c = GetChar();

    } while ( isdigit( c ) );

    return nr * sgn;
}

void read()
{
    freopen("gauss.in", "r", stdin);

    N = rd(); M = rd();

    for ( int i = 1; i <= N; ++i )
    {
        for ( int j = 1; j <= M + 1; ++j )
                A[i][j] = rd();
    }
}

void GaussianElimination()
{
    int i = 1, j = 1;

    while ( i <= N && j <= M )
    {
        int x = 0;

        for ( int k = i; k <= N; ++k )
        {
            if ( A[k][j] > EPS || A[k][j] < -EPS )
            {
                x = k;
                break;
            }
        }

        if ( x == 0 )
        {
            j++;
            continue;
        }

        if ( x != i )
        {
            for ( int k = 1; k <= M + 1; ++k )
            {
                swap( A[i][k], A[x][k] );
            }
        }

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

        A[i][j] = 1;

        for ( int l = i + 1; l <= N; ++l )
        {
            for ( int c = j + 1; c <= M + 1; ++c )
            {
                A[l][c] -= A[l][j] * A[i][c];
            }

            A[l][j] = 0;
        }

        i++;
        j++;
    }
}

void compute_values()
{
    ofstream g("gauss.out");

    for ( int i = N; i >= 1; i-- )
            for ( int j = 1; j <= M + 1; ++j )
            {
                if ( A[i][j] > EPS || A[i][j] < -EPS )
                {
                    if ( j == M + 1 )
                    {
                        g << "Imposibil\n";
                        return;
                    }

                    SOL[j] = A[i][M + 1];

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

                    break;
                }
            }

    for ( int i = 1; i <= M; ++i )
            g << fixed << setprecision( 13 ) << SOL[i] << " ";
}

int main()
{
    read();
    GaussianElimination();
    compute_values();

    return 0;
}