AcWing 883. 高斯消元解线性方程组
原题链接
简单
作者:
玛卡巴卡呀
,
2021-03-30 08:46:14
,
所有人可见
,
阅读 232
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static double[][] a;
static int n;
static double egs=1e-8;
//用于浮点数的比较
public static int guass() {
int r=0;
for(int c=0;c<n;c++){
int t=r;
for(int i=r;i<n;i++){
if(Math.abs(a[i][c]) > Math.abs(a[t][c])) t=i;
}
//从r开始寻找,当前列的最大值,之前比较过、且已经做过更改的行不做任何改变
if(Math.abs(a[t][c]) <egs) continue;
//如果该列的最大值为0,跳过
//此时变化的都是列,行数不变,直到在当前行的某一列中找到一个
//最大值不为0的数(绝对值大于0),否则n个线性方程变为n-1个
for(int i=0;i<=n;i++){
double tem=a[r][i];
a[r][i]=a[t][i];
a[t][i]=tem;
}
//交换,当前列绝对值最大的元素移动到了第一行
//在第一行中将绝对值最大的元素变为1
for(int i=n;i>=c;i--){
a[r][i]/=a[r][c];
}
//从后向前
//当前列的所有元素全部消0
for(int i=r+1;i<n;i++){
if(Math.abs(a[i][c])> egs){
for(int j=n;j>=c;j--){
a[i][j]-=a[i][c]*a[r][j];
}
}
}
r++;
}
if(r<n){//说明存在某一行的元素全部为0
for(int i=r;i<n;i++){
if(Math.abs(a[i][n]) > egs){
return 2;//无解
}
}
return 1;//多个解
}
for(int i=n-2;i>=0;i--){
for(int j=i+1;j<n;j++){
a[i][n]-=a[j][n]*a[i][j];
}
}
** //这个代码比较关键,想了好久才明白
/*因为本题的主要含义就是求解线性方程的解,然后此时我们已经可以确定方程存在唯一解
只需要依次将每一行的非主元素消成0,a[i][n]的值也会随之发生变化,最后输出该值即可
a[i][n]的值就是等于本身减去当前行非主元的值*下一行n列的值
此时的下一行已经是左边只有主元,右边是一个值*/**
return 0;//唯一解
}
public static void main(String[] args) throws NumberFormatException, IOException {
// TODO Auto-generated method stub
BufferedReader bufferedReader =new BufferedReader(new InputStreamReader(System.in));
n=Integer.parseInt(bufferedReader.readLine());
a=new double [n][n+1];
for(int i=0;i<n;i++){
String p[]=bufferedReader.readLine().split(" ");
for (int j = 0; j <=n; j++) {
a[i][j]=Double.parseDouble(p[j]);
}
}
int k=guass();
if(k==1){
System.out.println("Infinite group solutions");
}else if(k==2){
System.out.println("No solution");
}else if(k==0){
for(int i=0;i<n;i++){
System.out.printf("%.2f", a[i][n]);
System.out.println();
}
}
}
}