C语言三种方法计算行列式的值

2020年04月13日 229点热度 3人点赞 2条评论

1.递归求代数余子式求值

代码:

void getCofactor(int row, int column,int size,double in[][MAX_SIZE],double out[][MAX_SIZE])//获取个元素的余子式
{
    register int i,j;
    register int c=0,r=0;
    for (i = 0; i < size; i++)
    {
        if (row == i)continue;
        for (j = 0,c=0; j < size; j++)
        {
            if (j != column)out[r][c++] = in[i][j];
        }
        r++;
    }
}
double cal(double det[][MAX_SIZE], int size)
{
    if (size == 1)
    {
        return det[0][0];
    }
    int i,j;
    double detTemp[MAX_SIZE][MAX_SIZE] = { 0 };
    double res = 0;
    for (i = 0; i < size; i++)
    {
        getCofactor(0,i,size,det,detTemp);//获取余子式
        res += (((i+2) % 2) ? -det[0][i] * cal(detTemp, size - 1) : det[0][i] * cal(detTemp, size - 1));//递归求余子式的值
    }
    return res;
}

求值的时候调用cal函数计算

运行效果

2.递归求排列方式进而求行列式值

因为行列式结果等于从每行选出不同列的元素相乘 ,然后将所有积相加,所以用递归可以求出全排列然后求行列式的积再求值

代码:

void swap(int *a,int *b)
{
    int c;
    c = *a;
    *a = *b;
    *b = c;
}
int getSwapTime(int size,int sequence[])
{
    register int count = 0;
    int seq[MAX_SIZE] = { 0 };
    register int i,j;
    for (i = 0; i < size; i++)
    {
        seq[i] = i;
    }
    for (i = 0; i < size; i++)
    {
        if (seq[i] != sequence[i])
        {
            count++;
            for (j = 0; i == j || seq[j] != sequence[i]; j++);
            swap(seq+i,seq+j);
        }
    }
    return count;
}
double __cal(double det[][MAX_SIZE], int size, int sequence[])
{
    double ret= 1;
    register int i;
    for (i = 0; i < size; i++)
    {
        ret *= det[i][sequence[i]];
    }
    return ret;
}
double _cal(double det[][MAX_SIZE], int size,int depth,int sequence[])
{
    int i;
    int sequenceTemp[MAX_SIZE] = {0};
    static int used[MAX_SIZE] = {0};
    int swapTime;
    static double res;
    if (depth == 0)
    {
        res = 0;
        memset(used,0,sizeof(used));
    }
    if (size == depth)
    {
        swapTime = getSwapTime(size, sequence);
        res += ((swapTime % 2) ? -__cal(det, size, sequence): __cal(det, size, sequence));
        return res;
    }
    memcpy(sequenceTemp,sequence,sizeof(sequenceTemp));
    for (i = 0; i < size; i++)
    {
        if (!used[i])
        {
            used[i] = 1;
            sequenceTemp[depth] = i;
            _cal(det,size,depth+1,sequenceTemp);
            used[i] = 0;
        }
    }
    return res;
}
double cal(double det[][MAX_SIZE], int size)
{
    int seq[MAX_SIZE] = {0};
    return _cal(det,size,0,seq);
}

运行效果

3.用上三角行列式性质求值

这个和普通我们做题的时候用的方法相同 ,通过某一行乘以一个数加到另一行上行列式值不变,可以将普通行列式化为上三角行列式,然后将主对角线元素相乘即可求出最后结果。

代码:

void addRow(int size,double det[][MAX_SIZE], int dst, int row, double multiple)
{
    register int i;
    for (i = 0; i < size; i++)
    {
        det[dst][i] += det[row][i]*multiple;
    }
}
double _cal(double det[][MAX_SIZE], int size)
{
    register int i;
    register double res;
    for (i = 0,res = 1; i < size; i++)
    {
        res *= det[i][i];
    }
    return res;
}
void swapRow(double row1[MAX_SIZE], double row2[MAX_SIZE], int size)
{
    double temp[MAX_SIZE];
    memcpy(temp, row1, sizeof(double) * size);
    memcpy(row1, row2, sizeof(double) * size);
    memcpy(row2,temp, sizeof(double) * size);
}
double cal(double det[][MAX_SIZE],int size)
{
    int i, j;
    int k;
    for (i = 0; i +1< size; i++)
    {
        for (j = i+1; j < size; j++)
        {
            if (!det[i][i])
            {
                for (k = i;k<size;k++)
                {
                    if (det[k][i])
                    {
                        swapRow(det[i], det[k],size);
                        break;
                    }
                }
                if (k == size)return 0;
            }
            addRow(size,det,j,i,-det[j][i]/det[i][i]);
        }
    }
    return _cal(det,size);
}

运行效果

 

性能分析

三种方法用同种方式记录运行所用的时间,测试代码:(其中cal函数为算法的函数)

#include<stdio.h>
#include<string.h>
#include<time.h>
#pragma warning(disable :4996)
#define MAX_SIZE 50
double cal(double det[][MAX_SIZE], int size);
int main(int argNum, char* args[])
{
    long long start = 0, end;
    int size, i, j;
    double input[MAX_SIZE][MAX_SIZE] = { 0 };
    printf("size:");
    scanf("%d", &size);
    for (i = 0; i < size; i++)
    {
        for (j = 0; j < size; j++)
        {
            scanf("%lf", &input[i][j]);
        }
    }
    start = clock();
    printf("result:%lf\n", cal(input, size));
    end = clock();
    printf("time used: %d ms\n", (end - start) / (CLOCKS_PER_SEC / 1000));
    printf("press enter to quit");
    rewind(stdin);
    getchar();
}
方法 用时
方法1 1889ms
方法2 927ms
方法3 <1ms

三种方式前两种没有出现运算错误 ,第三种运算方式因为含有浮点数运算,在行列式较大,元素数据较大的时候,容易出现精度的损失,导致了如方法三图中,运算结果不正确的情况,但是因为第三种只采用了少量的循环,函数调用相对于递归少,压栈弹栈占用的成本也比较低,所以速度最快。

Danny

我就如一粒石子,在随波逐流中,逐渐冲蚀了自己的棱角,变光滑,也变丑陋。

文章评论

  • LeahDing

    ❤️❤️❤️

    2020年04月13日
  • 一位不愿意透露姓名的好心人

    厉害厉害,大佬加油

    2020年05月22日