Long Luo's Life Notes

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 所示为位于比利时一家磨坊的水车。水车虽好，但需要稳定的水流，旱季时水力不足，运转乏力甚至无法运行，如何才能一年四季不因雨量不同而影响水车运转呢？

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

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

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

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 天？要回答这个问题，我们需要穿越历史的迷雾，回顾人类文明史，才能找到答案。

逝者如斯夫，不舍昼夜！

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

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

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

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

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