By Long Luo

最近在短视频 App 里刷到不少中学数学题讲解，才发现现在的初中数学题，很多已经不只是“会算”这么简单了，背后往往还藏着不等式、函数、几何直觉等不同层面的思维训练。

当然，这也不算奇怪，几十年前的 IMO 试题放现在也就普通题。很多经典数学竞赛题，随着时间推移和教学资源普及，早已从高阶技巧逐渐变成了基础训练的一部分。

前几天我就反复刷到一道“求极值”的题，看起来不难，但这道题其实非常适合拿来练习数学直觉。

看到这道题，首先想到的几何意义其实是将军饮马模型，但将军饮马问题求得是最小值问题。那最大值该怎么求呢？最大值的几何意义是什么呢？

这道题的有趣之处在于可以用很多完全不同的思路来解决，有的解法只需要代数变形和基本不等式，也可以使用几何视角、函数思想。

下面就道题为例，把几种典型解法都梳理一遍，也顺便重新锻炼一下自己的数学思维。

解法一：常规解法

由 \(y = 5 - x\) ，原式变成 \(\sqrt {x + 1} + \sqrt {8 - x}\) ，要保证根号有意义，所以 \(−1 \le x \le 8\) 。

设 \(S = \sqrt {x + 1} + \sqrt {8 - x}\) ，两边平方得 \(S^2 = (\sqrt{x + 1} + \sqrt{8 - x})^2\) 。

展开可得：

\[ \begin{aligned} S^2 & = (x + 1) + (8 - x) + 2 \sqrt {(x + 1)(8 - x)} \\ & = 9 + 2 \sqrt {(x + 1)(8 - x)} \\ & = 9 + 2 \sqrt {-x^2 + 7x + 8} \\ & = 9 + 2 \sqrt {-(x - \frac {7}{2})^2 + \frac {81}{4}} \end{aligned} \]

因此 \(S^2 \le 9 + 2 \times \dfrac {9}{2} = 18\) ，于是 \(S \le 3 \sqrt 2\) 当且仅当 \(x = \dfrac {7}{2}\) 时取等号。

故最大值为 \(3\sqrt2\) 。

By Long Luo

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

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

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

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

具体到这道题示例 \(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]\) ，如何计算每个结果的概率值呢？

直接算当然是可行的，但是如果骰子数量很多的话，计算会非常繁琐，所以有没有更简单的方法呢？

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

Kalman Filter¹ 是贝叶斯滤波器的一种特殊实现。

Kalman Filter 1D | 一维卡尔曼滤波器

一维卡尔曼滤波器如下图所示：

在线动画展示：http://www.longluo.me/projects/kalman/

By Long Luo

2024 年很快就要过去了，就在今天，我们脚下的地球已经以每秒约 30 公里的速度飞快越过了近日点，飞驰在围绕着太阳的椭圆轨道上。当 2025 年新年钟声敲响时，对于位于银河系第三旋臂边缘的这颗蓝色行星来说，不过是围绕着一颗黄矮星完成了一次再普通不过的公转，正如之前的 40 多亿次一样。而对于这颗行星上的碳基生物来说，不同的生物感受大不一样，这一刻却意味着对过去 366 个日夜 的告别与总结，也承载着对未来的期待与梦想。

和 2023 年不一样的是，我们在 2024 年要经历 366 个日夜，因为 2024 年是闰年。小学时，课本和老师都告诉我们一年有 365 天，但是闰年却是 366 天，这多出来的一天就是 2 月 29 日，在英语中叫做 \(\textit{Leap Day}\) 。四年一闰，百年不闰，四百年再闰，这是闰年的规则。后来学习编程时，判断某一年是不是闰年也是常见的编程练习题。在学习之余，你有没有想过，为什么闰年的规则要这么奇怪呢？背后的原因是什么呢？

小学读书时，就想 2 月份很委屈， 1 月 和 3 月都是 31 天，2 月却只有 28 或者 29 天，为什么 2 月这么特别呢？为什么有的月份是 31 天，有的月份是 30 天呢？但我的老师并没有讲清楚为什么，因为当时我的老师们也不清楚为什么，我也一直到大学里读了一本天文学书才知道了这个问题的答案。

为什么 2024 年 2 月有 29 天？要回答这个问题，我们需要穿越历史的迷雾，回顾人类文明史，才能找到答案。

逝者如斯夫，不舍昼夜！

《鲁滨逊漂流记》中的鲁滨逊流落到荒岛之后第一时间就是竖起了一根大柱子，用刀子在立柱上刻上凹口当作日历。一方面是因为鲁滨逊是基督徒需要做礼拜，另外一方面也是为了记录时间。我们的现代生活是离不开钟表的，如果没有钟表来量化时间的话，我们的工作生活将失去秩序。当然鲁滨逊在荒岛上也只能过着“日出而作，日落而息”的农业社会生活，无法精确的安排工作和生活。

“朝菌不知晦朔，蟪蛄不知春秋”，我们智人的寿命足够长，不像朝生暮死的蜉蝣，也不似春生夏死的寒蝉，可以目睹很多生命的诞生、成长以及消亡，感受时间的流逝。“逝者如斯夫，不舍昼夜！”，时间的洪流永远奔涌向前，然而虽然以我们生命的长度可以跨越四季与年轮，但是依然无法触及时间的尽头。

寄蜉蝣于天地，渺沧海之一粟。哀吾生之须臾，羡长江之无穷。当然我们现在知道时间并不是均匀流逝的，也不能脱离物质而存在，但在足够宏大的尺度上，时间在均匀的流逝着。

虽然你可能没有意识到，但是我们一直都在用着天然的时钟，它们就位于我们头顶的星空。这些时钟都足够精准，地球自转的每日误差在毫秒级别，月球公转和地球公转上百年也仅有几毫秒的差别。

“日出东南隅，照我秦氏楼。”，新的一天又开始了；残月如弓，新月如眉，满月如镜，周而复始；“未觉池塘春草梦，阶前梧叶已秋声。”，四季轮回时，我们知道新的一年又来临了。

By Long Luo

任何一款科学计算器上都可以计算三角函数，三角函数应用于生活工作中的方方面面，但计算机是如何计算三角函数值的呢？

三角函数本质上是直角三角形的3条边的比例关系，计算并没有很直观，那么计算机是如何计算三角函数值的呢？

在微积分中我们学习过 泰勒公式 ，我们知道可以使用泰勒展开式来对某个值求得其近似值，例如：

\[ \sin \angle 18^{\circ} = \frac{\sqrt {5} - 1}{4} \approx 0.3090169943 \]

利用泰勒公式，取前 \(4\) 项：

\[ \sin x \approx x - \frac{x^3}{3!} + \frac{x^5}{5!} - \frac{x^7}{7!} \]

代入可得：

\[ \sin \angle 18^{\circ} = \sin \frac{\pi}{10} = \frac{\pi}{10} - \frac{1}{6} (\frac{\pi}{10})^3 + \frac{1}{120} (\frac{\pi}{10})^5 - \frac{1}{5040} (\frac{\pi}{10})^7 \approx 0.30903399538 \]

可见取前 \(4\) 项时精度已经在 \(10^{-5}\) 之下，对于很多场合精度已经足够高了。

在没有了解 CORDIC(Coordinate Rotation Digital Computer) Algorithm ¹ 算法之前，我一直以为计算器是利用泰勒公式去求解，最近才了解到原来在计算机中，CORDIC 算法远比泰勒公式高效。

下面我们就来了解下泰勒公式的不足之处和 CORDIC 算法是怎么做的。

泰勒公式的缺点

上一节我们使用泰勒公式去计算三角函数值时，需要做很多次乘法运算，而计算器中乘法运算是很昂贵的，其缺点如下所示：

1. 展开过小则会导致展开精度不够，展开过大则会导致计算量过大；
2. 幂运算需要使用乘法器，存在很多重复计算；
3. 需要很多变量来存储中间值。

在之前的文章 矩阵乘法的 Strassen 算法 ，就是通过减少乘法，多做加法，从而大大降低了运算量，那么我们可以用相同的思想来优化运算吗？

当然可以，让我们请出今天的主角：CORDIC 算法。