資料

線性方程組 [Wiki]
https://zh.wikipedia.org/wiki/%E7%BA%BF%E6%80%A7%E6%96%B9%E7%A8%8B%E7%BB%84
高斯消元法 [Wiki]
https://zh.wikipedia.org/wiki/%E9%AB%98%E6%96%AF%E6%B6%88%E5%8E%BB%E6%B3%95
一般線性方程組解的結(jié)構(gòu)
http://202.113.29.3/nankaisource/mathhands/linear%20algebra/s0504/s050402/t0504020001.htm
線性方程組求解教程
http://math.fudan.edu.cn/gdsx/JIAOAN/%E7%BA%BF%E6%80%A7%E6%96%B9%E7%A8%8B%E7%BB%84.pdf
淺談異或方程組
https://www.zybuluo.com/Kurunie/note/118965
kuangbin的高斯消元模板
http://www.cnblogs.com/kuangbin/archive/2012/09/01/2667044.html

以上是學(xué)習(xí)的相關(guān)資料，自己就只貼個(gè)不完整的高斯消元模板

實(shí)數(shù)方程組求解

//實(shí)數(shù)線性方程組高斯消元求解
//齊次和非齊次都可解
double a[N][M+1];
double eps = 1e-8;
int gauss(int n, int m){
    //n個(gè)方程, m個(gè)變?cè)? 增廣矩陣的列數(shù)為m+1
    //我們只需要處理前m列即可
    int row,col;
    for (row=0,col=0;row<n&&col<m;row++,col++){
        //當(dāng)前處理第col列, 第row行
        int p_row = row; //p_row 記錄當(dāng)前列元素絕對(duì)值最大的行, 做為主元行
        for (int i=row+1;i<n;i++){
            if ( fabs(a[i][col]) > fabs(a[p_row][col]) )
                p_row = i;
        }

        if (p_row!=row){ //把主元行交換至當(dāng)前行
            for (int j=col;j<m+1;j++)
                swap(a[p_row][j], a[row][j]);
        }

        if ( fabs(a[row][col]) < eps ) {
            row--; //若當(dāng)前行當(dāng)前列元素為0則跳過, 同時(shí)矩陣的非零行數(shù)量(秩)不增加
            continue;
        }

        for (int i=row+1;i<n;i++){
            if ( fabs(a[i][col]) < eps ) continue; //若當(dāng)前行當(dāng)前列元素為0則跳過
            double pro = a[i][col]/a[row][col];
            for (int j=col;j<m+1;j++){
                a[i][j] -= pro*a[row][j];
                //對(duì)該行做一次初等變換
            }
        }
    }

    //系數(shù)矩陣的秩小于增廣矩陣的秩 Rank(A) < Rank(A') 則方程組無解
    for (int i=row;i<n;i++){
        if ( fabs(a[i][col]) > eps ) return -1;
        //當(dāng)前col指向增廣矩陣的常數(shù)項(xiàng)列, 若row及以下的常數(shù)項(xiàng)存在非零項(xiàng), 說明方程組無解
    }

    //系數(shù)矩陣的秩等于增廣矩陣的秩, 則方程組有解, 有以下兩種情況
    //增廣矩陣的秩等于變?cè)獢?shù)量時(shí), 方程組有唯一解, 自由變?cè)獢?shù)量為0
    //增廣矩陣的秩小于變?cè)獢?shù)量時(shí), 方程組有無窮多解, 自由變?cè)獢?shù)量為 m - row
    return m - row; //返回自由變?cè)膫€(gè)數(shù)
}

0/1異或方程組求解

int gauss(int n, int m) {
    //n個(gè)方程, m個(gè)變?cè)? 增廣矩陣的列數(shù)為m+1
    int row, col;
    for (row = 0, col = 0;row<n&&col<m;row++, col++) {
        //當(dāng)前處理第col列, 第row行
        int p_row = row; //p_row 為主元所在行號(hào)
        for (int i = row + 1;i<n;i++) {
            if (a[i][col]>a[p_row][col])
                p_row = i;
        }
        if (p_row != row) { //把主元所在行與當(dāng)前行交換
            for (int j = col;j<m + 1;j++)
                swap(a[p_row][j], a[row][j]);
        }
        if (a[row][col] == 0) { //若當(dāng)前行主元為0則跳過, 并在下次繼續(xù)處理此行的下一列元素
            row--;
            continue;
        }
        for (int i = row + 1; i < n;i++) {
            if (a[i][col] == 0) continue; //跳過0元素開頭的行
            for (int j = col;j<m + 1;j++)
                a[i][j] ^= a[row][j]; //做一次初等變換
        }
    }
    for (int i = row;i<n;i++) { //方程組無解
        if (a[i][col] != 0) return -1;
    }
    return m - row; //有解, 返回自由變?cè)膫€(gè)數(shù)
}