专栏首页数据结构与算法P3389 【模板】高斯消元法

P3389 【模板】高斯消元法

题目背景

Gauss消元

题目描述

给定一个线性方程组,对其求解

输入输出格式

输入格式:

第一行,一个正整数 nn

第二至 n+1n+1行,每行 n+1n+1 个整数,为a_1, a_2 \cdots a_na​1​​,a​2​​⋯a​n​​ 和 bb,代表一组方程。

输出格式:

共n行,每行一个数,第 ii行为 x_ix​i​​ (保留2位小数)

如果不存在唯一解,在第一行输出"No Solution".

输入输出样例

输入样例#1:

3
1 3 4 5
1 4 7 3
9 3 2 2

输出样例#1:

-0.97
5.18
-2.39

说明

1 \leq n \leq 100, \left | a_i \right| \leq {10}^4 , \left |b \right| \leq {10}^41≤n≤100,∣a​i​​∣≤10​4​​,∣b∣≤10​4​​

本来想深入的研究一下矩阵来着,,

结果不知道怎么着的研究到高斯消元上了,。。。。

高斯消元法真是一个神(bao)奇(li)的的东西、

本来想仔细整理整理来着,结果发现我不会在博客园里写矩阵,

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 //#define Matrix double
 6 using namespace std;
 7 const int MAXN=101;
 8 typedef double Matrix[MAXN][MAXN];
 9 inline void read(int &n)
10 {char c=getchar();bool flag=0;
11 while(c<'0'||c>'9')        c=='-'?flag=1,c=getchar():c=getchar();
12 while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;}
13 int n;
14 Matrix a;
15 void debug()
16 {
17     /*printf("********************************\n");
18     for(int i=1;i<=n;i++)
19     {
20         for(int j=1;j<=n+1;j++)    printf("%.2lf ",a[i][j]);
21         printf("\n");
22     }*/
23 }
24 void gauss_elimination(int n)
25 {
26     int r;// 将要选择的最大值 
27     for(int i=1;i<=n;i++)
28     {
29         r=i;
30         for(int j=i+1;j<=n;j++)// 枚举后面的行 
31             if(fabs(a[j][i])>fabs(a[r][i]))    r=j;
32         debug();
33         if(r!=i)    swap(a[r],a[i]);
34         debug();
35         if(!a[i][i])
36         {
37             printf("No Solution\n");
38             return;
39         }
40         for(int k=i+1;k<=n;k++)// 与后面的进行消元
41         {
42             double f=a[k][i]/a[i][i];//模拟人工消元 
43             for(int j=i;j<=n+1;j++)    a[k][j]-=f*a[i][j];
44         } 
45         debug();
46     }
47     debug();
48     for(int i=n;i>=1;i--)
49     {
50         debug();
51         for(int j=i+1;j<=n;j++)
52             a[i][n+1]-=a[j][n+1]*a[i][j];
53         a[i][n+1]/=a[i][i];
54     }
55     for(int i=1;i<=n;i++)
56         printf("%.2lf\n",a[i][n+1]);
57 }
58 int main()
59 {
60     read(n);
61     for(int i=1;i<=n;i++)
62         for(int j=1;j<=n+1;j++)
63             scanf("%lf",&a[i][j]);
64     gauss_elimination(n);            
65     return 0;
66 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • hihoCoder #1195 : 高斯消元·一

    时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 小Ho:喂不得了啦,那边便利店的薯片半价了! 小Hi:啥?! 小Ho:那边的便利店...

    attack
  • 10:矩阵转置

    10:矩阵转置 总时间限制: 1000ms 内存限制: 65536kB描述 输入一个n行m列的矩阵A,输出它的转置AT。 输入第一行包含两个整数n和m,...

    attack
  • P3717 [AHOI2017初中组]cover

    题目背景 以下为不影响题意的简化版题目。 题目描述 一个n*n的网格图上有m个探测器,每个探测器有个探测半径r,问这n*n个点中有多少个点能被探测到。 输入输出...

    attack
  • hihoCoder #1195 : 高斯消元·一

    时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 小Ho:喂不得了啦,那边便利店的薯片半价了! 小Hi:啥?! 小Ho:那边的便利店...

    attack
  • Pascal三角形

    作者:bakari   时间:2012.8.4 Pascal三角形又称杨辉三角形,是多项式系数的一种规律展示,最早是由我国数学家杨辉发现,比Pascal早200...

    CloudDeveloper
  • 1036 跟奥巴马一起编程 (15 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • Minesweeper(蓝桥杯)

    然后就想着更好的方法嘛,就是给雷区标记,然后每个区的贡献值都是周围八个区的贡献值叠加。边输入边更新就能得到答案!

    用户7727433
  • P3717 [AHOI2017初中组]cover

    题目背景 以下为不影响题意的简化版题目。 题目描述 一个n*n的网格图上有m个探测器,每个探测器有个探测半径r,问这n*n个点中有多少个点能被探测到。 输入输出...

    attack
  • 蛇形填数

    在n*n方陈里填入1,2,...,n*n,要求填成蛇形。例如n=4时方陈为: 10 11 12 1 9 16 13 2 8 15 14 3 7 6 5 4

    书童小二
  • ECJTUACM16 Winter vacation training #4 题解&源码

    https://vjudge.net/contest/149692#overview 这周一VJ比赛,题解&源码已完成! A.....................

    Angel_Kitty

扫码关注云+社区

领取腾讯云代金券