Cod sursa(job #613314)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 21 septembrie 2011 13:41:58
Problema Algoritmul lui Gauss Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.08 kb
#include <iostream>
#include <cstdio>

#define NMax 305

using namespace std;

const double Eps=0.000000001;
int N, M;
double A[NMax][NMax], X[NMax];

void Read ()
{
    freopen ("gauss.in", "r", stdin);
    scanf ("%d %d", &N, &M);
    for (int i=1; i<=N; ++i)
    {
        for (int j=1; j<=M+1; ++j)
        {
            scanf ("%lf", &A[i][j]);
        }
    }
}

void Print (bool V)
{
    freopen ("gauss.out", "w", stdout);
    if (!V)
    {
        printf ("Imposibil\n");
    }
    for (int i=1; i<=M; ++i)
    {
        printf ("%.8lf ", X[i]);
    }
    printf ("\n");
}

void Reduce (int i, int j, int p)
{
    for (int k=p+1; k<=M+1; ++k)
    {
        A[j][k]-=(A[j][p]*A[i][k]);
    }
    A[j][p]=0;
}

void Swap (int i, int j)
{
    for (int k=1; k<=M+1; ++k)
    {
        double Aux=A[i][k];
        A[i][k]=A[j][k];
        A[j][k]=Aux;
    }
}

bool CalculateX ()
{
    for (int i=N; i>0; --i)
    {
        for (int j=1; j<=M+1; ++j)
        {
            if (A[i][j]<-Eps or A[i][j]>Eps)
            {
                if (j==M+1)
                {
                    return false;
                }
                X[j]=A[i][M+1];
                for (int k=j+1; k<=M; ++k)
                {
                    X[j]-=(X[k]*A[i][k]);
                }
                break;
            }
        }
    }
    return true;
}

bool Gauss ()
{
    int i=1, j=1, k;
    while (i<=N and j<=M)
    {
        for (k=i; k<=N; ++k)
        {
            if (A[k][j]<-Eps or A[k][j]>Eps)
            {
                break;
            }
        }
        if (k==N+1)
        {
            ++j;
            continue;
        }
        if (i!=k)
        {
            Swap (i, k);
        }
        for (int p=j+1; p<=M+1; ++p)
        {
            A[i][p]/=A[i][j];
        }
        A[i][j]=1;
        for (int l=i+1; l<=N; ++l)
        {
            Reduce (i, l, j);
        }
        ++i, ++j;
    }
    return CalculateX ();
}

int main()
{
    Read ();
    Print (Gauss ());
    return 0;
}