Cod sursa(job #2290706)

Utilizator ArctopusKacso Peter-Gabor Arctopus Data 26 noiembrie 2018 20:51:02
Problema Algoritmul lui Gauss Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.58 kb
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <fstream>

#define ld long double

using namespace std;

const int NLIM = 300 + 10;

int N, M;

ld mat[NLIM][NLIM];


// elementary row operations:
void divide_row(int row, ld val)
{
    for(int j = 0; j < M; ++j)
        mat[row][j] /= val;
}

void add_row(int row1, int row2, ld a = 1)
{
    for(int j = 0; j < M; ++j)
        mat[row1][j] += mat[row2][j] * a;
}

void swap_rows(int row1, int row2)
{
    for(int j = 0; j < M; ++j)
        swap(mat[row1][j], mat[row2][j]);
}

bool dead_row(int row)
{
    if(mat[row][M - 1] != 0)
    {
        for(int j = 0; j < M - 1; ++j)
            if(mat[row][j] != 0)
                return false;
        return true;
    }
    return false;
}

int first_one(int row)
{
    for(int j = 0; j < M; ++j)
        if(mat[row][j] == 1)
            return j;
    return -1;
}

void print()
{
    cerr << "\n";
    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < M - 1; ++j)
            cerr << setw(7) << mat[i][j];
        cerr << setw(7) << "|";
        cerr << setw(7) << mat[i][M - 1];
        cerr << "\n";
    }
    cerr << "\n";
}

ifstream fcin("gauss.in");
ofstream fcout("gauss.out");
int main()
{

    // input
    fcin >> N >> M;
    ++M;
    for(int i = 0; i < N; ++i)
        for(int j = 0; j < M; ++j)
            fcin >> mat[i][j];

    //print();

    // first phase
    for(int i = 0; i < N; ++i)
    {
        for(int i2 = i; i2 < N; ++i2)
            if(mat[i2][i] != 0)
            {
                swap_rows(i, i2);
                break;
            }

        // i th line is divided by first elment, if it isn't 0
        if(mat[i][i] != 0)
        {
            divide_row(i, mat[i][i]);

            for(int i2 = i + 1; i2 < N; ++i2)
                add_row(i2, i, -mat[i2][i]);
        }

        //print();
    }

    // look for dead rows:
    for(int i = 0; i < N; ++i)
        if(dead_row(i))
        {
            fcout << "Imposibil\n";
            return 0;
        }

    //cerr << "\n\n reduce \n\n";
    // reduced echelon form:
    for(int i = N; i >= 1; --i)
    {
        int first = first_one(i);
        for(int i2 = i - 1; i2 >= 0 && first != -1; --i2)
            add_row(i2, i, -mat[i2][first]);
    }

    // get results
    fcout.precision(8);
    int i = 0, j = 0;
    while( i < N && j < M - 1 )
    {
        if( mat[i][j] == 0 )
        {
            fcout << fixed <<  0 << " ";
            ++j;
        }
        else
        {
            fcout << fixed << mat[i][M-1] << " ";
            ++i;
            ++j;
        }
    }
    fcout << "\n";


    return 0;
}