Long Luo's Life Notes

By Long Luo

在上一篇文章我们剖析了 拼多多 2020 年校招笔试算法题中第一题: 多多的魔术盒子 ，今天来挑战下其中的第 4 题：骰子期望 ¹ ，题目如下：

要解答这道题，我们需要先从脑海里把中学数学知识捡起来，弄清楚什么是期望 ²？

在概率论和统计学中，一个离散性随机变量的数学期望是试验中每次可能的结果乘以其结果概率的总和：

\[ \operatorname {E} [X] = \sum _{i=1}^{\infty }x_{i}\,p_{i} \]

具体到这道题示例 \(1\) ，很明显 \(2\) 个骰子只能取到 \(1\) 或者 \(2\) 个值：

1. 假设这 \(2\) 个骰子取到的最大值为 \(1\) ，那么这 \(2\) 个骰子都只能选择 \(1\) ，概率为： \(\dfrac {1}{2} \times \dfrac {1}{2} = \dfrac {1}{4}\) ；

2. 假设这 \(2\) 个骰子取到的最大值为 \(2\) ，那么存在 \(2\) 种可能，要么都取 \(2\) 或者 \(2\) 个骰子中有一个骰子投出了 \(2\) ，其概率为： \(\dfrac {1}{2} \times \dfrac {1}{2} + \dfrac {1}{2} \times 1 = \dfrac {3}{4}\) 。

那么期望为： \(\dfrac {1}{4} \times 1 + \dfrac {3}{4} \times 2 = 1.75\) 。

对于骰子数少的时候还可以枚举，如果骰子数量很多呢？用上述方法就会遇到困难，比如有 \(N\) 个骰子，最大值为 \(M\) ，那么骰子结果为 \([1, 2, \dots, M]\) ，如何计算每个结果的概率值呢？

对于单个骰子，很显然每个结果的概率均为 \(\dfrac {1}{M}\) ，那多个不同骰子一起呢？如何计算最终结果的概率值呢？

By Long Luo

众多IT大厂中拼多多虽然工作强度很大，但在给钱方面非常大方。大厂给的钱多，但要求也高。下面就来挑战拼多多 2020 年校招笔试算法题 ¹ 中第一题：多多的魔术盒子 ² ，看看难度如何。

最少的操作次数该怎么做？

根据题意，我们关键是要找到最少次数这个方法，那如何操作才能使用最少次数呢？

当面对复杂问题时，我们需要从简单情况入手，分析其中规律，找到突破口。

1. \(N = 1\) 时，显然选择 \(X = 1\) ，需要 \(1\) 次操作；
2. \(N = 2\) 时，可以先选择 \(X = 1\) ，再选择 \(X = 2\) ，需要 \(2\) 次操作；
3. \(N = 3\) 时，只有先选择 \(X = 2\) ，再选择 \(X = 1\) ，最少需要 \(2\) 次操作；
4. \(N = 4\) 时，可以先选择 \(X = 2\) 或者 \(X = 3\) ，最少需要 \(3\) 次操作；

通过分析发现，每次操作之后，球的数量都会动态变化。如果每次都选择中间的数字，这样每次操作之后，如果 \(N\) 为奇数的话，可以变成 \(2\) 个对称相同的数组， \(N\) 为偶数的话，则 \(2\) 个数组中元素值会相差 \(1\) ，再选择元素值更多的数组进行消除，这样可以实现操作次数最少。

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13

private static int leastTimes_power(int n) {
    int ans = 1;

    for (int i = 0; i <= Math.sqrt(n); i++) {
        if (Math.pow(2, i) <= n) {
            ans = i;
        } else {
            break;
        }
    }

    return ans + 1;
}

为什么每次选取中间的数字进行操作次数最少呢？下面我们就来严谨的证明下！

By Long Luo

在科研和工程领域中，阶乘( \(\textit{Factorial}\) )有着广泛的应用。在概率论中，阶乘是计算排列( \(\textit{Permutation}\) )和组合( \(\textit{Combination}\) )时不可或缺的；在物理中，计算粒子系统的状态数以及大型系统的统计分布都要用到阶乘；在计算机中，阶乘则用于图论和组合优化问题。

大家都知道“指数爆炸”这个值，因为指数增长是非常迅猛的。其实阶乘增长要远远快于指数增长，如下图 1 所示为不同算法复杂度增长情况。随着 \(n\) 的增大，阶乘的计算复杂度迅速上升，当处理大 \(n\) 时，计算 \(n!\) 会变得极其复杂且耗时。例如 \(5! = 120\) ，而 \(50! \approx 3.04 \times 10^{64}\) ，这已经是一个非常庞大的数字！直接使用递归方法去求解 \(n!\) 的时间复杂度是 \(O(n)\) ，对于较大的 \(n\) 来说很容易栈溢出。在实际应用中，往往需要计算大数的阶乘，即使目前最先进的计算机去处理极大数的阶乘时，也会面临需要巨大的计算及存储资源消耗问题。

人们迫切需要找到一种可以快速计算阶乘的方法，在 18 世纪初期，苏格兰数学家詹姆斯·斯特林( \(\textit{James Stirling}\) )提出了斯特林公式 。斯特林公式( \(\textit{Stirling's Approximation}\) )提供了一种近似计算阶乘的方法，特别适用于大 \(n\) 的情况，其标准形式为：

\[ n! \approx {\sqrt {2\pi n}} \,\left( {\frac {n}{e}} \right )^n \tag{1.1} \label{1.1} \]

其对数形式为：

\[ \ln (n!) \approx n \ln n - n \]

这个公式最早是亚伯拉罕·棣莫弗( \(\textit{Abraham de Moivre}\) )在研究二项分布时，为了解决大数阶乘问题时发现的，其形式为：

\[ n! \approx C n^{n + \frac {1}{2}}e^{-n} \tag{1.2} \label{1.2} \]

其中 \(C\) 为某个常量值，斯特林证明了公式中 \(C = \sqrt {2 \pi}\) ，于是冠名权就给了斯特林。

斯特林公式可以大大简化阶乘的计算，特别是当 \(n\) 很大时，它提供了一个非常精确的近似值。斯特林公式使得复杂的阶乘计算可以通过较为简单的幂函数、指数函数和根号运算来完成。相比于直接计算阶乘，它极大地减少了计算量，是大数问题中不可或缺的工具。

斯特林公式中集合了圆周率 \(\pi\) 和自然常数 \(e\) ，这 \(2\) 个数学中最重要的常数，十分独特且具有美感。因为 \(e\) 意味着连续增长，而阶乘就是连续自然数的相乘。而出现 \(\pi\) 的时候，就要问自己 “Where is the circle?”，那么阶乘是如何和几何中的圆扯上关系了呢？

关于斯特林公式的证明，常见的证明是对数形式的证明或者利用伽马函数( \(\textit{Gamma Function}\) )来证明，这里将介绍一种从零开始更易理解的推导方式。

By Long Luo

知乎上有个问题是高考数学最后一题可以有多难？ ¹，而公认史上最难高考数学题就是 2008 年江西高考理科数学压轴题。2005 - 2014 年是江西自主命题，而江西卷也以题难计算量大著称，尤其是数学和理综。陶平生老师 是 2008 - 2011 年江西高考数学命题组长，参与了 2005 - 2011 年江西高考命题，他出江西数学卷时，是江西30多万学生被支配的恐惧！

作为一名来自十八线农村做题家，高考时赶上了江西自主命题，在考场上也体会到了数学和理综卷题目居然没做完没思路的恐惧！中学时没能感受到数学的乐趣，最近几年看了一些数学书之后，重新拾起了数学的乐趣，经常找些数学题来训练下我的思维，今天就来挑战一下 2010 年江西高考理科数学压轴题：

这道题其实是数论( \(\textit{Number theory}\) ) ² 背景，除了搞竞赛的同学，谁学过数论呢？这种构造性( \(\textit{Constructive proof}\) ) ³ 题目，没有接触过类似题目的话，根本不知道如何下手。要是我在考场上也会一脸懵圈，甚至在几年前我也是一筹莫展，不过现在倒是有勇气挑战这类题目了！网上关于这道题的参考答案太简略了，主要是如何找到答案的构造不清楚。这道题真是一道绝妙的题，我花了比较长时间来思考这道题，下面详细描述我的解题思路。

第一问

根据题意，正整数 \(a, b, c\) 且 \(b < c\) ，满足 \(a^2, b^2, c^2\) 为等差数列，即：

\[ b^2 - a^2 = c^2 - b^2 \Rightarrow 2b^2 = a^2 + c^2 \]

观察上式，我们可以得到 \(2\) 个推论：

1. \(a < b < c\) ；
2. \(a\) 和 \(c\) 要么都是偶数，要么都是奇数。

因为 \(a\) 为任意正整数，那么就从最简单的开始，不妨设 \(a = 1\) ，则有：

1. 令 \(c = 1\) , 得 \(b = 1\) ，与 \(a < b < c\) 矛盾；
2. 令 \(c = 3\) , 得 \(b = \sqrt {5}\) ，与 \(b\) 为正整数矛盾；
3. 令 \(c = 5\) , 得 \(b = \sqrt {13}\) ，与 \(b\) 为正整数矛盾；
4. 令 \(c = 7\) , 得 \(b = 5\) ，满足条件。

简单猜测实验得到一组要求的值： \(a = 1\) , \(b = 5\) , \(c = 7\) 。

再设 \(a = 2\) ，同理有：

1. 令 \(c = 4\) , 得 \(b = \sqrt {10}\) ，与 \(b\) 为正整数矛盾；
2. 令 \(c = 6\) , 得 \(b = 2 \sqrt {5}\) ，与 \(b\) 为正整数矛盾；
3. 令 \(c = 8\) , 得 \(b = \sqrt {34}\) ，与 \(b\) 为正整数矛盾；
4. 令 \(c = 10\) , 得 \(b = 2 \sqrt {13}\) ，与 \(b\) 为正整数矛盾；
5. 令 \(c = 12\) , 得 \(b = \sqrt {74}\) ，与 \(b\) 为正整数矛盾；
6. 令 \(c = 14\) , 得 \(b = 10\) ，满足条件。

通过实验又得到一组要求的值： \(a = 2\) , \(b = 10\) , \(c = 14\) 。

综合 \(a\) 为奇数和偶数的情况，猜想：

对于 \(\forall a = n \in \mathbb{N}^+\) ，令 \(b = 5a\) , \(c = 7a\) ，易得：

\[ 2 \cdot (5n)^2 = n^2 + (7n)^2 \]

故命题(1)得证。

By Long Luo

无论是家中的冰箱和空调，还是天上的飞机、水中的轮船、路上的汽车，它们本质上都属于热机 ¹。或许有人会疑惑：冰箱和空调明明是用电的，怎么能和烧油的归为一类呢？事实上，这些机器虽然形式各异，但原理上都涉及热能的转换。它们早已融入我们的日常生活，而对大多数人而言，知道它们是机器已经足够了。

人类一直以来都在努力提高机器的效率，从而更好的为我们服务。以汽车为例，目前汽油发动机的热效率大约为 \(30\%\) ，柴油机稍高一些，可达 \(40\%\) ，而电动机的效率则高达 \(90\%\) ，部分甚至可以达到 \(95\%\) 。为什么燃油发动机的效率远远低于电动机呢？主要原因在于电动机可以直接将电能转换为机械能，结构简单，损耗极少。而燃油发动机则涉及多个能量转换环节，结构复杂，损耗较大。

假如我们忽略燃油发动机的一切损耗，它的效率是否能达到 \(100\%\) 呢？我曾一度认为可以，但后来发现并非如此。要解答这个问题，我们需要先从水流谈起。

水轮机

把手放进流动的水中，我们可以明显感觉到水流的冲击力，水流越大越快，冲击力也就越大。人类很早就意识到了流水中蕴藏的能量，并用流水来驱动水车，用于灌溉、磨坊等，下图 1 所示为位于比利时一家磨坊的水车。水车虽好，但需要稳定的水流，旱季时水力不足，运转乏力甚至无法运行，如何才能一年四季不因雨量不同而影响水车运转呢？

答案很明显，修水坝，在雨季时把富余的水存储在高处，这样旱季时也能保证水车的正常运转。这一策略一直沿用了几千年，到现在无非就是大坝修得更高更好，水车换成了水轮机，驱动磨坊变成了发电而已。水在高处时，具有重力势能越大，但如果我们在高山湖泊中放置一台水车时，水车是不会转动的，因为湖泊中的水并不一定在流动，即使在流动，流速也很小，并不足以驱动水轮机。

只有当水从高处流向低处时，势能才能转化为动能，推动水轮机从而进行机械作功，实现能量的转化与利用。

从上图也可以看出，驱动水车的关键在于水的流动，而不在于水的多少。高山湖泊的水虽然重力势能很大，而且数量巨大，但是除非这些水从高处流下，否则并不能对外做功。