对角线问题

数学基础 2019-07-16 1746 字 59 浏览 点赞

问题

这里有 n * n 矩阵,要求左上到右下的对角线上都为 x,其他地方为 y。x、y 任意值,但不相等。

x y y ... y
y x y ... y
y y x ... y
. . . ... .
. . . ... .
y y y ... x

解决

我们可以把这里的矩阵看做一个二维数组,长度为 N;x,y 赋任意不等常数即可。

>>> 方法一

现在,最简单的法子是两层循环遍历数组,在内层循环中做条件判断,决定应该赋值 x,还是赋值 y。代码如下边这样:

void func_handle_problem_1()
{
    int x = 2;
    int y = 4;
    int N = 8;
    int M[N][N];

    for (int i=0; i<N; ++i) {
        for (int j=0; j<N; ++j) {
            // 条件判断
            if (i == j)
                M[i][j] = x;
            else
                M[i][j] = y;
        }
    }
}

这样做思维上很简单,但存在性能上的缺点。由于每次赋值前都要做一次条件判断,程序会做 n*n 次条件判断。这显得有些冗余。

>>> 方法二

事实上,我们知道这个 n*n 的矩阵是正方形矩阵。也就是说,左上到右下这条对角线上,一定存在 i == j。所以根本不需要条件判断,直接做一个 i < N 的循环体,对 Mi 赋值 x 即可。由于其他位置得填充 y 值,所以对角线赋值前,我们可以对整个二维数组做一次赋初值行为。

void func_handle_problem_2()
{
    int x = 2;
    int y = 4;
    int N = 8;
    int M[N][N];

    // 赋初值
    for (int i=0; i<N; ++i) {
        for (int j=0; j<N; ++j) {
            M[i][j] = y;
        }
    }

    // 只对对角线赋值
    for (int i=0; i<N; ++i)
        M[i][i] = x;
}

>>> 方法三

方法二相比方法一,其优势在于减少了条件判断;但劣势在于,对角线上重复赋值。因而,更优的处理是既不要条件判断,也不要重复赋值。

现将矩阵分三部分:对角线左边为第一部分,对角线为第二部分,对角线右边为第三部分。只要在行遍历的时候,对三部分分别赋值,就达到了没有冗余的条件判断,也不会重复赋值。

Alt text

代码如下:

void func_handle_problem_3()
{
    int x = 2;
    int y = 4;
    int N = 8;
    int M[N][N];

    for (int i=0; i<N; ++i) {

        M[i][i] = x;  // 第二部分

        for (int j=0; j<i; ++j)  // 第一部分
            M[i][j] = y;
        for (int j=i+1; j<N; ++j)  // 第三部分
            M[i][j] = y;
    }
}


本文由 Guan 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。

还不快抢沙发

添加新评论