Cod sursa(job #793710)

Utilizator danalex97Dan H Alexandru danalex97 Data 3 octombrie 2012 20:41:10
Problema Algoritmul lui Gauss Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.41 kb
// Eliminarea Gaussiana este o metoda buna ( defapt optima ) de a rezolva
// un tablou de ecuatii liniare. Algoritmul presupunere reducerea la un
// "triunghi". In acest triunghi cel mai de la stanga termen de pe fiecare
// line va fi determinabil daca am determinat toti termenii de pe urmatoarele
// linii. Deci aflam rezultatul de la N la 1.

// Reducerea la acest triunghi este Algoritmul lui Gauss propriu-zis. Incepem
// de pe prima linie si prima coloana. Cand gasim un termen nenul >i pe coloana
// j intersctam linia termenului nenul cu linia i. Apoi ca sa aducem la o forma
// mai simpla ecuatiile vom imparti linia cu termenul A[i][j]. Incrementam i
// si j pana cand unul dintre acestea este mai mare decat N resprectiv M.
// In cazul in care nu avem nici un termen pozitiv pe coloana j trecem la starea
// i,j+1 .

#include <cstdio>
using namespace std;

const int Nmax = 310;
const double EPS = 0.0000000001;

double A[Nmax][Nmax];
double V[Nmax];
int N,M;

#define swap(a,b) { double aux = a ; a = b ; b = aux; }

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

    scanf("%d %d\n",&N,&M);

    for (int i=1;i<=N;++i)
        for (int j=1;j<=M+1;++j)
            scanf("%lf",&A[i][j]);

    for (int i=1,j=1,k;i<=N && j<=M;++i,++j)
    {
        for ( k=i;k<=N;++k )
            if ( A[k][j]<-EPS || A[k][j]>EPS )
                break;
        if ( k==N+1 )
        {
            --i;
            continue;
        }

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

        for (int l=j+1;l<=M+1;++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+1;++l)
                A[u][l]-=A[u][j]*A[i][l];
            A[u][j] = 0;
        }
    }

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

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

                break;
            }

    for(int i = 1; i <= M; ++i)
        printf("%.8lf ", V[i]);
    printf("\n");

    fclose(stdin);
    fclose(stdout);

    return 0;
}