Метод Гаусса

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
#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]);
}
vector<double> gauss(vector<vector<double>> &a) {
    int eqCount = a.size(), varCount = a[0].size() - 1;
    vector<int> ansRow(varCount, -1);

    for (int col = 0, row = 0; col < varCount && row < eqCount; col++) {
        int bestRow = row;
        for (int i = row + 1; i < eqCount; i++)
            if (fabs(a[i][col]) > fabs(a[bestRow][col]))
                bestRow = i;

        if (fabs(a[bestRow][col]) < 1e-9)
            continue;

        swap(a[row], a[bestRow]);
        ansRow[col] = row;

        for (int i = 0; i < eqCount; i++) {
            if (i == row)
                continue;
            double k = -a[i][col] / a[row][col];
            for (int j = col; j <= varCount; j++)
                a[i][j] += k * a[row][j];
        }

        row++;
    }

    if (count(ansRow.begin(), ansRow.end(), -1))
        return {};

    vector<double> ans(varCount);
    for (int col = 0; col < varCount; col++)
        ans[col] = a[ansRow[col]].back() / a[ansRow[col]][col];

    for (int row = 0; row < eqCount; row++) {
        double sum = 0;
        for (int col = 0; col < varCount; col++)
            sum += a[row][col] * ans[col];

        if (fabs(sum - a[row].back()) > 1e-9)
            return {};
    }

    return ans;
}

Ссылки

Теория:

Код: