【算法】笔试题记录

哇今天做了道特别有意思的题。

编程就给了两道，第一题特别简单，a、b两个数，每次选其中一个数*2，这样操作两次，问最后得到的两数之和的期望值是多少。

简单吧？因为每次选择都有两种可能性，操作两次后就会有四种可能的结果(2²)。其中有两个结果是重复的(2a, 2b)，剩下两个分别是(a, 4b)和(4a, b)。把这四个结果求和除以4就是期望值。或者还有种角度，分别计算两次操作后 a 的期望和 b 的期望，把两者相加就是两数之和的期望（期望的线性性）。

第二题上来就看懵了。定义2*2的相邻元素（上下、左右）互不相同的01矩阵为好矩阵(比如[1 0 0 1]），而一个矩阵中包含好子矩阵的数量为它的权值。输入n、m，问所有 n * m 的矩阵权值的总和是多少？ 

啥玩意？我真的想破脑袋。后来笔试结束了才猛然醒悟，这两题是有联系的！第一题看似简单，其实正暗示了第二道题的解法：期望！

问题描述

•矩阵定义：我们考虑所有可能的  n * m  的 0-1 矩阵。

•权值定义：每个矩阵的权值是其中包含的好子矩阵的数量。

•好子矩阵定义：一个  2 * 2  的子矩阵，满足相邻元素（上下、左右）互不相同。

变量定义

•总矩阵数  N ：所有可能的  n * m  矩阵的数量。N = 2^n*m（因为每个元素有 2 种可能，共有  n * m  个元素）

•子矩阵位置数  K ：每个矩阵中可能的  2 * 2  子矩阵的数量。K = (n - 1) * (m - 1)（因为在  n * m  的矩阵中，横向有  n - 1  个位置，纵向有  m - 1  个位置）

•好子矩阵的概率  P ：随机生成的  2 * 2  子矩阵是好子矩阵的概率。P = 2/16 = 1/8（因为共有 16 种可能的  2 * 2  0-1 矩阵，其中只有 2 种是好子矩阵）

推导过程

目标：计算所有可能的  n * m  矩阵的权值总和，即所有矩阵中好子矩阵的总数量。

思路：从整体角度考虑，我们可以将问题转化为计算所有位置上好子矩阵出现的总次数。

1. 计算单个位置上的好子矩阵数量

•在单个位置上，可能的子矩阵数量等于总矩阵数  N ，因为每个矩阵在该位置上都有一个对应的子矩阵。

•在该位置上，好子矩阵的总数量为： N * P（每个矩阵在该位置上有一个子矩阵，成为好子矩阵的概率为  P ）

2. 计算所有位置上的好子矩阵数量

•总的位置数为  K ，每个位置独立且等价。

•所有位置上的好子矩阵总数为：总权值 = K * N * P

逻辑解释

有人可能疑惑了，每个位置怎么会独立呢？相邻子矩阵不是有共享的元素吗？

这里就要引入关键概念：期望的线性性。

期望的线性性是指，对于任意随机变量的和，其期望等于这些随机变量的期望之和，即使这些随机变量之间有相关性。这一点非常重要。

在我们的情境中：

•随机变量定义：对于矩阵中的每个可能的  2 * 2  子矩阵位置，我们定义一个指示变量  X_i ，如果该位置上的子矩阵是好子矩阵，其值为 1 ，否则为 0。

•总权值：所有矩阵的总权值等于所有  X_i  的和。

尽管这些  X_i 之间存在相关性（因为子矩阵共享元素），但在计算期望时，这种相关性并不影响总期望值的计算，期望的线性性仍然成立。

对于每个位置  i ：

总期望值：

其中  E[X]  是任意一个位置上子矩阵为好子矩阵的概率  P 。