AcWing 883. 高斯消元解线性方程组-JavaScript
原题链接
简单
作者:
semicloud
,
2024-02-12 21:41:51
,
所有人可见
,
阅读 33
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
terminal: false,
});
/**
*
* @param {number[][]} arr
*/
function print(arr) {
for (let i = 0; i < arr.length; ++i) {
for (let j = 0; j < arr[i].length; ++j)
process.stdout.write(arr[i][j].toFixed(2).toString().padStart(6, ' ') + ' ');
process.stdout.write('\n');
}
}
const eps = 1e-6;
/**
* 使用高斯消元法求解 n 元 1 次方程组
* @param {number[][]} mat n * n+1 矩阵,线性方程组的增广矩阵
* @return 0 | 1 | 2
* @description 0:有唯一解,1:无穷解,2:无解
*/
function gauss(mat) {
const n = mat.length;
let [c, r] = [0, 0];
for (c = 0, r = 0; c < n; ++c) {
// 找到第 c 列上,从第 r 行开始,绝对值最大的元素所在的行索引,记为 k
let k = r;
for (let i = r; i < n; ++i) {
if (Math.abs(mat[i][c]) > Math.abs(mat[k][c]))
k = i;
}
// 如果 mat[k][c] 已经是 0,就无需消元了
if (Math.abs(mat[k][c]) < eps) continue;
// 将第 k 行的元素交换到第 r 行,从第 c 列开始(因为前面的 c-1 列都是 0 了,无需交换)
for (let i = c; i <= n; ++i) {
const tmp = mat[r][i];
mat[r][i] = mat[k][i];
mat[k][i] = tmp;
}
// 将第 r 行第 c 个元素,即 mat[r][c],搞成 1
for (let i = n; i >= c; --i) mat[r][i] /= mat[r][c];
// 利用转换后的第 r 行,将第 r+1 行到第 n 行上,第 c 列上的的元素搞成 0
for (let i = r + 1; i < n; ++i) {
if (Math.abs(mat[i][c]) < eps) continue;
for (let j = n; j >= c; --j) {
// 当 j=c 时,mat[i][c] -= mat[r][c] * mat[i][c],又因为 mat[r][c]=1,因此可以将 mat[i][c] 搞成 0
mat[i][j] -= mat[r][j] * mat[i][c];
}
}
r++;
}
if (r < n) {
// 从第 r 行到第 n 行上,如果任意一行的最后一列上的值非 0,则说明出现了 0!=0 的情况,方程组无解
for (let i = r; i < n; ++i)
if (Math.abs(mat[i][n]) > eps)
return 2;
// 无穷解
return 1;
}
// 回代
for (let i = n - 1; i >= 0; --i) {
let sum = 0;
for (let j = i + 1; j < n; ++j) {
// 系数 mat[i][j] 对应的解是 mat[j][n],它俩相乘就相当于 a_{ij} * x_j
sum += mat[i][j] * mat[j][n];
}
mat[i][n] -= sum;
}
return 0;
}
let l = 0;
let mat = [];
let n = null;
rl.on('line', (line) => {
++l;
if (l === 1) {
n = parseInt(line);
} else {
mat.push(line.trim().split(' ').map((x) => parseFloat(x)));
if (l === n + 1) {
const res = gauss(mat);
if (res === 1) console.log('Infinite group solutions');
else if (res === 2) console.log('No solution');
else {
for (let i = 0; i < n; ++i) console.log(mat[i][n].toFixed(2));
}
}
}
});