xxyQwQ
0%

【题解】ACMOJ 1033 求行列式

发表于 更新于 分类于

题目描述

ACMOJ - 1033 - 行列式求值

求 $n$ 阶行列式 $\begin{vmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\
a_{21} & a_{22} & \cdots & a_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
a_{n1} & a_{n2} & \cdots & a_{nn}\end{vmatrix}$ 的值，保证 $n\leq 10$ 且答案在int范围内

问题分析

行列式的求解有多种方法，具体参见《线性代数》教材

此处介绍以下三种方法：

  • 全排列法：利用行列式的全排列定义直接计算
  • 余子式法：利用行列式的按行展开性质递归计算
  • 高斯消元：利用初等变换将行列式化为上三角阵简化计算

全排列法

设 $A=(a_{ij})_{n\times n}\in \mathbb{K}^{n\times n}$，则 $|A|=\sum \limits _{j_1j_2\dots j_n}(-1)^{\tau(j_1j_2\dots j_n)}a_{1j_1}a_{2j_2}\dots a_{nj_n}$

利用std::next_permutation函数构造 $1,2,\dots ,n$ 的全排列，借助函数统计逆序对数，完成计算

时间复杂度为 $O(n^2\cdot n!)$，利用分治求逆序对可以优化到 $O(n\log n\cdot n!)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <cstdio>
#include <algorithm>

int a[15][15], p[15], n, answer;

int invertion(int v[], int k)
{
    int r = 0;
    for (int i = 1; i <= k; i++)
        for (int j = i + 1; j <= k; j++)
            if (v[i] > v[j])
                r++;
    return r;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d", &a[i][j]);
    for (int i = 1; i <= n; i++)
        p[i] = i;
    do
    {
        int term = 1;
        for (int i = 1; i <= n; i++)
            term *= a[i][p[i]];
        term *= (invertion(p, n) & 1) ? -1 : 1;
        answer += term;
    } while (std::next_permutation(p + 1, p + n + 1));
    printf("%d\n", answer);
    return 0;
}

余子式法

设 $D=|a_{ij}|_{n\times n}$，则 $D=\sum \limits _{j=1}^na_{1j}A_{1j}$，其中 $A_{1j}$ 为 $D$ 的代数余子式

为实现递归计算，我们动态开辟数组，并且将二维数组压缩至一维，即构造映射 $a_{ij}\rightarrow a_{in+j}$，以此解决函数传参问题

时间复杂度为 $O(n!)$，实际运行快于全排列法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cstdio>

int a[105], n;

int det(int *v, int k)
{
    if (k == 1)
        return *v;
    int r = 0;
    for (int p = 0; p < k; p++)
    {
        int *s = new int[(k - 1) * (k - 1)];
        for (int i = 0; i < k - 1; i++)
            for (int j = 0; j < k - 1; j++)
                *(s + i * (k - 1) + j) = *(v + (i + 1) * k + (j < p ? j : (j + 1)));
        r += ((p & 1) ? -1 : 1) * *(v + p) * det(s, k - 1);
        delete[] s;
    }
    return r;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", a + i * n + j);
    printf("%d\n", det(a, n));
    return 0;
}

高斯消元

  • 依次遍历第 $i=1,2,\dots ,n$ 行，将 $a_{ii}$ 作为主元
  • 依次遍历第 $j=i+1,i+2,\dots ,n$ 行，通过初等变换将 $a_{ji}$ 消为 $0$
  • 特别地，若 $a_{ii}=0$，则遍历 $j=i+1,i+2,\dots ,n$ 寻找 $a_{ji}\neq 0$，并将第 $i$ 行与第 $j$ 行交换
    （每次交换两行会使结果的正负性反转）
  • 若 $a_{ji}$ 全为 $0$，行列式的值即为 $0$
  • 消元完成得到上三角阵 $D’$，其对角线元素乘积即为行列式的结果

时间复杂度为 $O(n^3)$，远优于前两种方法，但存在浮点数精度的局限性，代码实现中需要思考如下问题：

  • 如何判定两个浮点数相等？
  • 输出结果是否可以强制转换为整数？
  • 如果不行，应该怎么做？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <cstdio>
#include <cmath>
const double eps = 1e-5;

double a[15][15];
int n;

bool equal(double x, double y)
{
    return fabs(x - y) < eps;
}

template <typename T>
void swap(T &x, T &y)
{
    T temp = x;
    x = y, y = temp;
}

double determination()
{
    double r = 1;
    for (int i = 1; i <= n; i++)
    {
        if (equal(a[i][i], 0))
        {
            int j;
            for (j = i + 1; j <= n; j++)
                if (!equal(a[j][i], 0))
                    break;
            if (j == n + 1)
                return 0;
            r *= -1;
            for (int k = 1; k <= n; k++)
                swap(a[i][k], a[j][k]);
        }
        for (int j = i + 1; j <= n; j++)
        {
            double p = -(a[j][i] / a[i][i]);
            for (int k = i; k <= n; k++)
                a[j][k] += p * a[i][k];
        }
    }
    for (int i = 1; i <= n; i++)
        r *= a[i][i];
    return r;
}

int regularize(double x)
{
    double y = fabs(x);
    return (x >= 0 ? 1 : -1) * int(y + 0.5);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%lf", &a[i][j]);
    double result = determination();
    printf("%d\n", regularize(result));
    return 0;
}