例：ZOJ3645
题意：高斯消元模板题(浮点型)
/**
高斯消元求解线性方程组.
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
///高斯消元模板
const double eps = 1e-12;
const int Max_M = 15; ///m个方程,n个变量
const int Max_N = 15;
int m, n;
double Aug[Max_M][Max_N+1]; ///增广矩阵
bool free_x[Max_N]; ///判断是否是不确定的变元
double x[Max_N]; ///解集
int sign(double x){ return (x>eps) - (x<-eps);}
/**
返回值:
-1 无解
0 有且仅有一个解
>=1 有多个解,根据free_x判断哪些是不确定的解
*/
int Gauss()
{
int i,j;
int row,col,max_r;
for(row=0,col=0; row<m&&col<n; row++,col++)
{
max_r = row;
for(i = row+1; i < m; i++) ///找到当前列所有行中的最大值(做除法时减小误差)
{
if(sign(fabs(Aug[i][col])-fabs(Aug[max_r][col]))>0)
max_r = i;
}
if(max_r != row) ///将该行与当前行交换
{
for(j = row; j < n+1; j++)
swap(Aug[max_r][j],Aug[row][j]);
}
if(sign(Aug[row][col])==0) ///当前列row行以下全为0(包括row行)
{
row--;
continue;
}
for(i = row+1; i < m; i++)
{
if(sign(Aug[i][col])==0)
continue;
double ta = Aug[i][col]/Aug[row][col];
for(j = col; j < n+1; j++)
Aug[i][j] -= Aug[row][j]*ta;
}
}
for(i = row; i < m; i++) ///col=n存在0...0,a的情况,无解
{
if(sign(Aug[i][col]))
return -1;
}
if(row < n) ///存在0...0,0的情况,有多个解,自由变元个数为n-row个
{
for(i = row-1; i >=0; i--)
{
int free_num = 0; ///自由变元的个数
int free_index; ///自由变元的序号
for(j = 0; j < n; j++)
{
if(sign(Aug[i][j])!=0 && free_x[j])
free_num++,free_index=j;
}
if(free_num > 1) continue; ///该行中的不确定的变元的个数超过1个,无法求解,它们仍然为不确定的变元
///只有一个不确定的变元free_index,可以求解出该变元,且该变元是确定的
double tmp = Aug[i][n];
for(j = 0; j < n; j++)
{
if(sign(Aug[i][j])!=0 && j!=free_index)
tmp -= Aug[i][j]*x[j];
}
x[free_index] = tmp/Aug[i][free_index];
free_x[free_index] = false;
}
return n-row;
}
///有且仅有一个解,严格的上三角矩阵(n==m)
for(i = n-1; i >= 0; i--)
{
double tmp = Aug[i][n];
for(j = i+1; j < n; j++)
if(sign(Aug[i][j])!=0)
tmp -= Aug[i][j]*x[j];
x[i] = tmp/Aug[i][i];
}
return 0;
}
///模板结束
int main()
{
int i,j;
int t;
double a[12][12];
scanf("%d",&t);
while(t--)
{
memset(Aug,0.0,sizeof(Aug));
memset(x,0.0,sizeof(x));
memset(free_x,1,sizeof(free_x)); ///都是不确定的变元
for(i = 0; i < 12; i++)
for(j = 0; j < 12; j++)
scanf("%lf",&a[i][j]);
double sum=0;
for(int i=0;i<11;i++)
sum+=a[11][i]*a[11][i];
for(int i=0;i<11;i++)
{
for(int j=0;j<11;j++)
{
Aug[i][j]=2*(a[i][j]-a[11][j]);
Aug[i][11]+=a[i][j]*a[i][j];
}
Aug[i][11]+=-a[i][11]*a[i][11]+a[11][11]*a[11][11]-sum;
}
m = n = 11;
Gauss();
for(int i = 0; i < n; i++)
{
printf("%.2lf",x[i]);
printf("%c",i==n-1?'\n':' ');
}
}
return 0;
}
开关问题POJ1830
题意：有n(n<29)个开关,每个开关的状态用0/1表示关/开.
开关之间存在着某些联系,比如打开或关闭某个开关,与它相关的某些开关也会发生变化,即原来为开/关,现在变为关/开.
经过若干次操作后,由初始状态为s变为末端状态为t(s,t均为长度为n的01串).
问有多少种方法可以将s变为t,每个开关最多只能动一次,不考虑开关操作的顺序.
输入格式:
开关个数n
初始状态s和目标状态t(01串)
若干整数对(i,j),表示对开关i的操作,开关j的状态也会发生改变.
解:
利用矩阵思想A*x=b,其中A为n*n的变换矩阵，x,b均为列矩阵;
x 表示对n个开关的操作,1表示动它,0表示不动它,显然最后是求解的个数.
A[i][j]=1表示若操作开关j会引起i的变化.
b 表示若开关i的初始状态和目标状态不同,则b[i]=1,否则b[i]=0.即b表示最终所有开关的变化状态.0为不变,1为变.
b[i] = ^(A[i][j]*x[j]),0<=j<=n.
**********理解*********
考虑最终开关i状态的变化:
j!=i
若x[j]=1, 表示对开关j进行操作
若A[i][j]=1,表示开关j对i有影响,即A[i][j]*x[j]=1,此时开关i状态改变;
若A[i][j]=0,表示虽然对j操作,但开关j对i却没有影响,即A[i][j]*x[j]=0,此时开关i状态不变;
若x[j]=0, 表示不对开关j操作,显然对i的状态也没有影响,即A[i][j]*x[j]=0,此时开关i状态不变.
异或方程组的消元类似于普通方程组的消元：
若有ax + by = p，cx + dy = q，则有(a+c)x + (b+d)y = p+q；
同理：若有ax ^ by = p，cx ^ dy = q，则有(a^c)x ^ (b^d)y = p^q。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
///高斯消元模板
const int Max_M = 35;
const int Max_N = 35;
int Aug[Max_M][Max_N];
int m,n; ///m个方程,n个未知数
int Gauss()
{
int i,j;
int max_r,row,col;
for(col=0,row=0; row<m && col<n; row++,col++)
{
max_r = row;
for(i = row+1; i < m; i++)
{
if(Aug[i][col] > Aug[max_r][col])
max_r = i;
}
if(max_r != row)
{
for(j = row; j < n+1; j++)
swap(Aug[max_r][j],Aug[row][j]);
}
if(Aug[row][col]==0)
{
row--;
continue;
}
for(i = row+1; i < m; i++)
{
if(Aug[i][col]==0)
continue;
for(j = col; j < n+1; j++)
Aug[i][j] ^= Aug[row][j];
}
}
for(i = row; i < m; i++)
{
if(Aug[i][col] != 0)
return -1;
}
return 1<<(n-row); ///n-row个变元,只有0/1两种取值
}
///end
int main()
{
int i,j;
int t;
int nn;
int start[30],end[30];
scanf("%d",&t);
while(t--)
{
m = n = 0;
memset(Aug,0,sizeof(Aug));
scanf("%d",&nn);
for(i = 0; i < nn; i++)
scanf("%d",&start[i]);
for(i = 0; i < nn; i++)
scanf("%d",&end[i]);
while(true)
{
scanf("%d %d",&i,&j);
if(!i&&!j)
break;
Aug[j-1][i-1] = 1;
}
n = m = nn;
for(i = 0; i < n; i++)
{
Aug[i][i] = 1;
Aug[i][n] = start[i]^end[i];
}
int ret = Gauss();
if(ret==-1)
printf("Oh,it's impossible~!!\n");
else
printf("%d\n",ret);
}
return 0;
}
ps: 其实当时看到这题是用双向枚举过的，正向和逆向的复杂度为O(2^(n/2))，对于n比较小的也足够了，大了还是得用高斯消元解异或方程。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
const int MaxN = 30;
int nn; ///开关数<29
int start,end;
int ch[MaxN]; ///chp[i]表示拨动开关i,会引发的状态改变
bool flag[MaxN][MaxN]; ///防止输入对IJ重复
map<int,int> vis; ///记录状态及出现的次数
map<int,int>::iterator mit;
int result; ///次数
///枚举1..mid开关的所有情况,共2^mid种
void Forward(int mid)
{
int i,j,k;
int Max = 1<<mid;
for(i = 0; i < Max; i++)
{
j = i;
k = 0;
int now = start;
while(j)
{
if(j&1)
now = now ^ ch[k];
j >>= 1;
k++;
}
mit = vis.find(now);
if(mit == vis.end())
vis.insert(make_pair(now,1));
else
mit->second++;
}
}
void Backward(int mid)
{
int i,j,k;
int Max = 1<<(nn-mid);
for(i = 0; i < Max; i++)
{
j = i;
k = mid;
int now = end;
while(j)
{
if(j&1)
now = now ^ ch[k];
j >>= 1;
k++;
}
mit = vis.find(now);
if(mit!=vis.end())
result += mit->second;
}
}
int main()
{
int i,j;
int t;
scanf("%d",&t);
while(t--)
{
result = 0;
start = end = 0;
vis.clear();
memset(flag,0,sizeof(flag));
scanf("%d",&nn);
for(i = 0; i < nn; i++)
ch[i] = 1<<i,flag[i][i]=true;
for(i = 0; i < nn; i++)
{
scanf("%d",&j);
if(j) start += 1<<i;
}
for(i = 0; i < nn; i++)
{
scanf("%d",&j);
if(j) end += 1<<i;
}
while(true)
{
scanf("%d %d",&i,&j);
if(!i&&!j)
break;
if(!flag[i-1][j-1])
ch[i-1] += 1<<(j-1),flag[i-1][j-1]=true;
}
Forward(nn/2);
Backward(nn/2);
if(result==0)
printf("Oh,it's impossible~!!\n");
else
printf("%d\n",result);
}
return 0;
}
- 大小: 21.3 KB
分享到：
相关推荐
在数值计算方法中用高斯消元法和列选主元来求线性方程组的解的C++源代码
### 数值分析——高斯消元法解线性方程组 #### 一、引言 高斯消元法是一种非常重要的数值计算方法，广泛应用于线性方程组的求解之中。它不仅可以用于理论研究，也是实际工程计算中解决线性问题的基础工具之一。...
本文将详细探讨如何利用C++编程语言实现这一方法，并结合实验二——高斯消元法的实践过程，深入解析相关知识点。 线性方程组通常表示为以下形式： \[ Ax = b \] 其中，\( A \) 是一个 \( n \times n \) 的系数矩阵...
### 高斯列主元消去法解线性方程组——课程设计报告知识点解析 #### 一、引言 本课程设计报告旨在探讨利用**高斯列主元消去法**来解决线性方程组的方法及其实施过程。线性方程组是数学中的一个重要概念，广泛应用...
高斯-赛德尔迭代法（Gauss-Seidel Iteration Method）是改进版的高斯消元法，它在每次迭代中不仅用到了当前未知数的最新估计值，还利用了相邻未知数的最新值，从而加快了收敛速度。与简单迭代法相比，高斯-赛德尔...
根据给定的信息，本文将详细解释使用C++解决线性方程组的几种方法，包括克莱默法则（Cramer's Rule）、高斯消元法（Gauss Elimination）、全高斯消元法（Full Gauss Elimination）以及杜利特分解法（Doolittle ...
### 高斯列主消元法解n乘n线性方程组 #### 知识点概述 在数值分析和线性代数中，高斯列主消元法（Gaussian Elimination with Partial Pivoting）是一种求解线性方程组的方法。这种方法通过一系列的行操作将矩阵...
本实验报告详细介绍了高斯消去法中的一个变种——Gauss列主元消去法，并阐述了如何利用MATLAB软件实现该算法，以解决线性方程组的问题。下面是关于该报告的详细知识点： 1. 高斯消去法基础 高斯消去法是一种通过行...
本实验旨在通过两种不同的方法——顺序消元法和列主消元法——来解决线性方程组的问题，并通过C++编程实现这两种方法。 #### 实验方法 ##### 顺序消元法 顺序消元法是一种简化线性方程组求解过程的方法，通过一...
高斯列主消元法 LU分解法 迭代法求解线性方程组 高斯列主消元法 LU分解法 迭代法求解线性方程组 高斯列主消元法 LU分解法 迭代法求解线性方程组 高斯列主消元法 LU分解法 迭代法求解线性方程组 高斯列主消元法 LU...
线性方程组是许多科学计算的基础，列主消元法（也称为高斯消元法）是一种经典且实用的方法，用于求解这类方程组。本篇将详细介绍列主消元法以及如何使用C++编程语言实现它。 列主消元法是基于矩阵的变换，目的是将...
这种方法是高斯消元法的迭代版本，适用于处理稀疏矩阵，因为其在计算过程中仅更新部分元素，从而减少了计算量。以下是对这个主题的详细阐述： 一、线性方程组与高斯-赛德尔迭代法 线性方程组是一组形如Ax=b的方程...
在实际应用中，列主元LU分解通常结合简化的高斯消元法（Gauss-Elimination with Partial Pivoting，简称GEPP），形成列主元简化的高斯消元法（Gauss-Elimination with Complete Pivoting，简称GECPP）。这种方法可以...
通过本编程实验，加深对解线性方程组的直接法——高斯列主消元法、LU分解法、追赶法、LDLT分解法的构造过程的理解；实现高斯-约当消元法求逆矩阵。 自选线性方程组，分别编制高斯列主元消元法和LU分解法的功能模块...
高斯消元法是一种通过行变换将矩阵化为阶梯形或简化阶梯形的方法，进而求解线性方程组。其基本步骤包括前向消元和后向替代两个阶段。前向消元的目标是通过一系列行操作，使系数矩阵化为上三角矩阵；而后向替代则是...
对于求解线性方程组，有许多不同的方法，包括高斯消元法、LU 分解、迭代法等。本文将重点介绍一种特别的方法——全主元消去法（也称为全主元高斯消元法），并提供基于 C# 的实现。 #### 全主元消去法概述 全主元...
高斯消元法是线性代数中求解线性方程组的一种基本算法，尤其在信息学竞赛中被广泛运用。线性方程组可以用矩阵的形式表示，增广矩阵则是将系数矩阵与结果向量合并在一起形成的矩阵。高斯消元法通过一系列行变换，将...
当线性方程组规模较大时，直接求解方法如高斯消元法可能会面临计算量大、效率低的问题。此时，迭代法成为了一种实用的选择。本文将重点讨论两种常用的迭代法——雅可比迭代法（Jacobi Iteration）和高斯-赛德尔迭代...
在处理多元一次方程组时，我们通常会使用消元法、高斯-约旦消元法、克拉默法则或矩阵求逆等方法。环星计算器利用这些理论，为用户提供了解决复杂方程组的有效手段。 首先，消元法是通过加减乘除操作将方程组转换为...
在本章中，我们将深入探讨线性代数中的一个核心主题——解线性方程组的直接法。直接法是一种通过一系列数学运算直接求解线性方程组的方法，与迭代法不同，它通常能给出精确解，且适用于各种规模的方程组。在实际应用...