![洛谷 P3389：[模板] 高斯消元法 ← 高斯-约旦消元法（Gauss-Jordan Elimination）](images/news1.jpg)
【题目来源】https://www.luogu.com.cn/problem/P3389【题目描述】给定一个线性方程组对其求解。【输入格式】第一行一个正整数 n。第二至 n1 行每行 n1 个整数为 a1,a2,…,an 和 b代表一组方程。【输出格式】共 n 行每行一个数第 i 行为 xi四舍五入保留 2 位小数。如果不存在唯一解或无解在第一行输出 No Solution。【输入样例】31 3 4 51 4 7 39 3 2 2【输出样例】-0.975.18-2.39【数据范围】1≤n≤100|ai|≤10^4|b|≤10^4。保证数据若有解则所有解均满足 |xi|≤10^3且 xi±10^(-6) 和 xi 四舍五入后的结果相同即不会因为较小的精度误差导致四舍五入后的结果不同。【算法分析】● 高斯消元法Gaussian Elimination 是一种用于求解线性方程组的经典算法也是线性代数中最基础的工具之一。它通过一系列初等变换将增广矩阵化为行阶梯形矩阵或行最简形矩阵从而求出方程组的解。● 高斯消元法的本质是系统地消除未知数将复杂的方程组转化为更容易求解的形式。整个过程分为两个阶段1前向消元Forward Elimination将矩阵化为上三角矩阵行阶梯形。2回代求解Back Substitution从最后一个方程开始逐个求解未知数。● 核心代码解析一选主元int idxr; for(int ir; in; i) { if(fabs(a[i][c])fabs(a[idx][c])) idxi; }从第 r 行开始往下找第 c 列上绝对值最大的那个元素。idx 记录绝对值最大的行号。为什么要找绝对值最大的—— 减小浮点误差。二判断是否跳过该列if(fabs(a[idx][c])eps) continue;如果找到的最大值都接近于 0说明这一列全是 0。这个未知数在当前剩余的方程中不存在直接跳过该列它可能是自由变量。continue 跳过后面的代码进入下一列但 r 不变还没找到新的主元。三交换到当前行swap(a[r],a[idx]);把找到的主元行第 idx 行换到第 r 行。swap(a[r], a[idx]) 交换的是整行包括常数项。四归一化double diva[r][c]; for(int jc; jn; j) a[r][j]/div;div 就是主元的值。把第 r 行的所有元素从第 c 列到第 n 列含常数项都除以 div。结果主元变成了 1这一行其他元素相应缩放。五消去其他行for(int i0; in; i) { if(i!r fabs(a[i][c])eps) { double vala[i][c]; for(int jc; jn; j) { a[i][j]-val*a[r][j]; } } }对所有行不只是下面的行如果第 c 列不为 0就消掉它。val a[i][c] 是第 i 行第 c 列的当前值。a[i][j] - val * a[r][j] 就是用第 r 行归一化后主元为 1去消。消完后第 i 行的第 c 列变成 0。注意这里消的是所有行包括上面的这是高斯-约旦消元法的特点直接得到对角矩阵不用回代。【算法代码】#include bits/stdc.h using namespace std; const int N105; const double eps1e-8; double a[N][N]; int n; int gauss() { int r0; for(int c0; cn; c) { //1.Select pivot int idxr; for(int ir; in; i) { if(fabs(a[i][c])fabs(a[idx][c])) idxi; } if(fabs(a[idx][c])eps) continue; swap(a[r],a[idx]); //2.Normalize the current row, and the pivot becomes 1 double diva[r][c]; for(int jc; jn; j) a[r][j]/div; //3.Eliminate all rows below for(int i0; in; i) { if(i!r fabs(a[i][c])eps) { double vala[i][c]; for(int jc; jn; j) { a[i][j]-val*a[r][j]; } } } r; } for(int ir; in; i) { //No solution if(fabs(a[i][n])eps) return -1; } if(rn) return 0; //Infinite solutions return 1; //Unique solution } int main() { cinn; for(int i0; in; i) { for(int j0; jn; j) { cina[i][j]; } } int tgauss(); if(t-1 || t0) coutNo Solution\n; else { for(int i0; in; i) { printf(%.2lf\n,a[i][n]); } } return 0; } /* in: 3 1 3 4 5 1 4 7 3 9 3 2 2 out: -0.97 5.18 -2.39 */【参考文献】https://www.luogu.com.cn/problem/solution/P3389
洛谷 P3389：[模板] 高斯消元法 ← 高斯-约旦消元法（Gauss-Jordan Elimination）
【题目来源】https://www.luogu.com.cn/problem/P3389【题目描述】给定一个线性方程组对其求解。【输入格式】第一行一个正整数 n。第二至 n1 行每行 n1 个整数为 a1,a2,…,an 和 b代表一组方程。【输出格式】共 n 行每行一个数第 i 行为 xi四舍五入保留 2 位小数。如果不存在唯一解或无解在第一行输出 No Solution。【输入样例】31 3 4 51 4 7 39 3 2 2【输出样例】-0.975.18-2.39【数据范围】1≤n≤100|ai|≤10^4|b|≤10^4。保证数据若有解则所有解均满足 |xi|≤10^3且 xi±10^(-6) 和 xi 四舍五入后的结果相同即不会因为较小的精度误差导致四舍五入后的结果不同。【算法分析】● 高斯消元法Gaussian Elimination 是一种用于求解线性方程组的经典算法也是线性代数中最基础的工具之一。它通过一系列初等变换将增广矩阵化为行阶梯形矩阵或行最简形矩阵从而求出方程组的解。● 高斯消元法的本质是系统地消除未知数将复杂的方程组转化为更容易求解的形式。整个过程分为两个阶段1前向消元Forward Elimination将矩阵化为上三角矩阵行阶梯形。2回代求解Back Substitution从最后一个方程开始逐个求解未知数。● 核心代码解析一选主元int idxr; for(int ir; in; i) { if(fabs(a[i][c])fabs(a[idx][c])) idxi; }从第 r 行开始往下找第 c 列上绝对值最大的那个元素。idx 记录绝对值最大的行号。为什么要找绝对值最大的—— 减小浮点误差。二判断是否跳过该列if(fabs(a[idx][c])eps) continue;如果找到的最大值都接近于 0说明这一列全是 0。这个未知数在当前剩余的方程中不存在直接跳过该列它可能是自由变量。continue 跳过后面的代码进入下一列但 r 不变还没找到新的主元。三交换到当前行swap(a[r],a[idx]);把找到的主元行第 idx 行换到第 r 行。swap(a[r], a[idx]) 交换的是整行包括常数项。四归一化double diva[r][c]; for(int jc; jn; j) a[r][j]/div;div 就是主元的值。把第 r 行的所有元素从第 c 列到第 n 列含常数项都除以 div。结果主元变成了 1这一行其他元素相应缩放。五消去其他行for(int i0; in; i) { if(i!r fabs(a[i][c])eps) { double vala[i][c]; for(int jc; jn; j) { a[i][j]-val*a[r][j]; } } }对所有行不只是下面的行如果第 c 列不为 0就消掉它。val a[i][c] 是第 i 行第 c 列的当前值。a[i][j] - val * a[r][j] 就是用第 r 行归一化后主元为 1去消。消完后第 i 行的第 c 列变成 0。注意这里消的是所有行包括上面的这是高斯-约旦消元法的特点直接得到对角矩阵不用回代。【算法代码】#include bits/stdc.h using namespace std; const int N105; const double eps1e-8; double a[N][N]; int n; int gauss() { int r0; for(int c0; cn; c) { //1.Select pivot int idxr; for(int ir; in; i) { if(fabs(a[i][c])fabs(a[idx][c])) idxi; } if(fabs(a[idx][c])eps) continue; swap(a[r],a[idx]); //2.Normalize the current row, and the pivot becomes 1 double diva[r][c]; for(int jc; jn; j) a[r][j]/div; //3.Eliminate all rows below for(int i0; in; i) { if(i!r fabs(a[i][c])eps) { double vala[i][c]; for(int jc; jn; j) { a[i][j]-val*a[r][j]; } } } r; } for(int ir; in; i) { //No solution if(fabs(a[i][n])eps) return -1; } if(rn) return 0; //Infinite solutions return 1; //Unique solution } int main() { cinn; for(int i0; in; i) { for(int j0; jn; j) { cina[i][j]; } } int tgauss(); if(t-1 || t0) coutNo Solution\n; else { for(int i0; in; i) { printf(%.2lf\n,a[i][n]); } } return 0; } /* in: 3 1 3 4 5 1 4 7 3 9 3 2 2 out: -0.97 5.18 -2.39 */【参考文献】https://www.luogu.com.cn/problem/solution/P3389
