Cod sursa(job #3255737)

Utilizator BogdanRazvanBogdan Razvan BogdanRazvan Data 12 noiembrie 2024 10:51:35
Problema Algoritmul lui Gauss Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.33 kb
#include <bits/stdc++.h>

using namespace std;

#define EPS 0.0000001

// Cautam o linie k pentru care A[k][j] sa fie nenul. Folosim epsilonul pentru a nu lua in considerare micile erori de calcul.
bool find_nonzero_value(vector<vector<double>>& A, int& k, int& i, int& j, int& N)
{
    for (k = i; k <= N; ++k) {
        if (A[k][j] < -EPS || A[k][j] > EPS) {
            break;
        }
    }
    if(k == N + 1) {
        ++j;
        return false;
    }
    return true;
}

void read_input(vector<vector<double>>& A, vector<double>& X, int& N, int& M) {
    scanf("%d", &N);
    scanf("%d", &M);
    A.assign(N + 2, vector<double>(M + 2, 0));
    X.assign(M + 1, 0);
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M + 1; ++j) {
            scanf("%lf", &A[i][j]);
        }
    }   
}

// Interschimbam pe k cu i, daca este cazul.
void swap_values(vector<vector<double>>& A, int& k, int &i, int& M) {
    for(int l = 1; l <= M + 1; ++l) {
        double aux = A[i][l];
        A[i][l] = A[k][l];
        A[k][l] = aux;
    }
}

// Pentru a usura calculele, impartim toate valorile de pe linia i la A[i][j], A[i][j] devenind 1.
// Observam ca valorile de pe linia i si coloanele 1..j-1 sunt egale cu 0 de la pasii precedenti ai algoritmului,
// deci nu e necesar sa le parcurgem pentru a le imparti.
void divide_line(vector<vector<double>>& A, int& i, int& j, int& M) {
    for (int l = j + 1; l <= M + 1; ++l) {
        A[i][l] = A[i][l] / A[i][j];
    }
    A[i][j] = 1;
}

// Scadem din ecuatiile i+1...N ecuatia i inmultita cu A[u][j], pentru a egala toti coeficientii de coloana j
// a acestor linii la 0.
void make_zeros(vector<vector<double>>& A, int& i, int& j, int& N, int& M) {
    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;
    }
}

// Calculul necunoscutelor
void calculate_solution(vector<vector<double>>& A, vector<double>& X, int& N, int& M) {
    for (int i = N; i > 0; --i)
        for (int j = 1; j <= M + 1; ++j)
            if (A[i][j] > EPS || A[i][j] < -EPS) {
                //Singura valoare nenegativa de pe linia i este rezultatul => sistemul nu are solutie.
                if(j == M + 1) {
                    printf("Imposibil\n");
                    exit(0);
                }

                // Calculam pe necunoscuta j = rezultatul ecuatiei i - necunoscutele j+1...M inmultite cu coeficientii lor din aceasta ecuatie.
                X[j] = A[i][M + 1];
                for (int k = j + 1; k <= M; ++k) {
                    X[j] -= X[k] * A[i][k];
                }
                break;
            }
}

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

    int N = 0, M = 0;
    vector<vector<double>> A;
    vector<double> X;
    read_input(A, X, N, M);

    int i = 1, j = 1, k;
    double aux;

    //Algoritmul lui Gauss propriu-zis
    while(i <= N && j <= M)
    {
        bool res = find_nonzero_value(A, k, i, j, N);
        if (res == false) {
            continue;
        }
        if(k != i) {
            swap_values(A, k, i, M);
        }
        divide_line(A, i, j, M);
        make_zeros(A, i, j, N, M);
        ++i; ++j;
    }
    calculate_solution(A, X, N, M);

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

    return 0;
}