关于高斯消元和代入消元的一点问题
  • 板块学术版
  • 楼主SDNetFriend
  • 当前回复5
  • 已保存回复5
  • 发布时间2021/9/9 08:37
  • 上次更新2023/11/4 07:14:55
查看原帖
关于高斯消元和代入消元的一点问题
206258
SDNetFriend楼主2021/9/9 08:37

写了两个本来是高斯消元的题 P3232 P3389

但实际上蒟蒻记不住高斯消元的流程,就胡了个代入消元,然后看起来正确性没什么问题

然后翻看下代码感觉两种方式复杂度几乎一样,但个人觉得代入消元好理解得多,那为什么不能用代入消元代替高斯消元(雾),大概就是每次把第 i 行钦定成 b+k1f1+..+0fi+..+knfn=fib+k_1f_1+..+0f_i+..+k_nf_n=f_i 的形式,然后向下代

附代码(f[i][0] 表示第 i 行的常数项)

inline bool solve(){
	for(rint i=1;i<=n;++i){
		double x=-f[i][i];
		f[i][i]=0;
		for(rint j=0;j<=n;++j)
			f[i][j]/=x;
		for(rint j=i+1;j<=n;++j){
			double y=f[j][i];
			f[j][i]=0;
			for(rint k=0;k<=n;++k)
				f[j][k]+=y*f[i][k];
		}
	}
	for(rint i=1;i<=n;++i)
		if(f[n][i]!=0)
			return false;
	for(rint i=n;i>=1;--i){
		for(rint j=i+1;j<=n;++j){
			double x=f[i][j];
			f[i][j]=0;
			f[i][0]+=x*f[j][0];
		}
	}
	return true;
}
2021/9/9 08:37
加载中...