首页 > 其他分享 >高斯消元

高斯消元

时间:2024-07-20 20:08:28浏览次数:8  
标签:std return int inline include 高斯消 define

#include <iostream>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <climits>
#include <random>
#include <bitset>
#include <unordered_map>
#define orz %
#define ll long long
#define juruo Optimist_Skm
#define mid ((l + r) >> 1)
#define pii std::pair<int, int>
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define m_p std::make_pair
#define pq std::priority_queue<int>
#define pq_min std::priority_queue<int, std::vector<int>, std::greater<int> >
#define open(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define test(x) cout << "Test: " << x << '\n'
#define close fclose(stdin);fclose(stdout);
#define ull unsigned long long
#define debug(); printf("qwq\n");

namespace Fast_Skm {

	template <typename T>
	inline void read(T &x) {
		register T s = 0, w = 1;
 		char c = getchar();
		while(!isdigit(c)) {
			if(c == '-')  w  = -1;
			c = getchar();
		}
		while(isdigit(c))
			s = (s << 1) + (s << 3) + (c & 0xcf), c = getchar();
			
		x = s * w;
		return ;
	}

	template <typename T, typename... Arp>
	inline void read(T &x, Arp &...arp) {
		read(x), read(arp...);
        return ;
	}

	template <typename T>
	inline void write(T x) {
		if(x < 0) x = -x, putchar('-');
		register int p = 0;
		static char s[100];
		do {
			s[++p] = x orz 10 + '0';
			x /= 10;
		} while (x);
		while(p) putchar(s[p--]);
		putchar(' ');
	}

	template <typename T, typename... Arp>
	inline void write(T &x, Arp &...arp) {
		write(x), write(arp...);
		return ;
	}

	template <typename S, typename T>
	inline void smax(S &x, T y) {
		x = (x > y) ? x : y;
	}

	template <typename S, typename T>
	inline void smin(S &x, T y) {
		x = (x < y) ? x : y;
	}

	inline void quit() {
		exit(0);
		return ;
	}
	
	inline ll quick_pow(ll a, ll b, ll P) {
		register ll ans = 1;
		while(b >= 1) {
			if(b & 1) {
				ans = ans * a % P;
			}
			a = a * a % P;
			b >>= 1;
		}
		return ans;
	}
	
	template <typename T>
	inline T exgcd(T a, T b, T &x, T &y) {
		if(b == 0) {
		 	x = 1; y = 0;
		 	return a;
		}
		int gcd = exgcd(b, a % b, x, y);
		int tmp = y;
		y = x - a / b * y;
		x = tmp;
		return gcd;
	}


} using namespace Fast_Skm;

const int N = 105;
double eps = 1e-7;
int n;
double a[N][N];

inline int gauss(int n, int m) {   //n元,m个等式
	int c = 0;//当前主元数
	for (int i = 1; i <= n; ++i) { //枚举第i元(列)
		bool f = 0;
		for (int j = c + 1; j <= m; ++j) { //枚举第j个等式(行)
			if (fabs(a[j][i]) > eps) { //寻找系数不为0的行
				++c, f = 1;
				std::swap(a[j], a[c]);//交换
				break;
			}
		}
		if (!f) continue;
		double p = a[c][i];
		for (int j = 1; j <= n + 1; ++j) { //系数化为一
			a[c][j] = a[c][j] * 1.0 / p;
		}
		for (int j = 1; j <= m; ++j) {	//加减消元
			if (j != c && fabs(a[j][i]) > eps) {					
				double q = a[j][i];
                for (int k = i; k <= n + 1; ++k) {
                    a[j][k] -= a[c][k] * q;
                }
			}
		}
	}
	for (int i = c + 1; i <= m; ++i)
        if (fabs(a[i][n + 1]) > eps) return -1;//无解
	if (c == n) return 0;//唯一解
    return 1;//无穷多解
}

signed main() {

	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);

	read(n);

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n + 1; ++j) {
			scanf("%lf", &a[i][j]);
		}
	}

	if (!gauss(n, n)) {
		for (int i = 1; i <= n; ++i) {
			printf("%.2lf\n", a[i][n + 1]);
		}
	} else {
		printf("No Solution");
	}
	
	return 0;
}

标签:std,return,int,inline,include,高斯消,define
From: https://www.cnblogs.com/optimist-skm/p/18313690

相关文章

  • 【数学】高斯消元
    1.算法简介高斯消元法(Gauss–Jordanelimination)是求解线性方程组的经典算法。例如求解下列方程组:\(\begin{cases}2x+9y-5z=10\\4x+20y+z=24\\x-2y+3z=8\end{cases}\)形式化的,高斯消元可用于求解类似于\(\begin{cases}a_{1,1}x_1+a_{1,2}x_2+\dots+a_{1,n}x_n=b......
  • G68 实数线性基+高斯消元法 P3265 [JLOI2015] 装备购买
    视频链接:G68实数线性基+高斯消元法P3265[JLOI2015]装备购买_哔哩哔哩_bilibili  P3265[JLOI2015]装备购买-洛谷|计算机科学教育新生态(luogu.com.cn)//线性基+高斯消元法O(n*m*m)#include<iostream>#include<cstring>#include<algorithm>usingnames......
  • 高斯消元
    高斯-约旦消元解线性方程组例题:线性方程组步骤:选出未被更新的行中第\(k\)列绝对值最大的值,令为主元把主元所在行移到当前行,加减消元消去主元重复12结束后若存在找不到主元(找到是0)的情况,那就遍历没处理的行,如果有常数项非\(0\)则无解,否则无数解点击查看代......
  • 高斯消元
    前言:由于作者未系统过学习线性代数,故下文肯定有不严谨的成分,不过应付算法竞赛是绰绰有余了QAQ。\[\begin{cases}a_{1,1}x_1+a_{1,2}x_2+\cdots+a_{1,n}x_n=b_1\\a_{2,1}x_1+a_{2,2}x_2+\cdots+a_{2,n}x_n=b_2\\\cdots\\a_{n,1}x_1+a_{n,2......
  • 高斯消元和矩阵快速幂
    高斯消元高斯消元是一种能在\(O(N^3)\)的时间内求解\(N\)元一次方程组的算法。其思路大致如下:使第一个未知数只有第一个式子中系数非\(0\)。使第二个未知数只有第二个式子中系数非\(0\)。\(\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\vdots\)使第......
  • AcWing算法基础课笔记——高斯消元
    高斯消元用来求解方程组a11x1+......
  • 高斯消元学习笔记
    引入高斯-约当消元法(Gauss–Jordanelimination)是求解线性方程组的经典算法,它在当代数学中有着重要的地位和价值,是线性代数课程教学的重要组成部分。高斯消元法除了用于线性方程组求解外,还可以用于行列式计算、求矩阵的逆,以及其他计算机和工程方面。过程一个经典的问题,给定一......
  • 高斯消元学习笔记
    高斯消元学习笔记其实这个主题能够复活主要还是粘了\(\text{LGV}\)引理的光,不然我还不知道高斯消元其实不光能求解线性方程组。求解线性方程组这个只能说是典中典了,我不相信没有一个人的高斯消元不是从这里开始的。我们考虑求解线性方程组的本质:将每一个式子所有未知数前都......
  • 高斯消元学习笔记——P304题解
    如果你觉得这篇太啰嗦问题[SDOI2006]线性方程组题目描述已知\(n\)元线性一次方程组。\[\begin{cases}a_{1,1}x_1+a_{1,2}x_2+\cdots+a_{1,n}x_n=b_1\\a_{2,1}x_1+a_{2,2}x_2+\cdots+a_{2,n}x_n=b_2\\\cdots\\a_{n,1}x_1+a_{n,2}x......
  • 高斯消元
    不会高斯消元/kk。高斯消元,就是通过某种操作消元得到答案。eg:\[\begin{cases}3x+5y+z=20\\x-2y+3z=19\\2x-6y+z=6\end{cases}\]把它变成增广矩阵形式:\[\begin{bmatrix}3&5&1&&20\\1&-2&3&&19\\2&-6&1&&6\end{bmatrix}\]怎么把\(x\)消掉......