算法|题解

计蒜客 – 蒜头君学代数

凝神长老 · 2月20日 · 2019年 · · 902次已读

本文写于 2019年02月20日,距今已超过 1 年,距 2020年03月27日 的最后一次修改也已超过 3 个月,部分内容可能已经过时,您可以按需阅读。如果图片无法显示或者下载链接失效,请给我反馈,谢谢!


今天做了一道题,叫《蒜头君学代数》,本来觉得是数论知识,没想到是二分答案,这题我想了很久,也是看了题解以后才知道这个思路的。

题目链接:https://www.jisuanke.com/course/615/28897

题目:

蒜头君最近在研究二阶矩阵的行列式的计算:
[ $$\displaystyle det\left(\begin{matrix}a & b \\ c & d \end{matrix}\right)=ad-bc​$$ ]

定义 1:一个 奇异矩阵 是指矩阵的行列式的值为 $0​$。

定义 2:矩阵 $A$ 的 范数 定义为:[ $|A|=\max\sum_{i=1}^{m}\left|a_{i,j}\right|$ ],即矩阵中所有元素的绝对值的最大值。

现在给定一个 $2\times2$ 的矩阵 $A$,找到一个奇异矩阵 $B$ 满足 [ $|A-B|$ ] 的范数最小。求出 [ $|A-B|$ ]的最小范数。

输入格式:

第一行输入两个整数 [ $a,b(|a|,|b|\leq 10^9)$],表示矩阵 $A$ 中的第一行元素。

第二行输入两个整数 [$c,d(|c|,|d| \leq 10^9)$],表示矩阵 $A$ 中的第二行元素。

输出格式:

输出一行浮点数,表示最小的 [ $|A-B|$ ] 的范数。只要结果和标准答案误差在 $10^{-6}$ 以内都被认为是正确的。

样例输入1:

  1 2
  4 3

样例输出1:

  0.500000000

样例输入2:

  1 1
  1 0

样例输出2:

  0.333333333

这是一题二分的题。

首先说明思路,二分的东西就是答案,即所求的最小的范数。

矩阵 $A$ 已知,最小的范数就是二分的值,那么就可以求出矩阵 $B$ 的值的范围。

具体来说,如果$A-B$的范数最小是$x$,那么对于矩阵$A$中的某一个元素$a$,$|a-b|$应该在 $\pm x$ 之间,其中$b$是矩阵$B$中对应位置上的元素值。

这样,就可以求出矩阵$B$的四个位置上的元素的取值范围,各自都是一个长度为$2x$的闭区间,且,至少需要有一个位置上的元素取到端点值,其他位置上的值可以是范围内的任意值。

题目并没有规定必须是整数,所以,范围内的任意实数都是可以取的,也就是说,矩阵$B$的元素的取值是连续的。

下面计算矩阵$B$的行列式的值的可能取值,由于元素的取值是连续的,所以矩阵$B$的行列式的值有无穷多个,不可能一一枚举,然后找是不是有值为$0$的(即奇异矩阵)。

但是也正是因为连续的,所以我们只需要找行列式的值的最大值和最小值,如果矩阵$B$的行列式的值的最大值和最小值跨越了$0$,即,最小值小于等于$0$,最大值大于等于$0$,那么,根据函数的连续性(零点存在定理),一定存在行列式的值为$0$的情况,也就是说,一定存在一种构造,在满足各个元素的取值在给定范围内的情况下,使得矩阵$B$的行列式的值为$0$。

例如,对于样例2,最小值是$\frac{4}{9}$,最大值是 $\frac{16}{9}$,跨越了零点,那么就存在一种构造,在确保至少一个元素取得端点值,其他元素在给定范围内的情况下,使得矩阵$B$为奇异矩阵,例如:[ $$\displaystyle \left(\begin{matrix}\frac{4}{3} & \frac{2}{3} \\ \frac{2}{3} & \frac{1}{3} \end{matrix}\right)$$ ]。

由于这是一个$2\times2​$的矩阵,每个元素的取值范围是一个长度为$2x​$的闭区间,所以,只需要计算 16 种情况,就可以求出矩阵$B​$的行列式的值的取值范围。

下面考虑二分的收缩方向。

显然,初始条件,左端点一定是$0$,因为绝对值。

右端点一定是矩阵$A$中最大的值,因为如果存在一个最小范数比$A$中最大的值还大,记为$m$,那么令矩阵$B$为零矩阵(显然也是一个奇异矩阵),就得到范数为$A$中最大值,找到了一个比$m$更小的范数,矛盾。

简单起见,令右端点为一个无穷大的值也是可以的,反正会收缩回来的。

然后考虑什么时候是left=mid,什么时候是right=mid

显然,如果存在某个范数满足条件,他未必是最小的,但是,如果给定范数是可行的,那么比他更大的范数也一定是可行的(会令最小值更小,最大值更大,既然原来的最小值和最大值跨越了零点,那么显然现在的范围也是跨越零点的)。

例如,给定一个矩阵$B$,第一行第一列的元素是$10000$,其余元素都是$0$,显然$B$是一个奇异矩阵,那么$A-B$的范数就是$|a_{1,1}-10000|$,这是找到了一个答案,可以令ans=mid,但是这是不是最小的答案呢?不知道,因此,尝试缩小mid,即令right=mid再次尝试。

由此,可以得到核心代码。

while (left < right) {
    double mid = (left + right) / 2;
    if (check(mid)) {
        right = mid;
        ans = mid;
    } else {
        left = mid;
    }
}

代码中,考虑到浮点数的精度问题,left < right应该换成比较差值是不是小于$\epsilon$。

check(double)是一个函数,判断在给定的值作为范数的情况下,能不能构造出一个奇异矩阵$B$,如果能,返回true,那么二分代码中就缩小右端点,否则,说明不能构造出奇异矩阵,那么右移左端点,尝试更大的范数。

函数中,首先计算出$B$每个元素的两个端点值,分别是$A[i]\pm mid$,然后计算 16 种情况下的 $ad-bc$ 找到最大值和最小值,判断是不是跨越零点,即是不是异号。

完整代码如下:

import java.util.Scanner;

public class Main {

    static int[] A = new int[4];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        for (int i = 0; i < A.length; i++)
            A[i] = in.nextInt();
        double left  =0;
        double right = Integer.MAX_VALUE;
        double ans = right;
        double EPS = 1E-6;
        while (left - right < 0 && left - right < -EPS) {
            double mid = (left + right) / 2;
            if (check(mid)) {
                right = mid;
                ans = mid;
            } else {
                left = mid;
            }
        }
        System.out.println(ans);
    }

    private static boolean check(double mid) {
        double[][] B = new double[4][2];
        for (int i = 0; i < A.length; i++) {
            B[i][0] = A[i] + mid;
            B[i][1] = A[i] - mid;
        }
        double max = Integer.MIN_VALUE;
        double min = Integer.MAX_VALUE;
        for (int i = 0; i < 16; i++) {
            int a = i / 8;
            int b = i % 8 / 4;
            int c = i % 4 / 2;
            int d = i % 2;
            double det = B[0][a] * B[3][d] - B[1][b] * B[2][c];
            max = Math.max(max, det);
            min = Math.min(min, det);
        }
        return max * min <= 0;
    }

}
0 0 投票
文章评分
订阅评论动态
提醒
guest
0 评论
行内反馈
查看所有评论