Метод Гаусса: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Строка 56: Строка 56:
Теория:
Теория:
* [http://e-maxx.ru/algo/linear_systems_gauss e-maxx.ru — Метод Гаусса решения системы линейных уравнений]
* [http://e-maxx.ru/algo/linear_systems_gauss e-maxx.ru — Метод Гаусса решения системы линейных уравнений]
Код:
* [http://github.com/indy256/codelibrary/blob/master/java/src/Gauss.java CodeLibrary — Gaussian elimination algorithm in O(N^3)]
* [http://github.com/indy256/codelibrary/blob/master/java/src/Gauss.java CodeLibrary — Gaussian elimination algorithm in O(N^3)]
Код:
* [http://github.com/ADJA/algos/blob/master/NumberTheory/Gauss.cpp Algos — Gauss method of solving systems of linear algebraic equation.]
* [http://github.com/ADJA/algos/blob/master/NumberTheory/Gauss.cpp Algos — Gauss method of solving systems of linear algebraic equation.]

Версия от 03:49, 16 июля 2015

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;

int n, m, ansRow[110];
double a[110][110], ans[110];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m + 1; j++)
            scanf("%lf", &a[i][j]);

    fill(ansRow, ansRow + m, -1);
    for (int col = 0, row = 0; col < m && row < n; col++) {
        int bestRow = row;
        for (int i = row + 1; i < n; i++)
            if (fabs(a[i][col]) > fabs(a[bestRow][col]))
                bestRow = i;
        if (fabs(a[bestRow][col]) < 1e-9)
            continue;
        for (int j = 0; j < m + 1; j++)
            swap(a[row][j], a[bestRow][j]);
        ansRow[col] = row;
        for (int i = 0; i < n; i++) {
            if (i == row)
                continue;
            double k = -a[i][col] / a[row][col];
            for (int j = col; j < m + 1; j++)
                a[i][j] += k * a[row][j];
        }
        row++;
    }
    for (int col = 0; col < m; col++)
        ans[col] = (ansRow[col] != -1 ? a[ansRow[col]][m] / a[ansRow[col]][col] : 0);
    for (int row = 0; row < n; row++) {
        double s = 0;
        for (int col = 0; col < m; col++)
            s += a[row][col] * ans[col];
        if (fabs(s - a[row][m]) > 1e-9) {
            printf("NO");
            return 0;
        }
    }
    if (count(ansRow, ansRow + m, -1)) {
        printf("INF");
        return 0;
    }
    printf("YES\n");
    for (int i = 0; i < m; i++)
        printf("%.10lf ", ans[i]);
}

Ссылки

Теория:

Код: