做完了,发表下感想

P2455 [SDOI2006] 线性方程组

UnknownFrisk @ 2024-10-23 21:52:03

0 前言

终于啊,这道题我也是AC了(笑)
作为一名蒟蒻,也是花了很长时间呢,
虽然想过放弃,但还是坚持不看题解写完了。
这里也给各位还没AC的同志们提醒两点罢。

1 无解与无穷解的判断

如果各位有在#13里WA的,请一定要记住:
请一定要判断 所有 系数皆为零的行对应的常数项是否为零!
请一定要判断 所有 系数皆为零的行对应的常数项是否为零!
请一定要判断 所有 系数皆为零的行对应的常数项是否为零!

hack数据:

4
0 0 2 1 2
0 0 0 1 1
0 0 0 0 0
0 0 1 1 1

错误输出:0(判断第三行即结束)
正确输出:-1(全部判断)
建议:每次扫描到一个系数皆为零的行时都进行判断,若常数项为零继续判断,否则输出-1(即无解)并结束,全部扫描结束后输出0并结束。

2 关于选择主元时(全选主元,列主元)

如果各位有用高斯约当消去法的,那么在选取系数绝对值最大的元素(主元)的时候请不要忘记使用fabs,更不要使用abs(整数绝对值)。

3 最后

好吧,好像这些建议也不是那么有用罢。
最后代码附上。

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
#define DEBUG printf("Passing [%s] in LINE %d...\n",__FUNCTION__,__LINE__)
const int size = 101;
const double eps = 1e-10;
int /*未知数个数*/n,/*主元索引*/main_index,/*系数矩阵的秩*/rank = 0,ptr;
double A[size][size],b[size];
double temp_A[size],temp_b;
void to_one(int line,int unknown_index)
{
    //归一化 
    double k = A[line][unknown_index];
    for(int i = unknown_index; i <= n; i++)
        A[line][i] /= k;
    b[line] /= k;
    return;
}
void swap_line(int line1,int line2)
{
    //行交换
    if(line1 == line2)return;
    memcpy(temp_A,A[line1],(n+1)*sizeof(double));
    memcpy(A[line1],A[line2],(n+1)*sizeof(double));
    memcpy(A[line2],temp_A,(n+1)*sizeof(double));
    temp_b = b[line1];b[line1] = b[line2];b[line2] = temp_b;
    return;
}
void plus_multi(int line_to,int line_from,int main_index)
{
    //行变换步
    double k = - A[line_to][main_index];
    for(int i = line_from; i <= n; i++)
        A[line_to][i] += k * A[line_from][i];
    b[line_to] += k * b[line_from];
    return;
}
int choose_main_unknown(int unknown_index)
{
    //选择列主元(-1就是没找到) 
    double max = 0.0;
    int max_index = -1;
    for(int i = rank + 1; i <= n; i++)
    {
        if(fabs(A[i][unknown_index]) < eps) 
            continue;
        if(fabs(A[i][unknown_index]) > max)
        {
            max = fabs(A[i][unknown_index]);
            max_index = i;
        }
    }
    return max_index;
}
void print()
{
    //打印此时状态     
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
            printf("%lf ",A[i][j]);
        printf("%lf\n",b[i]); 
    }
    printf("\n");
}
bool find_zero_line()
{
    //异常解,查看全部零行
    //真为无解,假为无穷多解 
    int zero_line;
    bool flag = false;
    for(zero_line = 1; zero_line <= n; zero_line++)
    {
        for(ptr = 1; ptr <= n; ptr++)
            if(fabs(A[zero_line][ptr]) > eps)
                break;//非零行,跳过 
        if((ptr == n + 1) && (fabs(b[zero_line]) > eps))return true;//无解 
    }
    return false;//无穷多解 
}
int main()
{
    scanf("%d",&n);
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
            scanf("%lf",&(A[i][j]));
        scanf("%lf",b + i); 
    }
    for(int i = 1; i <= n; i++)
    {
        main_index = choose_main_unknown(i);
        if(main_index == -1)
            //哎呀,出错啦!
            continue;
        rank++;//线性独立,秩计数增加 
        swap_line(rank,main_index);to_one(rank,i);
        for(int j = rank + 1; j <= n; j++)
            plus_multi(j,rank,i);
    }
    if(rank != n)
    {
        if(find_zero_line())printf("-1\n");//无解 
        else printf("0\n");//无穷多解 
        return 0;
    }
    for(int i = n; i > 0; i--)
        for(int j = i - 1; j > 0; j--)
            plus_multi(j,i,i);//回代操作,系数矩阵变为单位矩阵 
    for(int i = 1; i <= n; i++)
        printf("x%d=%.2lf\n",i,b[i]);//正常解 
    return 0;
}

by ChampionCyan @ 2024-10-23 21:58:45

%%%


by TheShuMo @ 2024-10-23 22:00:43

tlqtj 不好评价


by UnknownFrisk @ 2024-10-26 08:38:53

@TheShuMo tlqtj啥意思


by User_leo @ 2024-11-10 10:44:28

讨论区题解,举报了。


|