高斯消元

算法简介

\(\quad\)高斯约旦消元法相比普通的消元法,代码更简单,精度更准确,复杂度差不多。

高斯-约旦消元法

\(\quad\)首先要为方程建立一个矩阵,储存等式两边的系数。

\(\quad\)这一种消元法最后的矩阵会消成只有对角线的数字>0。

\(\quad\)大致思路如下:

  1. 选择一个尚未被选过的未知数作为主元,选择一个包含这个主元且之前没有被选中过的方程。
  2. 将这个方程这个主元的系数化为1
  3. 通过加减消元,消掉其他方程中的这个未知数。
  4. 重复以上步骤,直到把每一行都变成只有一项有系数。

例题

Luogu 3389 模板题

综合代码理解上述内容即可

#include<bits/stdc++.h>
using namespace std;
const int maxn=101;
const double eps=1e-8;
int n;
double a[maxn][maxn];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) 
    for(int j=1;j<=n+1;j++)
    cin>>a[i][j];
    for(int i=1;i<=n;i++)
    {
        int mm=i;
        for(int j=i+1;j<=n;j++)
        {
            if(fabs(a[j][i])>fabs(a[mm][i])) mm=j;
        }
        for(int j=1;j<=n+1;j++) swap(a[i][j],a[mm][j]);
        if(fabs(a[i][i])<eps)
        {
            cout<<"No Solution"<<endl;
            return 0;
        }
        for(int j=1;j<=n;j++)
        {
            if(j!=i)
            {
                double tmp=a[j][i]/a[i][i];
                for(int k=i+1;k<=n+1;k++)
                {
                    a[j][k]-=(tmp*a[i][k]);
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(fabs(a[i][n+1]/a[i][i])<eps) cout<<"0.00"<<endl;
        else printf("%.2lf\n",a[i][n+1]/a[i][i]);
    }
    return 0;
}

Luogu 2455 线性方程组

\(\quad\)如何判断是无解还是有无数解?

\(\quad\)我们可以将每一列都为 0 的行积攒到最后,再判断等号右边的数是否为 0 。

#include<bits/stdc++.h>
using namespace std;
const int maxn=101;
const double eps=1e-10;
int n,cnt=0,rr;
double a[maxn][maxn];
int main()
{
    rr=1;
    cin>>n;
    for(int i=1;i<=n;i++) 
    for(int j=1;j<=n+1;j++)
    cin>>a[i][j];
    for(int i=1;i<=n;i++)
    {
        int mm=rr;
        for(int j=rr+1;j<=n;j++)
        {
            if(fabs(a[j][i])>fabs(a[mm][i])) mm=j;
        }
        if(fabs(a[mm][i])<eps)
        {
            continue ;
        }
        for(int j=1;j<=n+1;j++) swap(a[rr][j],a[mm][j]);
        for(int j=1;j<=n;j++)
        {
            if(j!=rr)
            {
                double tmp=a[j][i]/a[rr][i];
                for(int k=i+1;k<=n+1;k++)
                {
                    a[j][k]-=(tmp*a[rr][k]);
                }
            }
        }
        rr++;
    }
    rr--;
    if(rr<n)
    {
        for(int i=rr+1;i<=n;i++)
        {
            if(fabs(a[i][n+1])>eps) 
            {
                cout<<-1<<endl;
                return 0;
            }
        }
        cout<<0<<endl;
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        printf("x%d=",i);
        if(fabs(a[i][n+1]/a[i][i])<eps) cout<<"0.00"<<endl;
        else printf("%.2lf\n",a[i][n+1]/a[i][i]);
    }
    return 0;
}

注意

\(\quad\)有的题目虽然有方程但是经过手动推导是可以简化,不需要去用程序消元,程序消元的复杂度高达 \(n^3\)!

上一篇:data为什么是一个函数


下一篇:python报错:Failed to establish a new connection: [Errno -2] Name or service not known