上期题目:矩阵翻转
解答:显然一个必要条件是两个矩阵里的元素必须是一致的,如果不一致可以直接判定不可能了。但这明显还不够。
此类问题通常有一个入手点就是看看经过操作之后不变的是什么。对于本题,一个重要的观察是如果我们把矩阵如国际象棋棋盘一样黑白格交替染色,会发现翻转操作不会改变数字所在的格子颜色,黑格数永远是黑格数,白格数永远是白格数。那么自然的猜测就是,两个矩阵的黑格元素一致且白格元素一致,是不是可以成功的充分必要条件呢?
答案是肯定的,下面说一个不太正式的证明。实际上我们只需要2×2的翻转操作就可以达到目的。每次2×2翻转操作只交换了两个斜对角相邻的元素,我们可以想象把所有黑格拿出来排成一列,使得相邻的两个格子在原矩阵中是斜对角相邻的(对于非1xN或Nx1的矩阵总可以做到)。那么2×2翻转操作就是交换了序列里相邻的两个元素,显然通过这种交换我们可以得到任何一种可能的排列(想一下冒泡排序)。对白格同理。于是只要黑白格的元素分别是一致的,就一定可以达到。注意要特殊判断一下1xN的情况。
本期题目:大力出奇迹
我们都知道台球界有一句格言叫“大力出奇迹”(并没有),只要力气够大,总能把球蒙进去。下面从数学角度研究一下这个问题:在台球桌上放一个球,沿直线击出,球如果没有进洞就永远前进,撞到边后的反弹和光的反射一样入射角严格等于出射角。球看作一个点,洞也看作点。
问题一:如果球永远不能进洞,那么一定是出现了循环么?(循环指以同一个方向回到以前经过的位置,比如平行于桌边轰一发,那么永远来回反弹)有没有可能不循环但是又永不进洞?
问题二:假如随机选一个角度轰一发,球最终进洞的概率是多少?循环的概率是多少?
问题三:存不存在一条永不进洞的线路,能经过桌面上任意一点?
问题四:稍微改一下设定,现在洞不是点,而是一个半径非常非常小的圆,当球和洞心的距离小于洞的半径时我们就认为球进洞了。在这种情况下,随机选一个角度轰一发,球最终进洞的概率是多少?
这个其实是数学题,和算法没啥关系了,不过实在是很有意思所以发出来。来源记得是看到某篇公众号文章说的华尔街交易公司面试题,重新整理了一下。