洛谷P2455 [SDOI2006]线性方程组

高斯消元模板要求输出解的情况（无穷解/无解）

1. 之前写的丑陋代码

#include <iostream>

#include <cstdio>

#include <cmath>

#include <algorithm>

using namespace std;

const double eps=1e-7;

const int maxn=1000;

int n;//n个变量 n个方程

double A[maxn][maxn];

int Gauss() {//高斯消元 返回值 无解-- -1

             //多解 -- 0 唯一解 -- 1（此时解保存在A[i][n+1]中）

    int h,l,r;//h--行 l--列

    for(h = 1,l = 1;h <= n && l <= n;++ h,++ l){//消系数矩阵（n*n）

        r = h;

        for(int i = h + 1;i <= n;++ i) if(fabs(A[i][l]) > fabs(A[r][l]) + eps) r=i;//找到当前列所有行中的最大值(做除法时减小误差)

        if(r != h) for(int i = h;i <= n + 1;++ i) swap(A[r][i],A[h][i]);

        if(fabs(A[h][l]) < eps) {--h;continue;}///当前列h行以下全为0(包括h行)

        for(int i = h + 1;i <= n;++ i){

            if(fabs(A[i][l]) < eps) continue;

            for(int j = n + 1;j >= l;-- j) A[i][j]-=A[i][l]/A[h][l]*A[h][j];//加减消元

        }

    }

    for(int i = h;i <= n;++ i) if(A[i][l] > eps) return -1;//系数均为0但结果不为0 无解

    if(h <= n) return 0;//消元后所得方程不足n个（否则h为n+1） 有多解

    for(int i = n; i ;-- i){//有唯一解 此时为严格的上三角矩阵 代入消元

        for(int j = i + 1;j <= n + 1;++ j)

            A[i][n+1]-=A[i][j]*A[j][n+1];

        A[i][n+1]/=A[i][i];

    }

	return 1;

}

int main() {

    scanf("%d",&n);

    for(int i = 1;i <= n;++ i)

        for(int j = 1;j <= n + 1;++ j)

             scanf("%lf",&A[i][j]);

    int ans = Gauss();

    if(ans<=0) printf("%d",ans);

    else

   	for(int i = 1;i <= n;++i){

       printf("x%d=", i);

       if (fabs(A[i][n+1]) < eps) puts("0");

        else printf("%.2f\n", A[i][n+1]);

   }

    return 0;

}

2. 改进后（更短更好理解）还是很丑陋？？？

/*

高斯约当消元法

把矩阵直接消成对角矩阵

与普通的高斯消元（消成阶梯矩阵再回代）相比计算量略大

但因为省略回代过程 代码更好写

*/

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cmath>

using namespace std;

const int maxn=110;

int n,ans;

const double eps=1e-8;//控制精度

typedef double Matrix[maxn][maxn];//把二维数组重定义为矩阵

Matrix A;

int Guess(Matrix A,int n){

//传入增广矩阵和n的值 这里默认有n个未知数 n个方程 增广矩阵下标从1开始 有n行 n+1列

//若方程数有m个（m>=n） 可传入m 在此模板基础上微调

//返回值：-1--无实数解     0--有无穷多解    1--有唯一实数解 此时矩阵已被消成对角型

	int r; bool flag = false;//flag 判无穷解

    for(int i = 1; i <= n;++ i) {//i为枚举的行 也可以理解成当前要消第几个未知数

        r = i;

        for(int j = i + 1;j <= n;++ j) if(fabs(A[j][i]) > fabs(A[r][i])) r=j;//取包含该未知数的方程里系数绝对值最大的那个方程进行消元 可提高精度

        if(fabs(A[r][i]) < eps) {//若最大系数绝对值为0 则包含该未知数的方程系数全是0

        //此时说明【可能】有无穷解 之后有可能会出现无解的情况 所以只能先标记再处理 而不能直接返回无穷解

        //若题目不要求输出具体是无穷解还是无解 可以直接return

			flag = true; continue;}//放弃这一行 处理下一行（下一个未知数

        if(r != i) swap(A[i],A[r]);//若系数绝对值最大的不是这一行 就交换这两行（swap直接交换两行的指针 不用for循环再交换）

        for(int k = 1;k <= n;++ k) if(k != i)//与除了第i行以外其他行进行消元 直接消成对角型

			for(int j = n + 1;j >= 1;-- j)//逆序枚举列 可以避免用中间变量（double）记录需要乘的倍数造成的精度误差

				A[k][j] -= A[k][i] / A[i][i] * A[i][j];

    }

    //以下为判断解的情况 若题目中明确方程一定有解 或者 不要求输出具体是无解还是无穷解 可省略下面几行

    //需要先判断是否无解再判断是否为无穷解

	for(int i = 1,j;i <= n;++ i){//枚举每一行

    	for(j = 0;!A[i][j] && j <= n;++ j);//用指针j指向第一个这一行第一个不为零的数

    	if(j == n + 1 && A[i][j]) return -1;//若指向第n+1列说明系数全为零但结果不为零 方程无解

	}

	if(flag) return 0;//无穷解

    return 1;//唯一解

}

int main()

{

    scanf("%d",&n);

    for(int i = 1;i <= n;++ i)

        for(int j = 1;j <= n + 1;++ j)

            scanf("%lf",&A[i][j]);

    ans = Guess(A,n);

    if(ans != 1) printf("%d",ans);

    else

    for (int i = 1; i <= n; ++i) {

        printf("x%d=", i);

        if (fabs(A[i][n+1]/A[i][i]) < eps) puts("0");//防止输出负零（double型）

        else printf("%.2f\n", A[i][n+1]/A[i][i]);//已消成对角矩阵 第i+1列除以第i列就是答案

    }

    return 0;

}

巴特西

洛谷P2455 [SDOI2006]线性方程组

高斯消元模板要求输出解的情况（无穷解/无解）

1. 之前写的丑陋代码

2. 改进后（更短更好理解）还是很丑陋？？？

最新文章

热门文章

巴特西

洛谷P2455 [SDOI2006]线性方程组

高斯消元模板 要求输出解的情况（无穷解/无解）

1. 之前写的丑陋代码

2. 改进后（更短更好理解）还是很丑陋？？？

最新文章

热门文章

高斯消元模板要求输出解的情况（无穷解/无解）