Long Luo's Life Notes

每一天都是奇迹

By Long Luo

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

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

图1. 不同算法时间复杂度 Time Complexity Comparison

人们迫切需要找到一种可以快速计算阶乘的方法,在 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

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

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

  1. (本小题满分14分) 证明以下命题:
  1. 对任意正整数 \(a\) ,都存在正整数 \(b, c\)\(b < c\) )使得 \(a^2, b^2, c^2\) 为等差数列.
  2. 存在无穷多互不相似的三角形 \(\triangle_n\) ,其边长 \(a_n, b_n, c_n\) 为正整数且 \(a_n^2, b_n^2, c_n^2\) 成等差数列.

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

第一问

根据题意,正整数 \(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

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

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

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

水轮机

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

图1. 水车 Waterwheel

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

图2. 水轮

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

图3. 流动的水驱动水车

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

阅读全文 »

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

从之前的文章 正态分布(Normal Distribution)公式为什么长这样?从最小二乘法到正态分布:高斯是如何找到失踪的谷神星的? ,我们使用了 \(2\) 种不同的方法最终得到了如下公式 \((1)\) 所示的误差的概率密度函数 ( \(\text{Probability Density Function}\) ) :

\[ f(x) = \mathrm{e}^{-cx^2}, \, c > 0 \tag{1} \label{1} \]

其函数图像如下图 1 所示的钟形曲线 ( \(\text{Bell Curve}\) ) :

图1. 钟形曲曲线

在概率论中,我们需要保证上图 1 中 \(f(x)\)\(x\) 轴围成的面积是 \(1\) , 即:

\[ \int_{- \infty}^{+ \infty} f(x) \mathrm{d}x = 1 \tag{2} \label{2} \]

最终我们得到了正态分布 ( \(\text{Normal Distribution}\) ) 的公式如下所示:

\[ f(x) = {\frac {1}{\sigma {\sqrt {2 \pi }}}}\;e^{-{\frac {\left(x - \mu \right)^{2}}{2 \sigma ^{2}}}} \tag{3} \label{3} \]

上式中有一个 \(\pi\) ,用费曼( \(\text{Richard Feynman}\) )的话来说,当我们看到一个公式中存在 \(\pi\) 时,我们都要问自己“Where is the cycle?”。我们知道公式 \(\eqref{3}\) 中的归一化系数 \(\dfrac {1}{\sigma {\sqrt {2 \pi }}}\) 是为了保证 \(f(x)\) 下的面积为 \(1\) ,出现 \(\pi\) 是因为高斯积分 ( \(\text{Gaussian Integral}\) ) 的结果为 \(\sqrt{\pi}\)

那么什么是高斯积分呢?高斯积分和圆有什么关系呢?

阅读全文 »
0%