nefu503矩阵求解+十进制高斯消元

本是古典何须时尚 2022-07-15 13:53 172阅读 0赞

nefu503矩阵求解+高斯消元：[http://acm.nefu.edu.cn/JudgeOnline/problemShow.php?problem\_id=503][http_acm.nefu.edu.cn_JudgeOnline_problemShow.php_problem_id_503]

题目描述：

### 矩阵求解 ###

#### Problem:503 ####

#### Time Limit:1000ms ####

#### Memory Limit:65536K ####

### Description ###

给你系数矩阵和增广矩阵，让你求出矩阵代表方程的解，有唯一解直接输出就行，没解输出"no sovle!"，有多个解请输出"more sovle!".

### Input ###

数据有多组，每组第1行为N,表示是N行N列的矩阵，接下来输入N行每行N个系数，最后1行为这N行方程对应的值（Bi）.

### Output ###

有唯一解直接输出就行，没解输出"no sovle!"，有多个解请输出"more sovle!".

### Sample Input ###

5
    3 1 -1 2 1
    1 1 1 1 1
    -1 1 2 1 -2
    1 -1 -1 1 1
    3 2 1 1 1
    -2 3 10 -7 7

### Sample Output ###

1 2 3 -1 -2

题目分析：

求解十进制的线性方程组，注意此题要用long long类型，防止数据有溢出~

代码实现：

#include <iostream>
    #include <cstdio>
    
    using namespace std;
    
    const long long maxn=500;
    
    long long a[maxn][maxn+1],x[maxn];//a 是系数矩阵和增广矩阵，x 是最后存放的解
    // a[][maxn]中存放的是方程右面的值（bi）
    long long equ,var;//equ 是系数阵的行数，var 是系数矩阵的列数（变量的个数）
    long long free_num,ans=100000000;
    long long abs1(long long num) //取绝对值
    {
        if (num>=0) return num;
        else
            return -1*num;
    }
    void Debug(void) //调试输出，看消元后的矩阵值，提交时，就不用了
    {
        long long i, j;
        for (i = 0; i < equ; i++)
        {
            for (j = 0; j < var + 1; j++)
            {
                cout << a[i][j] << " ";
            }
            cout << endl;
        }
        cout << endl;
    }
    inline long long gcd(long long a, long long b) //最大公约数
    {
        long long t;
        while (b != 0)
        {
            t = b;
            b = a % b;
            a = t;
        }
        return a;
    }
    inline long long lcm(long long a, long long b) //最小公倍数
    {
        return a * b / gcd(a, b);
    }
    void swap(long long &a,long long &b)
    {
        long long temp=a;    //交换2 个数
        a=b;
        b=temp;
    }
    long long Gauss()
    {
        long long k,col = 0; //当前处理的列
        for(k = 0; k < equ && col < var; ++k,++col)
        {
            long long max_r = k;
            for(long long i = k+1; i < equ; ++i)
                if(abs1(a[i][col]) > abs1(a[max_r][col]))//注意要求绝对值
                    max_r = i;
            if(max_r != k)
            {
                for(long long i = k; i < var + 1; ++i)
                    swap(a[k][i],a[max_r][i]);
            }
            if(a[k][col] == 0)
            {
                k--;
                continue;
            }
            for(long long i = k+1; i < equ; ++i)
            {
                if(a[i][col] != 0)
                {
                    long long LCM = lcm(a[i][col],a[k][col]);
                    long long ta = LCM/a[i][col], tb = LCM/a[k][col];
                    if(abs1(a[i][col])*abs1(a[k][col]) < 0)<span style="font-size: 13.3333px; font-family: Arial, Helvetica, sans-serif;">//注意要求绝对值</span>
                        tb = -tb;
                    for(long long j = col; j < var + 1; ++j)
                        a[i][j] = ( (a[i][j]*ta) - (a[k][j]*tb) ) ; //a[i][j]只有0 和1 两种状态
                }
            }
        }
    
    //上述代码是消元的过程，行消元完成
    //解下来2 行，判断是否无解
    //注意K 的值，k 代表系数矩阵值都为0 的那些行的第1 行
        for(long long i = k; i < equ; ++i)
            if(a[i][col] != 0) return -1; // 无解返回-1
    //Debug();
    //唯一解或者无穷解,k<=var
    //var-k==0 唯一解；var-k>0 无穷多解，自由解的个数=var-k
    //能执行到这，说明肯定有解了，无非是1 个和无穷解的问题。
    //下面这几行很重要，保证秩内每行主元非0，且按对角线顺序排列，就是检查列
        for(long long i = 0; i <equ; ++i)//每一行主元素化为非零
            if(!a[i][i])
            {
                long long j;
                for(j = i+1; j<var; ++j)
                    if(a[i][j])
                        break;
                if(j == var)
                    break;
                for(long long k = 0; k < equ; ++k)
                    swap(a[k][i],a[k][j]);
            }
    // ----处理保证对角线主元非0 且顺序，检查列完成
    // free_num=k;
        if (var-k>0)
        {
    //无穷多解，先枚举解，然后用下面的回带代码进行回带；
    //这里省略了下面的回带的代码；不管唯一解和无穷解都可以回带，只不过无穷解
    //回带时，默认为最后几个自由变元=0 而已。
            return 1;
        }
        if (var-k==0)//唯一解时
        {
    //下面是回带求解代码，当无穷多解时，最后几行为0 的解默认为0；
            for(long long i = k-1; i >= 0; --i) //从消完元矩阵的主对角线非0 的最后1 行，开始往
    //回带
            {
                long long tmp = a[i][var] ;
                for(long long j = i+1; j < var; ++j) //x[i]取决于x[i+1]--x[var]啊，所以后面的解对前面的解有影响。
                    if(a[i][j] != 0)
                        tmp = ( tmp - a[i][j]*x[j]  ) ;
    //if (a[i][i]==0) x[i]=tmp; //最后的空行时，即无穷解得
    //else
                x[i] = tmp/a[i][i]; //上面的正常解
            }
    //回带结束了
            return 0;
        }
    }
    
    int main()
    {
        long long n;
        while(scanf("%lld",&n)!=EOF)
        {
            equ=var=n;
            for(long long i=0; i<n; i++)
            {
                for(long long j=0; j<n; j++)
                {
                    scanf("%lld",&a[i][j]);
                }
            }
            for(long long i=0; i<n; i++)
            {
                scanf("%lld",&a[i][n]);
            }
            //Debug();
            long long kkk=Gauss();
            if(kkk==0)
            {
                printf("%lld",x[0]);
                for(long long i=1; i<var; i++)
                {
                    printf(" %lld",x[i]);
                }
                printf("\n");
            }
            else if(kkk==1)
            {
                printf("more sovle!\n");
            }
            else
            {
                printf("no sovle!\n");
            }
        }
        return 0;
    }

[http_acm.nefu.edu.cn_JudgeOnline_problemShow.php_problem_id_503]: http://acm.nefu.edu.cn/JudgeOnline/problemShow.php?problem_id=503