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

高斯消元法

时间:2023-01-29 16:47:55浏览次数:43  
标签:xor int cdots 高斯消 operatorname 元法 curi

高斯消元法

心情不好,来写博客...

思想

一种通过消元求解线性方程组的方法,时间复杂度为 \(n^3\)

和普通的消元法无二,选定一个自变量为主元,将一行的主元系数化为一,再通过乘法消去其他行含有该元的项。

实现细节

for(int j=0;j<n;j++){
	int t;
	for(t=curi;t<n;t++)
		if(fabs(a[t][j])>eps)break;//对于浮点形的运算,一般定义小于一个常数就算是0了,这个常数视情况一般是1e-6
	if(t==n)continue;//主元 not found,no sulution
	for(int i=j;i<=n;i++)
		swap(a[t][i],a[curi][i]);
	for(int i=n;i>=j;i--)//这里要反着来,因为a[curi][j]的值还会用到
		a[curi][i]/=a[curi][j];
	for(int i=0;i<n;i++)
		if(i!=curi)//本行不需要继续修改
			for(int k=n;k>=j;k--)
				a[i][k]-=a[curi][k]*a[i][j];//同样的原因
	curi++; 
}

拓展

容易发现,xor的运算也有同样的消元性质 \(a\oplus b \oplus b=a\)

因此可以利用高斯消元解异或方程组 模板题见外星千足虫。

异或方程组也就是

\(\begin{cases} a_{1,1}x_1 \operatorname{xor} a_{1,2}x_2\operatorname{xor}\cdots\operatorname{xor}a_{1,n}x_n &\equiv b_1 \pmod 2&&(1)\\ a_{2,1}x_1 \operatorname{xor} a_{2,2}x_2\operatorname{xor}\cdots\operatorname{xor}a_{2,n}x_n&\equiv b_2 \pmod 2&&(2)\\ \cdots&\cdots&&\cdots\\ a_{m,1}x_1 \operatorname{xor} a_{m,2}x_2\operatorname{xor}\cdots\operatorname{xor}a_{m,n}x_n&\equiv b_m \pmod 2&&(m) \end{cases}\)

for(int i=1;i<=n;i++){
	now=i;
	while(now<=m and !a[now][i])
		now++;
	if(now==m+1){
		printf("Cannot Determine");
		return 0;
	}
	ans=max(ans,now);
	if(now!=i)
		swap(a[now],a[i]);//怎么好像变简单了?因为异或的次数只有1和0,那么可以略过系数化为一这一步了
	for(int j=1;j<=m;j++){
		if(j==i)continue;
		if(!a[j][i])continue;
		a[j]^=a[i];
	}
}

标签:xor,int,cdots,高斯消,operatorname,元法,curi
From: https://www.cnblogs.com/Hushizhi/p/17073089.html

相关文章

  • 高斯消元
    简述高斯消元法(Gauss-Jordanelimination)是求解线性方程组的经典算法,它在当代数学中有着重要的地位和价值,是线性代数课程教学的重要组成部分。高斯消元法除了用于线性方......
  • 高斯-约旦消元法详解
    注:本文章假设读者已经学会基础的高斯消元法引入高斯约旦消元法是高斯消元法的一种,一般用于求解线性方程组。对于一个线性方程组\[\begin{cases}x+3y+4z=5\\x......
  • 高斯-约旦消元法详解
    注:本文章假设读者已经学会基础的高斯消元法引入高斯约旦消元法是高斯消元法的一种,一般用于求解线性方程组。对于一个线性方程组\[\begin{cases}x+3y+4z=5\\x......
  • C++ 数学与算法系列之高斯消元法求解线性方程组
    1.前言什么是消元法?消元法是指将多个方程式组成的方程组中的若干个变量通过有限次地变换,消去方程式中的变量,通过简化方程式,从而获取结果的一种解题方法。消元法主要有代......
  • 数值分析·学习 | 解线性方程组的直接方法(高斯消去法以及LU求解)matlab实现
    ​ 目录一、前言:二、算法描述:三、实现代码:1、高斯消去法:2、高斯消去法-列主元消去法:3、LU分解:4、求逆矩阵:四、总结:一、前言:个人学习内容分享二、算法描述:1......
  • 高斯消元+组合数+卡特兰数
    高斯消元+组合数+卡特兰数高斯消元\(O(n^3)\)的线性时间内求解n元线性方程组\[\\\begin{cases}\a_{11}x_1+a_{12}x_2+...+a_{1n}x_n=b_1\\\a_{21}x_1+a_{22}x_2+.......
  • 算法学习笔记(39)——高斯消元
    高斯消元高斯消元高斯消元解线性方程组高斯消元解异或线性方程组高斯消元解线性方程组通过初等行变换把增广矩阵化为阶梯型矩阵,并回代得到方程的解适用于求解......
  • 高斯消元与线性基
    高斯消元与线性基Guass—约旦消元消元算法简介:这是求解线性方程组(也就是M个N元一次方程组)的方法思想:我们可以把方程组看作一个系数矩阵例如:\[\left\{\begin{aligned......
  • 高斯消元&高斯约旦消元
    高斯消元就是上三角,然后再回代。高斯约旦消元就是消的时候直接变成对角线了,你选取当前主元,然后把其他的都消去这个元。一般来说就写后者。注意二者都要特判自由元,但常数......
  • 高斯消元
    0x00背景高斯消元是求线性方程组的标准方法,原理和代码都不难0x01基本操作一个线性方程组有\(m\)个一次方程,\(n\)个变量,把所有系数都写成一个\(m\)行\(n\)列的矩阵,......