高斯消元用来求解线性方程组的解
时间复杂度O(n^3)
有浮点数的版本
const int N = 105; const double err = 1e-6; double a[N][N], x[N]; //equ个方程，n个变元 //无解返回-1，,无穷解返回自由变元的个数，唯一解返回1 int Gauss(int equ,int n) { //col正在处理的列，k正在处理的行 int col = 0, k = 0; for (; k < equ&&col < n; ++k,++col) { //max_row第col列绝对值最大的行号 int max_row = k; //找到绝对值最大的行号 for (int i = k + 1; i < equ; ++i) if (fabs(a[i][col]) > fabs(a[max_row][col])) max_row = i; //这一列全0，就不用处理了 if (fabs(a[max_row][col]) < err) { --k; continue; } //交换第k行和max_row行 if (max_row != k) for (int i = col; i <= n; ++i)std::swap(a[k][i], a[max_row][i]); for (int i = k + 1; i < equ; ++i) { if (fabs(a[i][col]) > err) { double t = a[i][col] / a[k][col]; for (int j = col; j <= n; ++j) a[i][j] -= t * a[k][j]; a[i][col] = 0; } } } //存在(0,0....0,a)这样的行则无解 for (int i = k; i < equ; ++i) if (fabs(a[i][col]) > err)return -1; //无穷个解，返回自由变元个数，也就是全零的行的数量 if (k < n)return n - k; //求解 for (int i = n - 1; i >= 0; --i) { double temp = a[i][n]; for (int j = i + 1; j < n; ++j) temp -= x[j] * a[i][j]; x[i] = temp / a[i][i]; } return 0; }洛谷oj P3389
#include<iostream> #include<cstdio> #include<cmath> const int N = 105; const double err = 1e-6; double a[N][N], x[N]; int Gauss(int equ,int n) { int col = 0, k = 0; for (; k < equ&&col < n; ++k,++col) { int max_row = k; for (int i = k + 1; i < equ; ++i) if (fabs(a[i][col]) > fabs(a[max_row][col])) max_row = i; if (fabs(a[max_row][col]) < err) { --k; continue; } if (max_row != k) for (int i = col; i <= n; ++i)std::swap(a[k][i], a[max_row][i]); for (int i = k + 1; i < equ; ++i) { if (fabs(a[i][col]) > err) { double t = a[i][col] / a[k][col]; for (int j = col; j <= n; ++j) a[i][j] -= t * a[k][j]; a[i][col] = 0; } } } for (int i = k; i < equ; ++i) if (fabs(a[i][col]) > err)return -1; if (k < n)return n - k; for (int i = n - 1; i >= 0; --i) { double temp = a[i][n]; for (int j = i + 1; j < n; ++j) temp -= x[j] * a[i][j]; x[i] = temp / a[i][i]; } return 0; } int main() { int n; scanf("%d", &n); for (int i = 0; i < n; ++i) for (int j = 0; j <= n; ++j)scanf("%lf", &a[i][j]); if (!Gauss(n, n)) for (int i = 0; i < n; ++i)printf("%.2lf\n", x[i]); else printf("No Solution\n"); return 0; }
