高斯消元——acwing

题目一：高斯消元解线性方程组

883. 高斯消元解线性方程组 - AcWing题库

分析

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 110;
const double eps = 1e-6; // 注意了double, 和1e-6 ,,这样才是double的0  
int n;

double a[N][N];

int guass() {
	int c, r = 0;
	// 遍历列 
	for(c = 0; c < n; c ++) {
		// 当前列最大值 
		int t = r;
		for(int i = r; i < n; i ++) {
			if(fabs(a[i][c])>fabs(a[t][c])) t = i;
		}
		// 当前列最大值是0 
		if(fabs(a[t][c])<eps) continue;
		// 和最大值叫换行 
		swap(a[t],a[r]);
		// 当前行 化1，从后往前推，防止a[r][c] 被覆盖 
		for(int i = n; i >= c; i --) a[r][i] /= a[r][c];
		// 当前行 以下 化0 
		for(int i = r+1; i < n; i ++) {
			if(fabs(a[i][c])<eps) continue;
			for(int j = n; j >= c; j --) //从后往前减掉，防止倍数a[i][c]被覆盖 
				a[i][j] -= a[r][j]*a[i][c];
		}
		
		r ++; // 当前行操作完 
	}
	// 无解或无穷解 
	if(r < n) {
		// 遍历剩下的行 
		for(int i = r; i < n; i ++) {
			if(fabs(a[i][n]) < eps) continue;
			return 2; // 有 左边0  != 右边 非0情况， 无解 
		}
		return 1; // 全是 0 = 0， 无穷解 
	}
	// 回代 
	for(int i = n-1; i >= 0; i --) { // 遍历行，从下往上 
		// 让j 在对角线右边一位 ，遍历对角线后 
		for(int j = i+1; j < n+1; j ++) 
			a[i][n] -= a[i][j]*a[j][n];
			// 最后一列的那个值， 减去前面的除了对角线的值
			// 那些值都是，a[i][j] *上x(j) ,x(j)就是a[j][n]去看对角线就知道了，
			//看j列对应下面行列相同的，然后横向看最后一个 
	}
	
	return 0; // 有解 
}

int main() {
	cin >> n;
	for(int i = 0; i < n; i ++) 
		for(int j = 0; j < n+1; j ++) 
			cin >> a[i][j];
	
	int t = guass();
	
	if(t == 0) {
		for(int i = 0; i < n; i ++) 
			printf("%.2lf\n",a[i][n]);
	}
	else if(t == 1) puts("Infinite group solutions");
	else puts("No solution");
	
	return 0;
}

题目二：高斯消元解异或线性方程组

884. 高斯消元解异或线性方程组 - AcWing题库

分析

代码

// ＋号变成了^的线性方程组求解

#include<bits/stdc++.h>
using namespace std;

const int N = 110;
int a[N][N];

int n;

int guass() {
    int c, r = 0;
    for(c = 0; c < n; c ++) {
        int t = r;
        for(int i = r; i < n; i ++) 
            if(a[i][c]) {
                t = i;
                break;
            }
        if(!a[t][c]) continue;
        
        swap(a[t],a[r]);
        
        for(int i = r+1; i < n; i ++) 
            if(a[i][c]) // 非0
                for(int j = c; j < n+1; j ++) 
                    a[i][j] ^= a[r][j];
        
        r ++;
    }
    
    if(r < n) {
        for(int i = r; i < n; i ++) 
            if(a[i][n]) return 1;
        return 2;
    }
    // 回代
    for(int i = n-1; i >= 0; i --) 
        for(int j = i+1; j < n; j ++) 
            if(a[i][j]) // 将解代入非0项异或
                a[i][n] ^= a[j][n];
    //
    return 0;
}

int main() {
    cin >> n;
    for(int i = 0; i < n; i ++) 
        for(int j = 0; j < n+1; j ++) 
            cin >> a[i][j];
    
    int t = guass();
    
    if(t == 0) {
        for(int i = 0; i < n; i ++) cout << a[i][n] << endl;
    }
    else if(t == 2) puts("Multiple sets of solutions");
    else puts("No solution");
    
    return 0;
}