Cod sursa(job #3255736)

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

using namespace std;

ifstream fin("gauss.in");
ofstream fout("gauss.out");

const int 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.
void 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;
        }
    }
}

// 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) {
                // 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;
            }
        }
    }
}

void print_solution(vector<double>& X, int& M) {
    for (int i = 1; i <= M; ++i) {
        fout << fixed << setprecision(8) << X[i] << ' ';
    }
    fout << '\n';
}

//Algoritmul lui Gauss propriu-zis
void gaussian_elimination(vector<vector<double>>& A, vector<double>& X, int& N, int& M, int& i, int& j, int& k) {
    while(i <= N && j <= M) {
        find_nonzero_value(A, k, i, j, N);
        if(k == N + 1) {
            ++j;
            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;
    }
}

void solve(vector<vector<double>>& A, vector<double>& X, int& N, int& M) {
    int i = 1, j = 1, k;
    gaussian_elimination(A, X, N, M, i, j, k);
    calculate_solution(A, X, N, M);
    print_solution(X, M);
}

void read_input(vector<vector<double>>& A, vector<double>& X, int& N, int& M) {
    fin >> N;
    fin >> 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) {
            fin >> A[i][j];
        }
    }   
}

int main(int argc, char* argv[]) {
    int N = 0, M = 0;
    vector<vector<double>> A;
    vector<double> X;
    read_input(A, X, N, M);
    solve(A, X, N, M);
    return 0;
}