#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=50; int equ,var; //行数，列数 int a[maxn][maxn]; //增广矩阵 int x[maxn]; //解集 bool free_x[maxn]; //标记是否是不确定的变元 void Debug(){ int i,j; for(i=0;i<equ;i++){ for(j=0;j<var+1;j++) printf("%d ",a[i][j]); printf("\n"); } printf("\n"); } int gcd(int a,int b){ return b==0?a:gcd(b,a%b); } int lcm(int a,int b){ return a/gcd(a,b)*b; //先除后乘防溢出 } // 高斯消元法解方程组(Gauss-Jordan elimination).(-2表示有浮点数解，但无整数解， //-1表示无解，0表示唯一解，大于0表示无穷解，并返回自由变元的个数) //有equ个方程，var个变元。增广矩阵行数为equ,分别为0到equ-1,列数为var+1,分别为0到var. int Gauss(){ int i,j,k; int max_row; // 当前这列绝对值最大的行 int col; //当前处理的列 int ta,tb; int LCM; int tmp; int free_x_num; int free_x_index; for(int i=0;i<=var;i++){ x[i]=0; free_x[i]=true; } //转换为阶梯阵. col=0; // 当前处理的列 for(k=0;k<equ && col<var;k++,col++){ // 枚举当前处理的行.找到该col列元素绝对值最大的那行与第k行交换.(为了在除法时减小误差) max_row=k; for(i=k+1;i<equ;i++) if(abs(a[i][col])>abs(a[max_row][col])) max_row=i; if(max_row!=k){ // 与第k行交换 for(j=k;j<var+1;j++) swap(a[k][j],a[max_row][j]); } if(a[k][col]==0){ // 说明该col列第k行以下全是0了，则处理当前行的下一列. k--; continue; } for(i=k+1;i<equ;i++){ // 枚举要删去的行. if(a[i][col]!=0){ LCM=lcm(abs(a[i][col]),abs(a[k][col])); ta=LCM/abs(a[i][col]); tb=LCM/abs(a[k][col]); if(a[i][col]*a[k][col]<0) //异号的情况是相加 tb=-tb; for(j=col;j<var+1;j++) a[i][j]=a[i][j]*ta-a[k][j]*tb; } } } Debug(); // 1. 无解的情况: 化简的增广阵中存在(0, 0, ..., a)这样的行(a != 0). for(i=k;i<equ;i++) // 对于无穷解来说，如果要判断哪些是自由变元，那么初等行变换中的交换就会影响，则要记录交换. if(a[i][col]!=0) return -1; // 2. 无穷解的情况: 在var * (var + 1)的增广阵中出现(0, 0, ..., 0)这样的行，即说明没有形成严格的上三角阵. // 且出现的行数即为自由变元的个数. if(k<var){ for(i=k-1;i>=0;i--){ // 首先，自由变元有var - k个，即不确定的变元至少有var - k个. // 第i行一定不会是(0, 0, ..., 0)的情况，因为这样的行是在第k行到第equ行. // 同样，第i行一定不会是(0, 0, ..., a), a != 0的情况，这样的无解的. free_x_num=0; // 用于判断该行中的不确定的变元的个数，如果超过1个，则无法求解，它们仍然为不确定的变元. for(j=0;j<var;j++) if(a[i][j]!=0 && free_x[j]){ free_x_num++; free_x_index=j; } if(free_x_num>1) // 无法求解出确定的变元. continue; tmp=a[i][var]; // 说明就只有一个不确定的变元free_index，那么可以求解出该变元，且该变元是确定的. for(j=0;j<var;j++) if(a[i][j]!=0 && j!=free_x_index) tmp-=a[i][j]*x[j]; x[free_x_index]=tmp/a[i][free_x_index]; // 求出该变元. free_x[free_x_index]=0; // 该变元是确定的. } return var-k; // 自由变元有var - k个. } // 3. 唯一解的情况: 在var * (var + 1)的增广阵中形成严格的上三角阵. // 计算出Xn-1, Xn-2 ... X0. for(i=var-1;i>=0;i--){ tmp=a[i][var]; for(j=i+1;j<var;j++) if(a[i][j]!=0) tmp-=a[i][j]*x[j]; if(tmp%a[i][i]!=0) // 说明有浮点数解，但无整数解. return -2; x[i]=tmp/a[i][i]; } return 0; } int main(){ freopen("input.txt","r",stdin); while(~scanf("%d%d",&equ,&var)){ memset(a,0,sizeof(a)); for(int i=0;i<equ;i++) for(int j=0;j<var+1;j++) scanf("%d",&a[i][j]); int free_num=Gauss(); if(free_num==-1) printf("无解\n"); else if(free_num==-2) printf("有浮点数解，无整数解!\n"); else if(free_num>0){ printf("无穷多解! 自由变元个数为%d\n", free_num); for(int i=0;i<var;i++){ if(free_x[i]) printf("x%d 是不确定的\n",i+1); else printf("x%d: %d\n",i+1,x[i]); } } else{ for(int i=0;i<var;i++) printf("x%d: %d\n", i + 1, x[i]); } printf("\n"); } return 0; }
例如：输入：
即：
4 4
1 -1 -2 -5 10
-2 7 6 -12 6
3 -2 -5 -17 31
-5 -2 9 27 -63
输出：
