高斯消元法講解（【洛谷】3389）

題面

Gauss消元

題目描述

給定一個線性方程組，對其求解

輸入輸出格式

輸入格式：

第一行，一個正整數n

第二至n+1行，每行n+1個整數，為a1,a2…an和b，代表一組方程。

輸出格式：

共n行，每行一個數，第i行為xi （保留2位小數）

如果不存在唯一解，在第一行輸出”No Solution”.

輸入輸出樣例

輸入樣例#1：

1

1 1

輸出樣例#1：

1.00

說明

1<=n<=100, |ai|<=10000, |b|<=10000

題解

高斯消元法，數學中比較常見的方法。

通過構造矩陣來求解多元一次方程，其主要思想就是加減消元法。

主要步驟如下（構成上三角）：

1.標明未被選擇過的、xi項系數絕對值最大的一行（這樣更加容易判斷是否有解），将整個式子除以xi的系數（xi系數化為1）。同時将其交換至第i行（友善求解）

2.将未被選擇過的行中的該項全部按照系數相應的減去標明的那行的系數（剩下的其他行xi系數化為0）

當所有行都標明過時，已經構成了上三角

3.倒序求解，每次将常數減去已經求出的所有項的解，此時可以求出目前項的解（将已知解帶入求未知解）

最後依次輸出即可

源代碼：

無所謂讀入優化了

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAX 110
using namespace std;
double g[MAX][MAX];
int n,now;
inline void read(double &x)
{
      x=;
      short int t=;
      char ch=getchar();
      while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
      if(ch=='-')
      {
              t=-;
              ch=getchar();
      }
      while(ch>='0'&&ch<='9')
      {
               x=x*+ch-;
               ch=getchar();
      }
      x*=t;
}
int main()
{
      cin>>n;
      for(int i=;i<=n;++i)
             for(int j=;j<=n+;++j)
                read(g[i][j]);
      for(int i=;i<=n;++i)
      {
              now=i;
              for(int j=i+;j<=n;++j)//找出目前項系數的絕對值的最大值 
                if(fabs(g[now][i])<fabs(g[j][i]))
                   now=j;
              for(int j=i;j<=n+;++j)//将其放在對應的行，友善計算 
                swap(g[now][j],g[i][j]);
              if(g[i][i]==)//如果此時絕對值最大系數已經為0 
              {             //則證明此方程組無解 
                      cout<<"No Solution"<<endl; 
                      return ;
              }
            for(int j=i+;j<=n+;++j)//将系數化為1 
               g[i][j]/=g[i][i];
            g[i][i]=;
            for(int j=i+;j<=n;++j)//在其他式子中将此項系數化為0 
            {
                  for(int k=i+;k<=n+;++k)
                    g[j][k]-=g[j][i]*g[i][k];
                  g[j][i]=;
            }
      }//做完之後，剩餘的矩陣是上三角
      for(int i=n;i>=;--i)//倒着求解即可 
      {
              for(int j=i+;j<=n;++j)//減去後面所有已經求出解的值 
              {
                  g[i][n+]-=g[i][j]*g[j][n+];
                  g[i][j]=;
              }
              g[i][n+]/=g[i][i];   //隻剩下目前的未知量以及常數量（其實沒必要除，因為已經是1了） 
              g[i][i]=;
      }
      for(int i=;i<=n;++i)
        printf("%.2f\n",g[i][n+]);
      return ;
}