对角线问题

偏执的太偏执、 2021-12-10 01:43 242阅读 0赞

# 对角线问题 #

## 问题 ##

这里有 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` 的循环体，对 M\[i\]\[i\] 赋值 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;
    }

**>>> 方法三**

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

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU5MDUx_size_16_color_FFFFFF_t_70]

代码如下：

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;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU5MDUx_size_16_color_FFFFFF_t_70]: /images/20211209/4a5ebab1d9714d04a412b4d70ea71912.png