广义表应用

广义表的应用 高斯消元法 实验报告

(2011-05-25 10:24:16)

广义表的应用

一、问题描述:

应用高斯消元法求解方程组并验证其正确性。

——输入：方程组，请自己设计输入格式

——输出：方程组的解，包括无解及有无限解等。

——提示：应以求得的解代入原方程组验证其正确性。

二、算法分析:

高斯消元法，是线性代数中的一个算法，可用来求解线性方程组，并可以求出矩阵的秩，以及求出可逆方阵的逆矩阵。

高斯消元法的原理是：

若用初等行变换将增广矩阵 化为 ，则AX = B与CX = D是同解方程组。 所以我们可以用初等行变换把增广矩阵转换为行阶梯阵，然后回代求出方程的解。

介绍程序中高斯消元法的步骤：

(我们设方程组中方程的个数为equ ，变元的个数为var ，注意：一般情况下是n 个方程，n 个变元，但是有些题目就故意让方程数与变元数不同)

1. 把方程组转换成增广矩阵。

2. 利用初等行变换来把增广矩阵转换成行阶梯阵。

枚举k 从0到equ – 1，当前处理的列为col(初始为0) ，每次找第k 行以下(包括第k 行) ，col 列中元素绝对值最大的列与第k 行交换。如果col 列中的元素全为0，那么则处理col + 1列，k 不变。

3. 转换为行阶梯阵，判断解的情况。

① 无解

当方程中出现(0, 0, …, 0, a)的形式，且a != 0时，说明是无解的。

② 唯一解

条件是k = equ，即行阶梯阵形成了严格的上三角阵。利用回代逐一求出解集。

③ 无穷解。

条件是k

这里单独介绍下这种解法：

首先，自由变元有var - k个，即不确定的变元至少有var - k个。我们先把所有的变元视为不确定的。在每个方程中判断不确定变元的个数，如果大于1个，则该方程无法求解。如果只有1个变元，那么该变元即可求出，即为确定变元。

以上介绍的是求解整数线性方程组的求法，复杂度是O(n3)。浮点数线性方程组的求法类似，但是要在判断是否为0时，加入EPS ，以消除精度问题。

三、程序代码：

头文件:

#ifndef Head_h

#define Head_h

#include

#include

#include

#include

typedef float Equation[30][30];

typedef int Status;

typedef int Elemtype;

#define ok 1

#define False 0

#endif

源文件:

#include"Head.h"

Status CreateEQ(Elemtype VariableNum,Elemtype EqNum,Equation EQ)//输入方程

{

}

Status PrintEQ(Elemtype VariableNum,Elemtype EqNum,Equation EQ)//打印方程

{ int Eq_i,Eq_j; for(Eq_j=0;Eq_j

} for(Eq_j=0;Eq_j

Status ChangeEQ(Elemtype Bottom,Elemtype Top,Elemtype

VariableNum,Equation EQ)//交换行

{

int Eq_i,Eq_j; float Eq_temp; if(fabs(EQ[Bottom][Bottom])0.000001) {

}

} } } { } return ok; Eq_temp=EQ[Eq_i][Eq_j]; EQ[Eq_i][Eq_j]=EQ[Bottom][Eq_j]; EQ[Bottom][Eq_j]=Eq_temp; if(Eq_i>=Top) return False; return ok;

Status DealEQ(Elemtype Bottom,Elemtype Top,Elemtype

VariableNum,Equation EQ)//某一列初等行变换

{

int Eq_j,Eq_i; float Eq_cn; for(Eq_j=1;Eq_j

{

EQ[Bottom+Eq_j][Eq_i]=EQ[Bottom+Eq_j][Eq_i]-Eq_cn*EQ[Bottom][Eq_i];

}

Status PreChange(Elemtype VariableNum,Elemtype &EqNum,Equation EQ)//线性方程初等变换

{

int Eq_i,Eq_j,Eq_n,Eq_m; for(Eq_i=0;Eq_i

} } } if(Eq_j>=VariableNum+1) { } for(Eq_n=Eq_i;Eq_n0.000001) break; return ok;

Status GetResult(Elemtype VariableNum,Elemtype EqNum,Equation EQ)//求解方程

{

float Result[40]={0.0};

int Eq_j,Eq_i; if(VariableNum>EqNum) { printf("此线性方程组有无穷解！\n");

printf("也可能无解，由于都不能得出结果，\n在此不进行判断，请参照变换后的线性方程进行判断!\n");

} if(EqNum>VariableNum) { for(Eq_j=VariableNum-1;Eq_j

if(EQ[Eq_j][VariableNum]/EQ[Eq_j][VariableNum-1]!=EQ[Eq_j+1][VariableNum]/EQ[Eq_j+1][VariableNum-1])

} for(Eq_i=EqNum-1;Eq_i>=0;Eq_i--) } if(Eq_j

for(Eq_j=0;Eq_j

if((fabs(EQ[Eq_i][Eq_i])0.000001))

{ } printf("此线性方程无解！\n"); return ok;

if((fabs(EQ[Eq_i][Eq_i])

Result[Eq_i]=(EQ[Eq_i][VariableNum]-Eq_sum)/EQ[Eq_i][Eq_i]; { } printf("此线性方程无穷解！\n"); return ok;

} printf("线性方程的解如下：\n"); for(Eq_j=0;Eq_j

void main() {

Elemtype VariableNum, EqNum; char cn; Equation EQ;//存放方程的数组 printf("请输入线性方程组的变量个数和方程的个数："); scanf("%d%d",&VariableNum,&EqNum); printf("\n"); for(;;) { CreateEQ(VariableNum,EqNum,EQ); PrintEQ(VariableNum,EqNum,EQ); printf("输入方程是否正确（y/n):"); getchar(); scanf("%c",&cn);

} } getchar(); printf("\n"); if(cn=='Y'||cn=='y') break; PreChange(VariableNum,EqNum,EQ); printf("进行初等行变换后的方程为：\n"); PrintEQ(VariableNum,EqNum,EQ); GetResult(VariableNum,EqNum,EQ); system("pause");

四、运行结果：(自己运行吧, 呵呵!)

五、算法复杂度：

O(5n^2-9n+3)=O(5n^2)