Long Luo's Life Notes

https://www.longluo.me/

https://www.longluo.me/atom.xml (RSS订阅地址)

夏至日测地球：利用太阳影子计算地球半径

By Long Luo 在之前的文章里 <a href="https://www.longluo.me/blog/measure-earth-circumference-shadow-eratosthenes/">如何用一根棍子测出地球有多大？复刻埃拉托色尼的春分实验</a> ，复刻了埃拉托色尼( $\textit{Eratosthenes}$ ) 的测量地球实验。因为春分时太阳直射赤道，我们只需要测量当地正午时影子即可，然后借助 Google 地图来获取与赤道之间距离，虽然这有点作弊的感觉，最后计算得到了非常精确的结果。 这个实验需要测量经度相同但纬度不同的 $2$ 个地方的影子数据以及它们之间的距离，根据影子计算 $A$ 地的纬度 $\theta_1$ 以及 $B$ 地的纬度 $\theta_2$ ，于是可以得到地球半径计算公式： \[ R_{\textit{earth}} \approx \frac {d}{\theta_1 - \theta_2} \approx \frac {d}{\Delta \theta} \tag{1} \] 如果我们能找到一个经度相差不大的远方朋友帮忙测量当地正午时的影子，然后根据两地的距离就可以很轻松计算地球大小。不过我并没有找到这样一位朋友在正午时测量日影，但我想到了多个方法可以实现这一点。首先在夏至日这天我并不需要这样一位朋友帮忙也可以实现。因为这一天太阳将直射北回归线，我只需要测量我所在地方正午时的影子就可以了。 2026 年 6 月 21 日夏至日，也恰逢端午假期。这里说下题外话，查了最近几年的端午假期，发现端午也就和夏至相隔几天，突然意识到端午最初起源可能就是纪念夏至日，以前都没想到这一点。网上搜了一些文章，发现确实如此，端午确实就是纪念夏至日的。 根据 <a href="https://www.timeanddate.com/">timeanddate</a> 网站，深圳当地时间正午为 $12:25$ ，下面图 1 是我拍摄的台阶的影子：

2026/6/21

太阳温度是怎么计算出来的？

By Long Luo 每天清晨，当太阳缓缓升起，第一缕阳光洒向大地，我们便开始感受到它带来的温暖。到了盛夏的中午，炽热的阳光甚至会让人汗流浃背，不得不寻找树荫或空调避暑。从植物进行光合作用，到风、雨和四季的形成，再到地球上几乎所有生命活动所需的能量，都直接或间接来自太阳。可以说，没有太阳，就没有今天丰富多彩的生命世界，这个生机勃勃的星球。 当人类走出蛮荒，开始仰望星空时，一些远古的智者肯定就思考过这样一个问题：这颗挂在天上的大火炉到底有多热？但直到现在，仍然没有人能够把温度计放到太阳表面进行测量。但令人惊讶的是，人类并不需要飞往太阳附近，也不需要把温度计伸到太阳表面，仅凭在地球上的观测数据和几条经典的物理定律，就能够计算出太阳表面的温度约为 $5770K$（约 $5500\,^\circ\mathrm{C}$）。实际上，计算得到这个数字只需要中学知识，那么这个数字究竟是如何一步步推导出来的呢？接下来，就让我们一起揭开其中的奥秘。 <h2 id="太阳有多热">太阳有多热？</h2> 科学家早已发现，太阳并不是一个整体均匀的“火球”，而是由不同区域组成的复杂天体，因此各个区域的温度也各不相同。例如，太阳核心的温度高达约 $1500$ 万摄氏度，在那里持续发生着核聚变反应，释放出巨大的能量；而在太阳大气的最外层——日冕中，温度反而升高到约 $100$ 万至 $200$ 万摄氏度，这一现象至今仍是太阳物理学中的重要研究课题。 太阳所产生的巨大能量，正是从这些高温区域向外传递，并最终从太阳表面向宇宙空间辐射出去。地球所接收到的太阳能量，只是其中极其微小的一部分，却足以维持地球上所有生命活动。

2026/4/10

《大象的时间，老鼠的时间》读书笔记：生命节奏背后的数学规律

By Long Luo 日本生物学家本川达雄( Tatsuo Motokawa )写的书 <a href="https://book.douban.com/subject/27148101/">《大象的时间，老鼠的时间》</a> 几年前我曾经在书店的畅销书里看到过，是一本很有趣的书，解答了我心中很多关于生物的疑问。书不厚，在书店里就读完了几章，后来去图书馆借来看完了剩下几章。最近又重新翻阅了这本书，这次做下读书笔记。 <h2 id="第一章-动物的体型和时间">第一章动物的体型和时间</h2> 在不同体型的动物身上感觉到时间的流逝是不一样的，比如狗的寿命是 12 年。但对于他的心率、呼吸、对时间流逝的感知度的角度来看，他们仿佛也度过了漫长的一生。 哺乳动物的时间与体重的 1/4 次方成正比。 每1次呼吸间隔，心跳会跳4次。 不管哪种哺乳动物，一生的心跳，大约都是20亿次，一生的呼吸则是5亿次。 <h2 id="第二章-动物的体型和进化">第二章动物的体型和进化</h2> “岛屿法则”指的是在岛屿上，大型动物有变小的趋势，小型动物有变大的趋势，这在古生物学中被称为岛屿法则。 对于这种法则，很大的体型也需要很大的摄入量，在岛屿这种，捕食压力变小的情况下，大象就没有必要为了变大而勉强支撑。同样的，老鼠也变大了，回到了作为哺乳动物最轻松的体型。 还是先回到变大策略的好处上来吧。 柯普法则：同一物种的进化过程中，体型大的种类有晚出现的趋势。 体型大的优势： <ol type="1"> <li>不易受环境影响能保持独立。体型越大，越容易保持恒温。恒温有利于动物体内生化反应的稳定发生。</li> <li>恒温还能确保恒时，比如鸟儿要保持一个体温，才能够快速的移动。也就是说，当体温变化时间在生物身上的流逝，也是会发生变化的。如果温度忽高忽低，在低温状态移动会减慢，就等于时间的流速也慢了。就跟看视频的时候卡了一样。</li> <li>体型越大，恒温所需的能量越少。也因为表面积体积比例越小而更耐干旱。</li> <li>体型越大的动物细胞数量越多，因此就能够把多余的部分用于新机能的开发。细胞代谢率也相对更低，能量更富余，所以大型动物有条件来充分的发展智能。挺新月大的动物进食，时间见个月长，也有更充裕的时间来从事其他活动。</li> </ol> 体型小的优势: <ol type="1"> <li>越小越容易发生变异寿命，短数量多，短时间内产生变异的概率大。</li> <li>移动能力弱，从地理上与附近的其他种群保持隔离，产生新集团而独自发展的机会就更多。</li> <li>个体越小生存压力越大，能适应才能活下来，所以抗逆性会更高。</li> <li>小型动物水不断被捕时，死亡率高君个体多而不断产生新物种，因此有很大概率能留下后代。</li> </ol> 这里又开始出现辩证的哲思了。大型动物不易受微小环境变化影响，更长寿，这本来是优势，但是这种稳定性现在又成了障碍，使得这一种群很难产生新的物种，而且大型动物数量少，一旦遇到了超越承受边界的环境压力，有可能还没来得及苟活变异，直接就整灭绝了。

2026/4/2

小港流到哪里去？

By Long Luo 我出生在长江中下游的一个小山村，村子背后是一座小山，村子前面有一条小河，它在村子前面转了个大弯。 它没有乱石穿空的激流险滩，也没有飞流直下的瀑布，随着地势弯弯曲曲的小河，就是一条在很小很小的小河。说它是河又不能称之为河，因为它太小、太窄了，最宽处也就不过5，6米左右，远没有河的宽广和波澜壮阔。在南方，它是条普通到不能再普通的河，普通到没有名字，乡里四邻约定俗称的都称它为小港。 我小时候不知道港字是哪个字，后来才知道就是“港”字，而字典里“港”有“小河、小沟、小水道”的意思。之所以叫小港，因为还有条更大的小河叫大港，小港最终汇入到了大港。 如果小港在穿城而过或者在北方，我想它肯定会被赋予一个很好听的名字，但在农村，像小港这样的小河实在是太多了，多到每个镇都可能有好几条，所以我们都叫小港或者大港。

2026/3/28

如何用一根棍子测出地球有多大？复刻埃拉托色尼的春分实验

By Long Luo 天似穹庐，笼盖四野。仰望天空，头顶的苍穹如同一顶巨大的圆盖，将万物尽数笼罩；而脚下的大地辽阔无垠，行走其上却难见边界。在漫长的历史中，“天圆地方”的观念显得那样自然：天空是弯曲的，土地是平坦的。毕竟，对古人而言，大地实在太大了，大到穷尽一生也难以走到尽头，很难获知大地到底是什么样的形状。 <h2 id="我们脚下的大地是个球">我们脚下的大地是个球</h2> 在遥远的地中海彼岸，生活在古希腊的思想家们却通过观察到很多自然现象开始怀疑直觉，认识到其实大地并非平坦，而是一个巨大的球体。 公元前600年前后，古希腊哲学家毕达哥拉斯( $\textit{Pythagoras}$ )从美学观念出发，认为宇宙一定是和谐的、简单的，宇宙中所有天体的形状和它们的运动轨道都应该是完美的。他认为，一切立体图形中最美的是球形，因为球面上的任何一点离球心的距离都相等，所以天体一定是球形的，太阳、月亮是球形的，恒心天球是球形的，大地也一定是球形的 <a href="#fn1" class="footnote-ref" id="fnref1" role="doc-noteref">1</a> 。 古希腊著名哲学家亚里多士德( $\textit{Aristotle}$ )则提供了多个物理证据说明了地球是圆的：远去的帆船逐渐消失在地平线下，桅杆是最后消失的；当我们朝北或朝南运动时，所看到的星空是不相同的，例如越往北，北极星在天空的高度就越高；发生月食时，地球在月亮上的阴影是圆的。 如果大地真是一个球，那么一个不可回避的问题便随之而来：这个球究竟有多大？它的周长是多少？在没有卫星、没有望远镜的时代，这似乎是一个无解的难题。 <h2 id="埃拉托色尼的最美实验">埃拉托色尼的最美实验</h2> 几乎每一本讲述科学史的书都会讲述埃拉托色尼( $\textit{Eratosthenes}$ ) <a href="#fn2" class="footnote-ref" id="fnref2" role="doc-noteref">2</a> 测量地球实验。他仅凭阳光与影子，便完成了人类历史上第一次对地球大小的测量，这个实验也被评为世界最美实验之一 <a href="#fn3" class="footnote-ref" id="fnref3" role="doc-noteref">3</a>。 埃拉托斯特尼（公元前 276 —— 195 年）是亚历山大图书馆的馆长，也是古代最伟大的思想家之一，不仅博学多才，还是一位杰出的数学家和天文学家。不幸的是，亚历山大图书馆后来毁于战火，他的大部分著作也随之失传，但幸运的是，他用棍子的阴影计算地球大小的优雅方法得以保存。

2026/3/22

2007江苏高考数学第20题解析：一道通向黄金分割数的数列压轴题

By Long Luo 2007 年江苏高考数学卷第 20 题是一道颇具代表性的数列综合题。题目将等差数列与等比数列联系在一起，通过两列数的公共项建立方程关系，并逐步挖掘出数列背后的代数结构。 第一问利用公共项条件证明一个看似巧合的求和结论；第二问进一步由特殊项关系推出公比必须为整数，并证明整个等比数列都嵌入在等差数列之中；而最有趣的是第三问，当我们研究等比数列中何时会出现三项成等差数列时，竟然会得到一个十分熟悉的特殊数 —— 黄金分割数。 解答这道题不依赖复杂的技巧，只需要按照题目条件找到关系，列好方程即可。下面按照题目的三个小问，逐步分析其证明过程。 <div class="note primary"><ol start="20" type="1"> <li>（本题满分16分）</li> </ol> 已知 $\{ a_{n} \}$ 是等差数列， $\{ b_{n} \}$ 是公比为 $q$ 的等比数列， $a_1 = b_1$ ， $a_2 = b_2 \ne a_1$ 。记 $S_{n}$ 为数列 $\{ b_{n} \}$ 的前 $n$ 项和。 （1）若 $b_k = a_m$ （ $m, k$ 是大于 $2$ 的正整数），求证： $S_{k-1} = (m - 1)a_1$ ； （2）若 $b_3 = a_i$ （ $i$ 是某个正整数），求证： $q$ 是整数，且数列 $\{ b_n \}$ 中的每一项都是数列 $\{ a_{n} \}$ 中的项； （3）是否存在这样的正数 $q$ ，使等比数列 $\{ b_{n} \}$ 中有三项成等差数列？若存在，写出一个 $q$ 的值，并加以说明；若不存在，请说明理由。 </div>

2026/3/14

Google经典面试题: 鸡蛋应该怎么扔？

By Long Luo 微软、Google 等科技公司的面试题库中，流传着许多经典问题。小时候在杂志上看过微软那道著名的面试题 ——“为什么下水道井盖是圆的？”，当时觉得这类问题十分有趣，因为它考察的往往不是知识储备，而是分析问题的思维方式。 最近，我又重新翻到了 Google 的一道经典面试题 —— 双蛋问题（ $\textit{Two Eggs Problem}$ ）或者说鸡蛋掉落问题（ $\textit{Egg Dropping Puzzle}$ ）。与井盖问题不同，这道题更偏向数学推导与算法优化，但同样充满巧思。乍看之下，它只是一个简单的试验设计问题；深入分析后却会发现，其中隐藏着相当优美的最坏情况分析思想，是一道非常值得细细品味的经典题目。 这道题的原文如下： <div class="note primary">You work in a $100$ floor building and you get $2$ identical eggs. You need to figure out the highest floor an egg can be dropped without breaking. Find an algorithm that is minimizing number of throws in the worst-case scenario. 你站在一栋 $100$ 层高的大楼里，手中有 $2$ 个完全相同的鸡蛋。有一未知的临界楼层，鸡蛋从临界楼层以下扔下去，一定不会碎；从临界楼层以上丢下去，一定会碎。已知未碎的鸡蛋可以重复使用，碎了的鸡蛋就不能再往下扔了。要求即便在最坏情况下，尝试次数也要尽可能少。请问最少需要尝试多少次能够找到这个临界楼层？ </div> <h2 id="一个鸡蛋">一个鸡蛋</h2> 如果只有 $1$ 个鸡蛋，问题解法非常简单。我们别无选择，只能从一楼开始逐层测试。用这种方法一定能找到鸡蛋安全掉落的最高楼层：该楼层就是鸡蛋摔碎楼层的楼下一层。 那么在最坏情况下，最少需要尝试多少次？答案就是 $100$ 次。因为最坏的情况就是临界楼层为第 $100$ 层。如果鸡蛋在第 $100$ 层摔碎，则临界楼层为 $99$ 层。 <h2 id="两个鸡蛋">两个鸡蛋</h2> 如果有 $2$ 个鸡蛋，那么问题就变得有趣起来。此时我们允许试错一次，大家很自然会想到二分查找，但在这里并不是最优方案。如果最高安全楼层是 $49$ 层，一开始就在 $50$ 层扔下第一枚鸡蛋，鸡蛋直接摔碎，之后只能逐层测试 $49$ 次才能得到答案，总计尝试 $50$ 次。 既然一开始从 50 层扔下不可行，那么很容易想到隔少一点楼层扔下行不行呢？如果我们每隔 $10$ 层测试一次的话，那么依次在 $10, 20, 30, 40, 50$ 层扔鸡蛋，鸡蛋在 $50$ 层摔碎后，再逐层测试 $41 - 49$ 层即可得出答案，全程仅需 $14$ 次尝试。由此可见，每隔 $k$ 层测试一次是可行的思路。在这种策略下在最坏情况下的尝试次数：最坏场景是连续跳层直到鸡蛋摔碎，之后只能用仅剩的一个鸡蛋，在最后一段长度为 $k - 1$ 的区间内逐层排查。 那么尝试次数计算公式为：$\lfloor \dfrac {100}{k} \rfloor + (k - 1)$ 。注意到 $\dfrac {100}{k}$ 和 $k - 1$ 是此消彼长的关系，在大概 $k = 10$ 左右有极值，当 $k = 8, 9, 10, 11, 12, 13$ 时，计算得到最坏尝试次数为 $19$ 次。 那这个问题的正确答案是扔多少次呢？

2026/3/6

2010年江苏高考数学压轴题解析：巧用余弦定理与数学归纳法

By Long Luo 2010年江苏高考数学II卷的压轴题是一道竞赛味很浓的题，涉及群论( $\textit{Group Theory}$ ) <a href="#fn1" class="footnote-ref" id="fnref1" role="doc-noteref">1</a> 中有理数在四则运算下的封闭性，并需要结合余弦定理与数学归纳法进行递推证明。 如果对有理数的运算性质较为熟悉，这类问题解题思路非常简单；但若缺乏相关代数结构的理解，则容易在递推关系的构造上产生困难。 <div class="note primary">23、（本小题满分 10 分）已知 $\triangle ABC$ 的三边长为有理数。 <ol type="1"> <li>求证 $\cos A$ 是有理数；</li> <li>对任意正整数 $n$ ，求证 $\cos nA$ 也是有理数。</li> </ol> </div> <h2 id="分析">分析</h2> 第一问比较简单，利用余弦定理( $\textit{Law of Cosines}$ ) <a href="#fn2" class="footnote-ref" id="fnref2" role="doc-noteref">2</a> 可以将角度的余弦表达为三角形三边的代数组合。由于已知三边均为有理数 <a href="#fn3" class="footnote-ref" id="fnref3" role="doc-noteref">3</a>，因此可直接转化为有理数的四则运算问题，从而证明。 第二问的关键在于观察到角度之间存在递推关系，因此可以自然构造二阶递推关系式，并使用数学归纳法 <a href="#fn4" class="footnote-ref" id="fnref4" role="doc-noteref">4</a> 证明该性质在正整数范围内均成立。 <h2 id="第一问">第一问</h2> 设 $\triangle ABC$ 三边长分别为 $a, b, c$ ，因为 $a, b, c$ 是有理数，那么 $a, b, c$ 均可表示为 $\dfrac {m}{n}$（$m, n$ 为互质的整数）形式，根据余弦定理有： \[ \cos A = \dfrac{b^2 + c^2 - a^2}{2bc} \] 根据有理数在四则运算下具有封闭性，则分子 $b^2 + c^2 - a^2$ 是有理数，分母 $2bc$ 为有理数，所以 $\dfrac{b^2 + c^2 - a^2}{2bc}$ 必定为有理数，所以 $\cos A$ 是有理数。

2026/2/28

2011年清华大学自主招生数学题解析：一道经典数列题的解法与思路

By Long Luo 数学题中个人比较喜欢数列与不等式结合的题目，这类题主要对递推关系的观察、数列分析、不等式放缩和解题思路的构造都有较高要求，能体会到数学乐趣。今天来挑战一道2011年清华大学自主招生数学试题中的数列大题，这道题本身计算量不大，难度中等。本文将详细分析这道数列题的解题过程，希望能够帮助读者直观理解这类题目的解题思路。 <div class="note primary"><ol start="13" type="1"> <li>(本小题满分14分)</li> </ol> 已知函数 $f(x) = \dfrac{2x}{ax + b}$ ，$f(1) = 1$ ，$f(\dfrac{1}{2}) = \dfrac{2}{3}$ 。令 $x_1 = \dfrac{1}{2}$ ，$x_{n+1} = f(x_n)$ 。 <ol type="I"> <li>求数列 $\{ x_n \}$ 的通项公式；</li> <li>证明 $x_1x_2 \dots x_n > \dfrac{1}{2e}$ 。</li> </ol> </div> <h2 id="第一问">第一问</h2> 解：由 $f(1) = 1$ ，$f(\dfrac{1}{2}) = \dfrac{2}{3}$ 得： \[ \begin{cases} a + b = 2 \\ a + 2b = 3 \end{cases} \] 易得：$a = 1, \ b = 1$ ，所以 $f(x)$ 的表达式为： \[ f(x) = \frac{2x}{x+1} \label{1.1} \tag{1.1} \] <div class="note info">先求出数列 $\{ x_n \}$ 的前几项： $x_1 = \dfrac{1}{2}，x_2 = \dfrac{2}{3}，x_3 = \dfrac{4}{5}，x_4 = \dfrac{8}{9}$ ，可以猜测 $\{ x_n \}$ 通项公式为： \[ x_n = \frac{2^{n-1}}{2^{n-1} + 1} \label{1.2} \tag{1.2} \] </div>

2026/2/14

2006年江西高考理科数学压轴题解析：递推、放缩与不等式结构

By Long Luo 在 2005 - 2015 年江西高考自主命题时期，江西卷一直以鲜明的风格闻名全国，尤其是数学试卷，更因题目难度大、运算量惊人而被许多考生视为“噩梦级”存在。此前我们曾解析过 <a href="https://www.longluo.me/blog/2010-jiangxi-gaokao-math-exam-final-question/">2010年江西高考数学压轴题</a> ，一道融合数论的难题。 今天继续回顾江西卷另一道代表性压轴题：2006 年江西高考理科数学最后一题。这道题以数列为核心，将递推关系与不等式深度结合，综合性极强，即使放到今天来看，依然是一道颇具挑战性的高水平试题。 <div class="note primary"><ol start="22" type="1"> <li>(本小题满分 14 分)</li> </ol> 已知数列 $\{ a_n \}$ 满足： $a_1 = \dfrac{3}{2}$ ，且 $a_n = \dfrac {3na_{n-1}}{2a_{n-1} + n - 1}$ （ $n \geq 2$ ， $n \in \mathbb{N}^{*}$ ）. <ol type="i"> <li>求数列 $\{ a_n \}$ 的通项公式；</li> <li>证明：对于一切正整数 $n$ ，不等式 $a_1 \cdot a_2 \cdot \cdots \cdot a_n < 2 \cdot n!$ 恒成立。</li> </ol> </div> <h2 id="第一问">第一问</h2> <div class="note info">在没有头绪的时候，我们不妨先算出数列的前几项，推测数列可能的表达式。 容易计算出： $a_1 = \dfrac{3}{2}$ , $a_2 = \dfrac{9}{4}$ , $a_3 = \dfrac{81}{26}$ ， $a_3 = \dfrac{162}{40}$ 。 不过观察数列 $\{ a_n \}$ 前 4 项，仍然看不出什么规律，这个时候就要根据题设条件，找到数列的递推公式。 </div> 观察 $a_n = \dfrac {3na_{n-1}}{2a_{n-1} + n - 1}$ ，由于分子只有1项，而分母里既有 $a_{n-1}$ 又有 $n - 1$ ，这种情况下如果对原式取倒数更容易化简：

2026/2/7

一道初中数学极值题的多种解法：柯西不等式、几何法、函数法详解

By Long Luo 最近在短视频 App 里刷到不少中学数学题讲解，才发现现在的初中数学题，很多已经不只是“会算”这么简单了，背后往往还藏着不等式、函数、几何直觉等不同层面的思维训练。 当然，这也不算奇怪，几十年前的 IMO 试题放现在也就普通题。很多经典数学竞赛题，随着时间推移和教学资源普及，早已从高阶技巧逐渐变成了基础训练的一部分。 前几天我就反复刷到一道“求极值”的题，看起来不难，但这道题其实非常适合拿来练习数学直觉。 <div class="note primary">已知 $x + y = 5$ ，求 $\sqrt {x + 1} + \sqrt {y + 3}$ 的最大值。 </div> 看到这道题，首先想到的几何意义其实是将军饮马模型，但将军饮马问题求得是最小值问题。那最大值该怎么求呢？最大值的几何意义是什么呢？ 这道题的有趣之处在于可以用很多完全不同的思路来解决，有的解法只需要代数变形和基本不等式，也可以使用几何视角、函数思想。 下面就道题为例，把几种典型解法都梳理一遍，也顺便重新锻炼一下自己的数学思维。 <h2 id="解法一常规解法">解法一：常规解法</h2> 由 $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$ 。

2026/2/1

扔几个骰子，怎么算出期望？——拼多多校招笔试算法题的数学故事

By Long Luo 在上一篇文章我们剖析了 <a href="https://www.longluo.me/blog/pinduoduo-2020-campus-recruitment-coding-problems-magic-boxes/">拼多多 2020 年校招笔试算法题中第一题: 多多的魔术盒子</a> ，今天来挑战下其中的第 4 题：骰子期望 <a href="#fn1" class="footnote-ref" id="fnref1" role="doc-noteref">1</a> ，题目如下： <div class="note primary"><h2 id="骰子期望">骰子期望</h2> 扔 $n$ 个骰子，第 $i$ 个骰子有可能投掷出 $X_i$ 种等概率的不同的结果，数字从 $1$ 到 $X_i$ 。所有骰子的结果的最大值将作为最终结果。求最终结果的期望。 <ul> <li>输入描述: <ul> <li>第一行一个整数 $n$ ，表示有 $n$ 个骰子。( $1 \le n \le 50$ )</li> <li>第二行 $n$ 个整数，表示每个骰子的结果数 $X_i$ 。( $2 \le X_i \le 50$ )</li> </ul></li> <li>输出描述: <ul> <li>输出最终结果的期望，保留两位小数。</li> </ul></li> <li>输入例子 $1$ : <ul> <li>2</li> <li>2 2</li> </ul></li> <li>输出例子 $1$ : <ul> <li>1.75</li> </ul></li> </ul> </div> 要解答这道题，我们需要先从脑海里把中学数学知识捡起来，弄清楚什么是期望 <a href="#fn2" class="footnote-ref" id="fnref2" role="doc-noteref">2</a>？ 在概率论和统计学中，一个离散性随机变量的数学期望是试验中每次可能的结果乘以其结果概率的总和： \[ \operatorname {E} [X] = \sum _{i=1}^{\infty }x_{i}\,p_{i} \tag{1} \label{1} \] 具体到这道题示例 $1$ ，很明显 $2$ 个骰子只能取到 $1$ 或者 $2$ 个值： <ol type="1"> <li>假设这 $2$ 个骰子取到的最大值为 $1$ ，那么这 $2$ 个骰子都只能选择 $1$ ，概率为： $\dfrac {1}{2} \times \dfrac {1}{2} = \dfrac {1}{4}$ ；</li> <li>假设这 $2$ 个骰子取到的最大值为 $2$ ，那么存在 $2$ 种可能，要么都取 $2$ 或者 $2$ 个骰子中有一个骰子投出了 $2$ ，其概率为： $\dfrac {1}{2} \times \dfrac {1}{2} + \dfrac {1}{2} \times 1 = \dfrac {3}{4}$ 。</li> </ol> 那么期望为： $\dfrac {1}{4} \times 1 + \dfrac {3}{4} \times 2 = 1.75$ 。 对于骰子数少的时候还可以枚举，如果骰子数量很多呢？用上述方法就会遇到困难，比如有 $N$ 个骰子，最大值为 $M$ ，那么骰子结果为 $[1, 2, \dots, M]$ ，如何计算每个结果的概率值呢？ 直接算当然是可行的，但是如果骰子数量很多的话，计算会非常繁琐，所以有没有更简单的方法呢？

2025/2/1

拼多多校招笔试算法题：一行公式搞定“多多的魔术盒子”

By Long Luo 众多IT大厂中拼多多虽然工作强度很大，但在给钱方面非常大方。大厂给的钱多，但要求也高。下面就来挑战拼多多 2020 年校招笔试算法题 <a href="#fn1" class="footnote-ref" id="fnref1" role="doc-noteref">1</a> 中第一题：多多的魔术盒子 <a href="#fn2" class="footnote-ref" id="fnref2" role="doc-noteref">2</a> ，看看难度如何。 <div class="note primary"><h2 id="多多的魔术盒子">多多的魔术盒子</h2> 多多鸡有 $N$ 个魔术盒子(编号 $1 \sim N$ )，其中编号为 $i$ 的盒子里有 $i$ 个球。多多鸡让皮皮虾每次选择一个数字 $X$ ( $1 \le X \le N$ )，多多鸡就会把球数量大于等于 $X$ 个的盒子里的球减少 $X$ 个。通过观察，皮皮虾已经掌握了其中的奥秘，并且发现只要通过一定的操作顺序，可以用最少的次数将所有盒子里的球变没。 那么请问聪明的你，是否已经知道了应该如何操作呢？ <ul> <li>时间限制： <ul> <li>C/C++ 1秒，其他语言 2 秒</li> </ul></li> <li>空间限制： <ul> <li>C/C++ 256M，其他语言 512M</li> </ul></li> <li>输入描述: <ul> <li>第一行，有 $1$ 个整数 $T$ ，表示测试用例的组数。 ( $1 \le T \le 100$ )</li> <li>接下来 $T$ 行，每行 $1$ 个整数 $N$ ，表示有 $N$ 个魔术盒子。 ( $1 \le N \le 1,000,000,000$ )</li> </ul></li> <li>输出描述: <ul> <li>共 $T$ 行，每行 $1$ 个整数，表示要将所有盒子的球变没，最少需要进行多少次操作。</li> </ul></li> <li>输入例子 1 : <figure class="highlight txt"><table><tbody><tr><td class="gutter"><pre>1 2 3 4 </pre></td><td class="code"><pre>3 1 2 5 </pre></td></tr></tbody></table></figure></li> <li>输出例子 1 : <figure class="highlight txt"><table><tbody><tr><td class="gutter"><pre>1 2 3 </pre></td><td class="code"><pre>1 2 3 </pre></td></tr></tbody></table></figure></li> </ul> </div> <h2 id="最少的操作次数该怎么做">最少的操作次数该怎么做？</h2> 根据题意，我们关键是要找到最少次数这个方法，那如何操作才能使用最少次数呢？ 当面对复杂问题时，我们需要从简单情况入手，分析其中规律，找到突破口。 <ol type="1"> <li>$N = 1$ 时，显然选择 $X = 1$ ，需要 $1$ 次操作；</li> <li>$N = 2$ 时，可以先选择 $X = 1$ ，再选择 $X = 2$ ，需要 $2$ 次操作；</li> <li>$N = 3$ 时，只有先选择 $X = 2$ ，再选择 $X = 1$ ，最少需要 $2$ 次操作；</li> <li>$N = 4$ 时，可以先选择 $X = 2$ 或者 $X = 3$ ，最少需要 $3$ 次操作；</li> </ol> 通过分析发现，每次操作之后，球的数量都会动态变化。如果每次都选择中间的数字，这样每次操作之后，如果 $N$ 为奇数的话，可以变成 $2$ 个对称相同的数组， $N$ 为偶数的话，则 $2$ 个数组中元素值会相差 $1$ ，再选择元素值更多的数组进行消除，这样可以实现操作次数最少。 实现代码如下： <figure class="highlight java"><table><tbody><tr><td class="gutter"><pre>1 2 3 4 5 6 7 8 9 10 11 12 13 </pre></td><td class="code"><pre>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; } </pre></td></tr></tbody></table></figure> 为什么每次选取中间的数字进行操作次数最少呢？下面我们就来严谨的证明下！

2025/1/26

斯特林公式(Stirling's Formula)：我一个阶乘表达式，怎么就和圆扯上关系了呢？

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$ 来说很容易栈溢出。在实际应用中，往往需要计算大数的阶乘，即使目前最先进的计算机去处理极大数的阶乘时，也会面临需要巨大的计算及存储资源消耗问题。 <figure> <img src="https://www.longluo.me/assets/blog/images/time-complexity/comparison-computational-complexity.svg" title="Time Complexity Comparison" alt="图1. 不同算法时间复杂度 Time Complexity Comparison"> <figcaption aria-hidden="true">图1. 不同算法时间复杂度 Time Complexity Comparison</figcaption> </figure> 人们迫切需要找到一种可以快速计算阶乘的方法，在 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}$ )来证明，这里将介绍一种从零开始更易理解的推导方式。

2025/1/18

我爱做题：2010年江西高考理科数学压轴题

By Long Luo 知乎上有个问题是高考数学最后一题可以有多难？ <a href="#fn1" class="footnote-ref" id="fnref1" role="doc-noteref">1</a>，而公认史上最难高考数学题就是 <a href="https://www.longluo.me/blog/2008-jiangxi-gaokao-math-exam-final-question/">2008 年江西高考理科数学压轴题</a> 。2005 - 2014 年是江西自主命题，而江西卷也以题难计算量大著称，尤其是数学和理综。<a href="https://baike.baidu.com/item/%E9%99%B6%E5%B9%B3%E7%94%9F/3922596">陶平生老师</a> 是 2008 - 2011 年江西高考数学命题组长，参与了 2005 - 2011 年江西高考命题，他出江西数学卷时，是江西30多万学生被支配的恐惧！ 作为一名来自十八线农村做题家，高考时赶上了江西自主命题，在考场上也体会到了数学和理综卷题目居然没做完没思路的恐惧！中学时没能感受到数学的乐趣，最近几年看了一些数学书之后，重新拾起了数学的乐趣，经常找些数学题来训练下我的思维，今天就来挑战一下 2010 年江西高考理科数学压轴题： <div class="note primary"><ol start="22" type="1"> <li>（本小题满分14分）证明以下命题：</li> </ol> <ol type="1"> <li>对任意正整数 $a$ ，都存在正整数 $b, c$（ $b < c$ ）使得 $a^2, b^2, c^2$ 为等差数列.</li> <li>存在无穷多互不相似的三角形 $\triangle_n$ ，其边长 $a_n, b_n, c_n$ 为正整数且 $a_n^2, b_n^2, c_n^2$ 成等差数列.</li> </ol> </div> 这道题其实是数论( $\textit{Number theory}$ ) <a href="#fn2" class="footnote-ref" id="fnref2" role="doc-noteref">2</a> 背景，除了搞竞赛的同学，谁学过数论呢？这种构造性( $\textit{Constructive proof}$ ) <a href="#fn3" class="footnote-ref" id="fnref3" role="doc-noteref">3</a> 题目，没有接触过类似题目的话，根本不知道如何下手。要是我在考场上也会一脸懵圈，甚至在几年前我也是一筹莫展，不过现在倒是有勇气挑战这类题目了！网上关于这道题的参考答案太简略了，主要是如何找到答案的构造不清楚。这道题真是一道绝妙的题，我花了比较长时间来思考这道题，下面详细描述我的解题思路。 <h2 id="第一问">第一问</h2> 根据题意，正整数 $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$ 个推论： <ol type="1"> <li>$a ；</li> <li>$a$ 和 $c$ 要么都是偶数，要么都是奇数。</li> </ol> 因为 $a$ 为任意正整数，那么就从最简单的开始，不妨设 $a = 1$ ，则有： <ol type="1"> <li>令 $c = 1$ , 得 $b = 1$ ，与 $a 矛盾；</li> <li>令 $c = 3$ , 得 $b = \sqrt {5}$ ，与 $b$ 为正整数矛盾；</li> <li>令 $c = 5$ , 得 $b = \sqrt {13}$ ，与 $b$ 为正整数矛盾；</li> <li>令 $c = 7$ , 得 $b = 5$ ，满足条件。</li> </ol> 简单猜测实验得到一组要求的值： $a = 1$ , $b = 5$ , $c = 7$ 。 再设 $a = 2$ ，同理有： <ol type="1"> <li>令 $c = 4$ , 得 $b = \sqrt {10}$ ，与 $b$ 为正整数矛盾；</li> <li>令 $c = 6$ , 得 $b = 2 \sqrt {5}$ ，与 $b$ 为正整数矛盾；</li> <li>令 $c = 8$ , 得 $b = \sqrt {34}$ ，与 $b$ 为正整数矛盾；</li> <li>令 $c = 10$ , 得 $b = 2 \sqrt {13}$ ，与 $b$ 为正整数矛盾；</li> <li>令 $c = 12$ , 得 $b = \sqrt {74}$ ，与 $b$ 为正整数矛盾；</li> <li>令 $c = 14$ , 得 $b = 10$ ，满足条件。</li> </ol> 通过实验又得到一组要求的值： $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)得证。

2025/1/10

热机的效率上限在哪里？解析卡诺循环（Carnot Cycle）

By Long Luo 无论是家中的冰箱和空调，还是天上的飞机、水中的轮船、路上的汽车，它们本质上都属于热机 <a href="#fn1" class="footnote-ref" id="fnref1" role="doc-noteref">1</a>。或许有人会疑惑：冰箱和空调明明是用电的，怎么能和烧油的归为一类呢？事实上，这些机器虽然形式各异，但原理上都涉及热能的转换。它们早已融入我们的日常生活，而对大多数人而言，知道它们是机器已经足够了。 人类一直以来都在努力提高机器的效率，从而更好的为我们服务。以汽车为例，目前汽油发动机的热效率大约为 $30\%$ ，柴油机稍高一些，可达 $40\%$ ，而电动机的效率则高达 $90\%$ ，部分甚至可以达到 $95\%$ 。为什么燃油发动机的效率远远低于电动机呢？主要原因在于电动机可以直接将电能转换为机械能，结构简单，损耗极少。而燃油发动机则涉及多个能量转换环节，结构复杂，损耗较大。 假如我们忽略燃油发动机的一切损耗，它的效率是否能达到 $100\%$ 呢？我曾一度认为可以，但后来发现并非如此。要解答这个问题，我们需要先从水流谈起。 <h2 id="水轮机">水轮机</h2> 把手放进流动的水中，我们可以明显感觉到水流的冲击力，水流越大越快，冲击力也就越大。人类很早就意识到了流水中蕴藏的能量，并用流水来驱动水车，用于灌溉、磨坊等，下图 1 所示为位于比利时一家磨坊的水车。水车虽好，但需要稳定的水流，旱季时水力不足，运转乏力甚至无法运行，如何才能一年四季不因雨量不同而影响水车运转呢？ <figure> <img src="https://www.longluo.me/assets/blog/images/turbine/waterwheel-braine-le-chateau.jpg" alt="图1. 水车 Waterwheel"> <figcaption aria-hidden="true">图1. 水车 Waterwheel</figcaption> </figure> 答案很明显，修水坝，在雨季时把富余的水存储在高处，这样旱季时也能保证水车的正常运转。这一策略一直沿用了几千年，到现在无非就是大坝修得更高更好，水车换成了水轮机，驱动磨坊变成了发电而已。水在高处时，具有重力势能越大，但如果我们在高山湖泊中放置一台水车时，水车是不会转动的，因为湖泊中的水并不一定在流动，即使在流动，流速也很小，并不足以驱动水轮机。 <figure> <img src="https://www.longluo.me/assets/blog/images/turbine/vertical-waterwheel-simple.svg" alt="图2. 水轮"> <figcaption aria-hidden="true">图2. 水轮</figcaption> </figure> 只有当水从高处流向低处时，势能才能转化为动能，推动水轮机从而进行机械作功，实现能量的转化与利用。 <figure> <img src="https://www.longluo.me/assets/blog/images/turbine/overshot-waterwheel-simple.svg" alt="图3. 流动的水驱动水车"> <figcaption aria-hidden="true">图3. 流动的水驱动水车</figcaption> </figure> 从上图也可以看出，驱动水车的关键在于水的流动，而不在于水的多少。高山湖泊的水虽然重力势能很大，而且数量巨大，但是除非这些水从高处流下，否则并不能对外做功。

2025/1/5

为什么 2024 年会有 366 天？

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 天？要回答这个问题，我们需要穿越历史的迷雾，回顾人类文明史，才能找到答案。 <h2 id="逝者如斯夫不舍昼夜">逝者如斯夫，不舍昼夜！</h2> 《鲁滨逊漂流记》中的鲁滨逊流落到荒岛之后第一时间就是竖起了一根大柱子，用刀子在立柱上刻上凹口当作日历。一方面是因为鲁滨逊是基督徒需要做礼拜，另外一方面也是为了记录时间。我们的现代生活是离不开钟表的，如果没有钟表来量化时间的话，我们的工作生活将失去秩序。当然鲁滨逊在荒岛上也只能过着“日出而作，日落而息”的农业社会生活，无法精确的安排工作和生活。 “朝菌不知晦朔，蟪蛄不知春秋”，我们智人的寿命足够长，不像朝生暮死的蜉蝣，也不似春生夏死的寒蝉，可以目睹很多生命的诞生、成长以及消亡，感受时间的流逝。“逝者如斯夫，不舍昼夜！”，时间的洪流永远奔涌向前，然而虽然以我们生命的长度可以跨越四季与年轮，但是依然无法触及时间的尽头。 寄蜉蝣于天地，渺沧海之一粟。哀吾生之须臾，羡长江之无穷。当然我们现在知道时间并不是均匀流逝的，也不能脱离物质而存在，但在足够宏大的尺度上，时间在均匀的流逝着。 虽然你可能没有意识到，但是我们一直都在用着天然的时钟，它们就位于我们头顶的星空。这些时钟都足够精准，地球自转的每日误差在毫秒级别，月球公转和地球公转上百年也仅有几毫秒的差别。 “日出东南隅，照我秦氏楼。”，新的一天又开始了；残月如弓，新月如眉，满月如镜，周而复始；“未觉池塘春草梦，阶前梧叶已秋声。”，四季轮回时，我们知道新的一年又来临了。

2024/12/21

数学之美：几何视角下的高斯积分(Gaussian Integral)

By Long Luo 从之前的文章 <a href="https://www.longluo.me/blog/normal-distribution/">正态分布(Normal Distribution)公式为什么长这样？</a> 和 <a href="https://www.longluo.me/blog/least-squares-and-normal-distribution/">从最小二乘法到正态分布：高斯是如何找到失踪的谷神星的？</a> ，我们使用了 $2$ 种不同的方法最终得到了如下公式 $(1)$ 所示的误差的概率密度函数 ( $\text{Probability Density Function}$ ) ： \[ f(x) = \mathrm{e}^{-cx^2}, \, c > 0 \tag{1} \label{1} \] 其函数图像如下图 1 所示的钟形曲线 ( $\text{Bell Curve}$ ) ： <figure> <img src="https://www.longluo.me/assets/blog/images/normal-distribution/standard-deviation-diagram-micro.svg" alt="图1. 钟形曲曲线"> <figcaption aria-hidden="true">图1. 钟形曲曲线</figcaption> </figure> 在概率论中，我们需要保证上图 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}$ 。 那么什么是高斯积分呢？高斯积分和圆有什么关系呢？

2024/5/11

从最小二乘法到正态分布：高斯是如何找到失踪的谷神星的？

By Long Luo 在上一篇文章 <a href="https://www.longluo.me/blog/normal-distribution/">正态分布(Normal Distribution)公式为什么长这样？</a> 中，我们使用了投掷飞镖的模型，推导出了正态分布( $\text{Normal Distribution}$ )的表达式。这种方法既优雅又直观，所以常被用于科普视频或者文章中。那么这个例子是怎么来的呢？我们知道这个方法是天文学家赫歇尔（ $\text{John Herschel}$ ）在 1850 年给出的，难道他在投掷飞镖时想到的吗？ 答案是否定的，原因是因为赫歇尔作为一个天文学家，需要精确的测量天体的位置，而在观测星星时，必须要考虑误差的影响。星星在天球中的位置误差是二维的，考虑到误差大家不太好理解，所以用了投掷飞镖这个更通俗易懂的例子。 正如法国著名哲学家孔德( $\text{Auguste Comte}$ ，1798-1857)所说“To understand a science, it is necessary to know its history. ”，只有了解这个学科的发展历史，了解这个学科的重要概念是如何建立起来的，才能真正理解这个学科。不同于我们在课本中学习顺序，科学是用来解决实际问题的，科学是由一个个问题所驱动发展的。正如仅次牛顿和爱因斯坦的伟大物理学家麦克斯韦( $\text{James Clerk Maxwell}$ ) 曾说过“It is of great advantage to the student of any subject to read the original memoirs on that subject, for science is always most completely assimilated when it is in the nascent state…”，我们学习历史上科学家是如何解决这些问题，用了什么方法，才能获取某个概念的 insight ，建立 intuition 。 正态分布，又被称为高斯分布（ $\text{Gaussian Distribution}$ ），人们可能会以为正态分布是由高斯发现的，但事实并非如此！ 正态分布最早是由法国数学家棣莫弗( $\text{Abraham de Moivre}$ , 1667-1754)在 1718 年左右发现的。他为了解决朋友提出的一个赌博问题，而去认真研究了二项分布。他发现当实验次数增大时，二项分布( $p=0.5$ )趋近于一个看起来呈钟形的曲线，如下图 1 所示。后来著名法国数学家拉普拉斯( $\text{Pierre-Simon Laplace}$ , 1749-1827)对此作了更详细的研究，并证明了 $p \ne 0.5$ 时二项分布的极限也是正态分布。之后人们便将此称为棣莫弗 - 拉普拉斯中心极限定理（ $\text{Central limit theorem}$ ）。 <figure> <img src="https://www.longluo.me/assets/blog/images/probability/de-moivre-laplace.gif" alt="图1. 二项分布趋近钟形曲线"> <figcaption aria-hidden="true">图1. 二项分布趋近钟形曲线</figcaption> </figure> <h2 id="失踪的谷神星">失踪的谷神星</h2> 16 和 17 世纪是天文学发展的黄金时期，这一时期的科学革命彻底改变了人类对宇宙的理解。哥白尼( $\text{Nicolaus Copernicus}$ ，1473-1543)的日心说、开普勒( $\text{Johannes Kepler}$ ，1571-1630)的行星运动三定律、伽利略( $\text{Galileo Galilei}$ ，1564-1642)的望远镜观测以及牛顿( $\text{Isaac Newton}$ ，1643-1727)的万有引力定律共同构成了现代天文学的基础。这一时期的科学家们不仅改变了人类对宇宙的理解，还为后续的科学研究提供了重要的方法和工具。

2024/5/2

正态分布(Normal Distribution)公式为什么长这样？

By Long Luo 相信大家或多或少都听过六西格玛( $\text{6 Sigma}$ ) <a href="#fn1" class="footnote-ref" id="fnref1" role="doc-noteref">1</a> 这个词，六西格玛是指生产的产品中， $99.99966\%$ 的产品是没有质量问题的，即只有 $3.4ppm$ 的不良率。 假如一家工厂生产某型号零件，零件的长度要求是 $100mm$ ，允许的标准差是 $0.1mm$ 。根据 $6 \sigma$ 原则，零件规格允许的偏差范围是： $100 \pm 6 \times 0.1 = 100 \pm 0.6$ 。 这意味着，零件长度超过 $100.6mm$ 或低于 $99.4mm$ 的概率是非常低的，约为 $0.00034\%$ 。如果工厂每天生产 100 万个零件，只允许有 $3.4$ 个零件会超出 $6 \sigma$ 的范围，几乎可以忽略不计。因此，生产过程是极其稳定和可靠的，达到了六西格玛水平。 那么 $6 \sigma$ 中 $3.4ppm$ 的不良率来自哪里呢？ 学过中学数学都知道，在正态分布( $\text{Normal Distribution}$ ) <a href="#fn2" class="footnote-ref" id="fnref2" role="doc-noteref">2</a> 中， $68.27\%$ 的数据位于平均值的一个标准差内， $95.45\%$ 位于两个标准差内， $99.73\%$ 位于三个标准差内，这也是著名的 68-95-99.7 Rule <a href="#fn3" class="footnote-ref" id="fnref3" role="doc-noteref">3</a> ，如下图 1 所示： <figure> <img src="https://www.longluo.me/assets/blog/images/normal-distribution/standard-deviation-diagram-micro.svg" alt="图1. 68-95-99.7 Rule"> <figcaption aria-hidden="true">图1. 68-95-99.7 Rule</figcaption> </figure> <h2 id="什么是正态分布">什么是正态分布？</h2> 数据可以用不同的方式“分布”，比如数据可以向左散布的多一些，也可以向右散布的多一些，或者分布的乱七八糟，如下图 2 - 4 所示， <figure> <img src="https://www.longluo.me/assets/blog/images/normal-distribution/normal-distribution-skew-left.gif" alt="图2. 数据偏向左散布"> <figcaption aria-hidden="true">图2. 数据偏向左散布</figcaption> </figure> <figure> <img src="https://www.longluo.me/assets/blog/images/normal-distribution/normal-distribution-skew-right.gif" alt="图3. 数据偏向右散布"> <figcaption aria-hidden="true">图3. 数据偏向右散布</figcaption> </figure> <figure> <img src="https://www.longluo.me/assets/blog/images/normal-distribution/normal-distribution-random.gif" alt="图4. 数据随机分布"> <figcaption aria-hidden="true">图4. 数据随机分布</figcaption> </figure> 但数据经常会集中在一个中心值的附近，而不向左或右偏斜，像一个钟形，如下图 5 所示。 <figure> <img src="https://www.longluo.me/assets/blog/images/normal-distribution/empirical-rule-histogram.svg" alt="图5. 数据正态分布"> <figcaption aria-hidden="true">图5. 数据正态分布</figcaption> </figure> 正态分布，又称高斯分布（ $\text{Gaussian Distribution}$ ），是一种重要的概率分布，数学王子高斯 <a href="#fn4" class="footnote-ref" id="fnref4" role="doc-noteref">4</a> 在正态分布的研究和应用上做出了巨大贡献。有很多日常现象都符合这种分布，如人的身高、考试成绩等。正因为它几乎无处不在，所以叫 $\text{Normal Distribution}$ 。德国曾经发行的一款 10 马克的纸币上就印着高斯和正态分布曲线，如下图 6 所示。 <figure> <img src="https://www.longluo.me/assets/blog/images/normal-distribution/gauss-10-mark.jpg" alt="图6. 高斯和正态分布曲线"> <figcaption aria-hidden="true">图6. 高斯和正态分布曲线</figcaption> </figure>

2024/4/27

高速公路编号背后的数学密码

By Long Luo 世界那么大，我想去看看！随着科技的发展，我们早已做到无需离开家就能领略世界各地的风景和文化。通过高清视频、高清直播、社交媒体、 VR 技术、各种图片或者视频分享平台，我们不仅可以体验世界名胜古迹、自然美景和各地的风土人情，还能与当地居民互动，了解他们的日常生活和传统文化。互联网丰富了人们的生活，缩小了地域的界限，真正实现了让世界触手可及，足不出户便可周游世界的梦想。但正所谓“百闻不如一见”，“读万卷书，不如行万里路！”，尽管互联网让我们可以虚拟游览世界，但亲自出行的体验无可替代。自由行不仅提供了前所未有的自由和灵活性，还能让我们亲身感受到大自然的美妙、城市的活力。这种身临其境的体验，远非屏幕前的感受可比。 当你打开地图软件时，你会看到如图 1 所示的道路标志， <figure> <img src="https://www.longluo.me/assets/blog/images/road/highway-mark.png" alt="图1. 道路编号"> <figcaption aria-hidden="true">图1. 道路编号</figcaption> </figure> 当你在道路出行时，你也会看到看到如下图 2 所示的路牌，但你可能并未真正留意过这些标志。因为现在我们只需要有一部联网的智能手机，在地图类软件里，设定出发地和目的地，自然有导航会指引我们到达目的地。 <figure> <img src="https://www.longluo.me/assets/blog/images/road/china-expwy-g35-sign-with-name-in-luogang-tollgate.jpg" alt="图2. G35 高速萝岗路段"> <figcaption aria-hidden="true">图2. G35 高速萝岗路段</figcaption> </figure> 这些编号肯定不是随机的，那么这些道路编号到底有什么用呢？出于好奇心你可能会去寻找答案，你很容易轻松找到中国国家高速的编号密码 <a href="#fn1" class="footnote-ref" id="fnref1" role="doc-noteref">1</a> 和高速公路是怎样命名和编号 <a href="#fn2" class="footnote-ref" id="fnref2" role="doc-noteref">2</a> 这样的文章。但这些文章只是告诉我们是什么，并没有告诉我们为什么。 国内现行的高速公路命名是由交通部从 2005 年启动的 <a href="#fn3" class="footnote-ref" id="fnref3" role="doc-noteref">3</a> ，之前道路都以起始地和终点地命名。你可能会想，之前那种命名方式不是更合理吗？用了数字不是更加不清晰易懂吗？如果图 1 不是路牌上写了济广高速，谁知道 G35 <a href="#fn4" class="footnote-ref" id="fnref4" role="doc-noteref">4</a> 是哪里到哪里呢？ 如果你更进一步的话，如果你去了解世界其他国家的高速公路命名的话，你会惊讶的地发现为什么居然全世界各主要大国都选择了类似的编号系统，这背后的原因是什么呢？ 要回答这个问题，我们需要把时钟拨回几十年前，回到高速公路诞生的时期，那个没有 GPS ，没有手机，只有纸质地图的时代，我们才能知道这种编号系统的重要意义和实用性，以及背后的数学密码。 <h2 id="世界各国如何对高速公路进行编号">世界各国如何对高速公路进行编号？</h2> 我们已经了解了国内高速公路编号 <a href="#fn5" class="footnote-ref" id="fnref5" role="doc-noteref">5</a> ，让我们看看其他国家的高速公路系统编号是什么样的。这些国家需要国土面积足够大，高速公路系统足够发达，国土疆域长宽比例没有太夸张，人口分布比较均匀。

2024/4/21

2024阿里巴巴全球数学竞赛预选赛试题及解答

By Long Luo <a href="https://damo.alibaba.com/?language=zh">阿里巴巴达摩院</a> 从 2018 年开始每年都会举办一届全球数学竞赛，之前一方面自己数学水平比较弱，另外一方面也没有报名，但一直很仰慕那些数学大神的风采。今年是第一次报名参加 <a href="https://damo.alibaba.com/alibaba-global-mathematics-competition?language=zh">2024阿里巴巴全球数学竞赛</a> ，上周末参加了预选赛，但遗憾的是，全部 $7$ 道题中只有第 $1, 2, 6$ 题会做，这里分享下我的解答： <h2 id="problem-1">Problem 1</h2> 几位同学假期组成一个小组去某市旅游. 该市有 $6$ 座塔，它们的位置分别为 $A, B, C, D, E, F$ 。同学们自由行动一段时间后，每位同学都发现，自己在所在的位置只能看到位于 $A, B, C, D$ 处的四座塔，而看不到位于 $E$ 和 $F$ 的塔。已知： <ol type="1"> <li>同学们的位置和塔的位置均视为同一平面上的点，且这些点彼此不重合；</li> <li>塔中任意 $3$ 点不共线；</li> <li>看不到塔的唯一可能就是视线被其它的塔所阻挡，例如，如果某位同学所在的位置 $P$ 和 $A, B$ 共线，且 $A$ 在线段 $PB$ 上，那么该同学就看不到位于 $B$ 处的塔。</li> </ol> （5 分） 请问这个旅游小组最多可能有多少名同学？ $A. \ 3 \qquad B. \ 4 \qquad C. \ 6 \qquad D. \ 12$ <h3 id="solution">Solution</h3> 这道题选 $C$ ，最多只能有 $6$ 名同学。 <div class="note info">这道题的解题思路是从假设只有 $1$ 座塔开始，一直到 $6$ 座塔，找到思路。 </div> <ol type="1"> <li>假设有 $1$ 座塔 $A$ ，那么很显然有无数多同学可以看到塔 $A$ ，也可以有无数多同学看不到塔 $A$ ；</li> <li>假设有 $2$ 座塔 $A, B$ ，那么只有以 $A$ 为起点的射线 $AB$ 且位于 $B$ 之后的同学无法看到塔 $A$ ；</li> <li>假设有 $3$ 座塔 $A, B, C$ ，同理可知存在无数位同学至少可以看见 $2$ 座塔；</li> <li>假设有 $4$ 座塔 $A, B, C, D$ ，同理可知存在无数位同学至少可以看见 $2$ 座塔；</li> <li>假设有 $6$ 座塔 $A, B, C, D, E, F$ ，如果每位同学都无法看见 $E, F$ 塔，如下图1 所示：</li> </ol> <figure> <img src="https://www.longluo.me/assets/blog/images/math/2024-alibaba-math-contest-problem1-solution.png" alt="图1. Solution of Problem 1"> <figcaption aria-hidden="true">图1. Solution of Problem 1</figcaption> </figure> 所以至多有 $6$ 位同学位于 $M, N, O, P, R, Q$ 处，无法看到塔 $E, F$ 。

2024/4/16

库函数 (libm) 是如何计算三角函数值的？

By Long Luo <h2 id="挖坑">挖坑！</h2> <figure class="highlight java"><table><tbody><tr><td

2024/2/16

payne hanek 归约算法

By Long Luo <h2 id="挖坑">挖坑</h2> <h2 id="参考文献">参考文献</h2> <ol type="1"> <li><a

2024/1/22

音乐背后的数学

By Long Luo <h2 id="挖坑">挖坑</h2> <h2 id="声音是什么">声音是什么？</h2> <h2 id="什么是和弦">什么是和弦？</h2> <h2

2024/1/12

素描背后的物理

By Long Luo <h1 id="挖坑">挖坑</h1> <h1 id="参考文献">参考文献</h1> <ol type="1"> <li><a

2023/12/30

cody waite

By Long Luo <h2 id="挖坑">挖坑</h2> <h2 id="参考文献">参考文献</h2> <ol type="1"> <li><a

2023/12/19

浮点数

By Long Luo <h2 id="挖坑">挖坑</h2> 假如你知道浮点数的话，你就知道为什么了！ 按照 IEEE 754 浮点数标准制定的浮点数运算法则，

2023/12/3

Remez Algorithm

By Long Luo <h2

2023/10/6

参数归约算法(Argument Range Reduction)：如何在浮点数环境下计算超大数字的三角函数值？

By Long Luo 之前写过一篇介绍 CORDIC 算法 <a href="#fn1" class="footnote-ref" id="fnref1" role="doc-noteref">1</a> 的文章，里面提到 CORDIC 算法的 <a href="https://www.longluo.me/blog/cordic/#cordic-%E7%AE%97%E6%B3%95%E7%9A%84%E4%B8%8D%E8%B6%B3">不足</a> 之处，CORDIC 算法的输入角度范围需要在 $[−99.88^{\circ} , 99.88^{\circ}]$ ，那么我们不禁要问，如果输入角度 $\large {\theta }$ 很大的话，怎么处理呢？ 这个问题同样存在于泰勒展开式(Taylor series) <a href="#fn2" class="footnote-ref" id="fnref2" role="doc-noteref">2</a> 中，比如 $\large {\sin (x) }$ 和 $\large {\cos (x) }$ 的泰勒展开式： \[ \sin(x) = x - \frac {1}{3!}x^3 + \frac {1}{5!}x^5 - \frac {1}{7!} x^7 + \frac {1}{9!} x^9 + o(x^9) \quad \forall x \subset \mathbb{R} \] \[ \cos(x) = 1 - \frac {1}{2!}x^2 + \frac {1}{4!}x^4 - \frac {1}{6!} x^6 + \frac {1}{8!} x^8 + o(x^8) \quad \forall x \subset \mathbb{R} \] 虽然在整个实数集 $\large { \mathbb{R}}$ 都成立，但是在实际应用中因为展开项数限制和浮点数的精度限制， $\large {x}$ 的范围只有在接近 $\large {0}$ 的时候才有比较高的精度。 但是实际应用中，如果输入 $\large {x}$ 很大的话，比如 $\large {2^{32}, 10^{10}, 10^{22} \dots }$ 情况下怎么得到足够精确的值呢？ 中学里我们知道三角函数是周期函数，对于比较大的值，我们可以使用下面的公式将值归约到一个比较小的范围内。 \[ x' = x - 2k \pi \quad k \subset \mathbb{Z} \] 这就是我们今天要讲的 参数归约(Argument Reduction) 算法。 <h2 id="从小学计算题开始">从小学计算题开始</h2> 参数归约 听起来就很唬人，什么是参数啊，什么归约啊，都是些高大上的名词，听起来云里雾里的！ 为了不让大家产生厌倦和畏难心理，我们先从一道小学数学计算题开始： 不借助计算器，计算 $\large {66600 \times 666000}$ 的值！ 对于这道题，大家可能会列出下列算术： \[ 66600 \times 666000 = 666 \times 666 \times 100000 = 44355600000 \] 但其实呢，我们也可以使用下面的方法： \[ \begin{aligned} 66600 \times 666000 &= 111^2 \times 4 \times 9 \times 10^5 \\&= 444 \times 999 \times 10^5 \\&= 444 \times (1000 - 1) \times 10^5 \\&= 4443556 \times 10^5 \end{aligned} \] 如果我说上面这 $\large {2}$ 种方法都用到了参数归约的思想，你可能会感到震惊，什么？这种小学计算题也用到了参数归约算法吗？

2023/9/16

素描背后的数学

By Long Luo <h2 id="挖坑">挖坑</h2> <h2 id="参考文献">参考文献</h2> <ol type="1"> <li><a

2023/8/2

发生在计算机内存里的进化：解密遗传算法(Genetic Algorithm)

By Long Luo 这篇文章部分内容还在优化，Demo 还在继续开发，大概还需要 7 - 8 小时写作时间。 无限猴子定理（英语：Infinite monkey theorem） 让一只猴子在打字机上随机地按键，当按键时间达到无穷时，几乎必然能够打出任何给定的文字，比如莎士比亚的全套著作。 在这里，几乎必然是一个有特定含义的数学术语，“猴子”也不是一只真正意义上的猴子，它被用来比喻成一个可以产生无限随机字母序列的抽象设备。这个理论说明把一个很大但有限的数看成无限的推论是错误的。猴子精确地通过键盘敲打出一部完整的作品比如说莎士比亚的哈姆雷特，在宇宙的生命周期中发生的概率也是极其低的，但并不是零。 遗传算法(Genetic Algorithm) <a href="#fn1" class="footnote-ref" id="fnref1" role="doc-noteref">1</a> 是一种元启发式搜索和优化技术，借鉴了生物进化中的自然选择和遗传机制。它已经在各个领域展示出了强大的应用潜力。本文将介绍遗传算法的发展历史、原理、示例，以及其广泛应用和不足之处。 <h2 id="发展历史">发展历史</h2> 遗传算法的发展可以追溯到上世纪60年代的约翰·荷兰德（John Holland）和他的同事们的工作。他们首先提出了基因型与表现型之间的映射关系，并通过模拟生物进化过程来解决复杂的优化问题。 <h2 id="原理">原理</h2> 遗传算法的核心原理是模拟自然进化的过程。它通过定义适应度函数来评估候选解的质量，并利用遗传操作（选择、交叉和变异）对候选解进行迭代改进。具体而言，算法从一个初始种群开始，通过选择适应度较高的个体作为父代，进行交叉和变异操作产生新的后代个体，然后通过评估适应度来选择出下一代个体。这个过程不断迭代，直到找到满足特定条件的优秀解。 It’s never too late <h2 id="举个例子">举个例子</h2> 目前参考网络资源写了一个简单的Demo，地址：http://longluo.me/projects/genetic 这个例子还有待完善！ <a href="http://longluo.me/projects/genetic"><img src="https://user-images.githubusercontent.com/3395062/247012809-febec500-50dd-4d52-a6f6-d5b86aba4132.png" alt="Genetic Algorithm"></a>

2023/6/12

CORDIC算法：一种高效计算三角函数值的方法

By Long Luo 任何一款科学计算器上都可以计算三角函数，三角函数应用于生活工作中的方方面面，但计算机是如何计算三角函数值的呢？ 三角函数本质上是直角三角形的3条边的比例关系，计算并没有很直观，那么计算机是如何计算三角函数值的呢？ 在微积分中我们学习过 <a href="https://www.longluo.me/blog/taylor-series/">泰勒公式</a> ，我们知道可以使用泰勒展开式来对某个值求得其近似值，例如： \[ \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 <a href="#fn1" class="footnote-ref" id="fnref1" role="doc-noteref">1</a> 算法之前，我一直以为计算器是利用泰勒公式去求解，最近才了解到原来在计算机中，CORDIC 算法远比泰勒公式高效。 下面我们就来了解下泰勒公式的不足之处和 CORDIC 算法是怎么做的。 <h2 id="泰勒公式的缺点">泰勒公式的缺点</h2> 上一节我们使用泰勒公式去计算三角函数值时，需要做很多次乘法运算，而计算器中乘法运算是很昂贵的，其缺点如下所示： <ol type="1"> <li>展开过小则会导致展开精度不够，展开过大则会导致计算量过大；</li> <li>幂运算需要使用乘法器，存在很多重复计算；</li> <li>需要很多变量来存储中间值。</li> </ol> 在之前的文章 <a href="https://www.longluo.me/blog/strassens-matrix-multiplication-algorithm/">矩阵乘法的 Strassen 算法</a> ，就是通过减少乘法，多做加法，从而大大降低了运算量，那么我们可以用相同的思想来优化运算吗？ 当然可以，让我们请出今天的主角：CORDIC 算法。

2023/6/7

墨卡托的魔术：地图是如何欺骗你的眼睛的？

By Long Luo 最近在书店里看到一本 <a href="https://book.douban.com/subject/35548116/">《数学的奥秘》</a> ，原著是《The Secret Life of Equations: The 50 Greatest Equations and How They Work》，讲的是最伟大的数学方程式起源、构成、含义和应用。书的内容并不多，我看了其中的一部分，里面有讲墨卡托投影( $\textit{Mercator projection}$ )<a href="#fn1" class="footnote-ref" id="fnref1" role="doc-noteref">1</a> 。 我对地理和地图一直很感兴趣，但之前对原理一直一知半解的，只知道我们常见的地图都是墨卡托投影，由墨卡托( $\textit{Gerardus Mercator}$ )<a href="#fn2" class="footnote-ref" id="fnref2" role="doc-noteref">2</a> 在 1569年创立。但墨卡托投影的原理是什么却并不清楚。书里面只有几页，但具体公式缺乏说明及推导过程，所以这几天通过查找资料掌握了墨卡托投影的原理。 <h2 id="如何绘制地图">如何绘制地图？</h2> 在大航海时代，航海家可以通过六分仪和观察日月星辰获取到经纬度，但在茫茫大海中迷失方向是很可怕的事情，如何才能正确的航行到目的地呢？ 地球由于自转是一个两极比赤道略短的扁球体，但扁率约为 $\dfrac {1}{300}$ ，非常之低，因为可以视为球体。因为球面不是可展曲面，也就是如果展成平面的话，长度会发生形变，所以也会形变。因为根据高斯绝妙定理 ( $\textit{Theorema Egregium}$ )<a href="#fn3" class="footnote-ref" id="fnref3" role="doc-noteref">3</a> ，平面的高斯曲率为 $0$ ，而球面的高斯曲率为 $\dfrac {1}{R^2}$ ，其中 $R$ 为球面半径，所以在保持图形完整性前提下，将球面转化为平面，投影后得到的经纬线网形状必然会产生变形，也就是说，在投影的过程中，变形是必然存在的。 在这种情况下，墨卡托运用等角圆柱投影法绘制了航海图，极大地方便了航海家。有了墨卡托海图，航海家想要到达某个目的地，只需要在出发点和目的地之间连一条直线，量出这条航线和经线的夹角，按照航行路线就能到达目的地。 <figure> <img src="https://www.longluo.me/assets/blog/images/map/earth-map-mercator.jpg" alt="图1. 地图的墨卡托投影"> <figcaption aria-hidden="true">图1. 地图的墨卡托投影</figcaption> </figure> <h2 id="什么是墨卡托投影">什么是墨卡托投影？</h2> 设想将地球置于在一中空的圆柱里，如下图所示，其基准纬线（赤道）与圆柱相切。再设想地球中心处放置一灯泡，那么从球心处发射的光线会把球面上的图形投影到圆柱体上，之后再将把圆柱体展开，那么就可以得到一张墨卡托投影绘制出的地图。

2023/5/20

PID 算法到底在干什么？工程师最常用的控制方法

By Long Luo PID 算法是自动控制领域中很重要的算法。 \[ u(t) = K_Pe(t) + K_I \int e(t) \mathrm{d}t + K_D \frac{\mathrm{d}e(t)}{\mathrm{d}t} \] <h2 id="simple-pid-controller">Simple PID Controller</h2> 非常简单的 PID 算法在线互动式模拟器，<a href="https://www.longluo.me/projects/pid/">传送门 →</a> ： <a href="https://www.longluo.me/projects/pid/"><img src="https://user-images.githubusercontent.com/3395062/238180467-c7852d59-b9e3-4fe5-89b4-d8ddd4d44592.png" alt="PID Algorithm"></a> 之前这个是 PID v1.0 版本，最近重构了代码，增加了一些新功能： <ol type="1"> <li>增加机器人速度 $v$ 及加速度 $a$ 显示；</li> <li>增加 2 个图表展示 PID X 轴方向及 Y 轴方向的 P、I、D $3$ 个分量随时间变化显示；</li> <li>之前代码将时间及速度固定了，但这不符合实际，增加随 $dt$ 变化积分和微分项；</li> </ol> <a href="https://www.longluo.me/projects/pid/"><img src="https://user-images.githubusercontent.com/3395062/246782983-695c0d08-1998-4d96-b13b-a0a5827f19fc.png" alt="pid_track"></a>

2023/5/5

解密卡尔曼滤波(Kalman Filter)算法：深入解析卡尔曼滤波算法原理与在线可视化实例

By Long Luo Kalman Filter<a href="#fn1" class="footnote-ref" id="fnref1" role="doc-noteref">1</a> 是贝叶斯滤波器的一种特殊实现。 <h1 id="kalman-filter-1d-一维卡尔曼滤波器">Kalman Filter 1D | 一维卡尔曼滤波器</h1> 一维卡尔曼滤波器如下图所示： <figure> <img src="https://user-images.githubusercontent.com/3395062/239743987-c86b622d-7c17-429c-8221-def992aacf55.PNG" alt="Kalman Filter 1D"> <figcaption aria-hidden="true">Kalman Filter 1D</figcaption> </figure> 在线动画展示：http://www.longluo.me/projects/kalman/

2023/4/29

从记忆到洞察：轻松掌握泰勒展开式(Taylor Series)的记忆技巧

By Long Luo 在数学、物理学、工程和计算机领域中，泰勒级数( $\textit{Taylor Series}$ )<a href="#fn1" class="footnote-ref" id="fnref1" role="doc-noteref">1</a> 是一种广泛使用的分析方法，用来计算函数的近似值。在实践中，很多函数非常复杂，而且某些函数是不可积的，想求其某点的值，直接求无法实现。 泰勒公式可以将复杂的函数近似地表达为简单的多项式函数，用一个多项式函数去逼近一个给定的函数(即尽量使多项式函数图像拟合给定的函数图像)。注意在逼近的时候一定是从函数图像上的某个点展开。 下图所示就是不同项数的泰勒公式对 $\sin x$ 的逼近： <figure> <img src="https://www.longluo.me/assets/blog/images/taylor/taylor-sine.svg" alt="图1. 泰勒公式对 \sin x 的逼近"> <figcaption aria-hidden="true">图1. 泰勒公式对 $\sin x$ 的逼近</figcaption> </figure> 泰勒级数的定义为： \[ f(x) = \sum _{n=0}^{\infty}{\frac{f^{(n)}(a)}{n!}}(x-a)^{n} = f(a) + {\frac {f'(a)}{1!}}(x - a) + {\frac {f''(a)}{2!}}(x - a)^{2} + {\frac {f'''(a)}{3!}}(x - a)^{3} + \cdots \] 这里， $n!$ 表示 $n$ 的阶乘，而 $f^{(n)}(a)$ 表示函数 $f$ 在点 $a$ 处的 $n$ 阶导数。如果 $a = 0$ ，这个级数也被称为麦克劳林级数( $\textit{Maclaurin series}$ )<a href="#fn2" class="footnote-ref" id="fnref2" role="doc-noteref">2</a> 。 泰勒展开式有很多，那么如何记忆呢？首先我们需要明白，泰勒公式之间都是有相互关联的，我们可以通过推导来理解性记忆这些公式。泰勒公式的具体推导过程可以参考数学分析教材或者网络<a href="#fn3" class="footnote-ref" id="fnref3" role="doc-noteref">3</a> 。 下面我们就推导这些公式，以便更好的记忆<a href="#fn4" class="footnote-ref" id="fnref4" role="doc-noteref">4</a> ！ <h2 id="几何级数-geometric-series">几何级数 Geometric series</h2> 对于 $-1 < x < 1$ 的情况，几何级数( $\textit{Geometric series}$ )<a href="#fn5" class="footnote-ref" id="fnref5" role="doc-noteref">5</a> 由等比数列求和公式可得： \[ \frac{1}{1 - x} = \sum _{n=0}^{\infty}x^{n} = 1 + x + x^{2} + \cdots + x^{n} \] 用 $-x$ 代入 $x$ 上式，则： \[ \frac{1}{1 + x} = \sum _{n=0}^{\infty}(-1)^nx^{n} = 1 - x + x^{2} - x^3 + \cdots + (-1)^n x^{n} \] 用 $x^2$ 替代 $x$ , 由于 $\arctan x = \int_{0}^{x} \dfrac{1}{1 + x^2} \mathrm{d}x$ ，对于 $-1 \le x \le 1, x \neq \pm i$ ， \[ \arctan x = \sum _{n=0}^{\infty }{\frac {(-1)^{n}}{2n + 1}}x^{2n + 1} = x - {\frac {x^3}{3}} + {\frac {x^5}{5}} - \cdots + \frac{(-1)^n}{2n + 1}x^{2n + 1} \] 因为 $\dfrac {1}{(1 - x)^2} = (\dfrac {1}{1 - x})'$ ，则： \[ \begin{aligned} \frac {1}{(1 - x)^2} & = \sum _{n=1}^{\infty }n x^{n-1} \\ & = 1 + 2x + 3x^2 + \cdots + n x^{n-1} \end{aligned} \] 同 $\dfrac {1}{(1 - x)^3} = \dfrac {1}{2} (\dfrac {1}{(1 - x)^2})'$ ，则有： \[ \frac {1}{(1 - x)^3} = \sum _{n=2}^{\infty }{\frac {n(n - 1)}{2}}x^{n - 2} \] <h2 id="指数函数-exponent-function">指数函数 Exponent function</h2> 由于 $\dfrac {\mathrm{d} e^x}{\mathrm{d} x} = e^x$ ，$e^0 = 1$ 那么： \[ e^x = \sum _{n=0}^{\infty }{\frac {x^n}{n!}} = 1 + x + {\frac {x^2}{2!}} + {\frac {x^3}{3!}} + \cdots + {\frac {x^n}{n!}} \] 很明显： \[ \begin{aligned} (e^x)' & = (\frac {1}{0!} + \frac {x}{1!} + \frac {x^2}{2!} + \frac {x^3}{3!} + \cdots)' \\ e^x & = 0 + 1 + \frac {x}{1} + \frac {x^2}{2!} + \frac {x^3}{3!} \cdots \\ & = 1 + x + \frac {x^2}{2!} + \frac {x^3}{3!} + \cdots \end{aligned} \] 对于普通指数函数 $a^x$ , 由于 $a^x=e^{x \ln a}$ ，如果将 $x$ 换为 $x \ln a$ ，那么 $a^x$ 的泰勒展开式： \[ \begin{aligned} a^x & = e^{x \ln a} \\ & = 1 + x \ln a + \frac {(x \ln a)^2}{2!} + \frac {(x \ln a)^3}{3!} + \cdots + \frac {(x \ln a)^n}{n!} \\ \end{aligned} \]

2023/4/26

哪个更大呢？ $2^{100!}$ 还是 $2^{100}!$ ？

By Long Luo 昨天在B站看到一个数学视频<a href="#fn1" class="footnote-ref" id="fnref1" role="doc-noteref">1</a> ，比较 $2^{100!}$ 和 $2^{100}!$ 的大小。直观感受就是这 $2$ 个数都非常非常大，但哪个更大无法一眼看出来。 虽然指数爆炸，但阶乘实际上增长的速度比指数更快，如下图 1 所示： <figure> <img src="https://www.longluo.me/assets/blog/images/function/function-growth-rate-graph.png" alt="图1. 函数增长示意图"> <figcaption aria-hidden="true">图1. 函数增长示意图</figcaption> </figure> 可以看出阶乘图像 $y = x!$ 实际上比指数 $y = e^x$ 要快很多，而 $y = x^x$ 是最快的。 但具体哪个更大呢？ 这个问题有很多种方法，这里展示了 $4$ 种方法。 <h2 id="对数放缩法">对数放缩法</h2> 由于对数( $\textit{Logarithm}$ ) <a href="#fn2" class="footnote-ref" id="fnref2" role="doc-noteref">2</a> 函数 $y = \log_{a}{b}$ 当 $a > 1$ 是单调递增函数，所以比较两个数大小时，可以通过比较两者对数值来实现大小比较。 两边同取对数 $\log_{2}{x}$ ， 左边： \[ A = \log_{2}{(2^{100!})} = 100! \] 右边： \[ B = \log_{2}{2^{100}!} = \log_{2}{2^{100}} + \log_{2}{(2^{100} - 1)} + \dots + 1 + 0 \] 共有 $2^{100}$ 项，值从 $0$ 到 $\log_{2}{2^{100}} = 100$ ，所以 \[ B < 100 \cdot 2^{100} < 128 \cdot 2^{100} = 2^7 \cdot 2^{100} = 2^{107} \] 综合上式，我们只需要比较 $100!$ 和 $2^{107}$ 的大小即可。 $100!$ 至少有 $(100 - 64 + 1) = 37$ 项是大于等于 $64 = 2^6$ ，也就是 $(2^6)^{37} = 2^{222}$ 。 显然可得 $100! \gg 2^{222} \gg 2^{107}$ 。 故有虽然两个数都非常大，但 $2^{100!}$ 仍然远远大于 $2^{100}!$ 。

2023/4/16

Google经典编程竞赛题：计算 $(3 + \sqrt{5})^n$ 的小数点前三位数

By Long Luo 安全界大牛 <a href="https://baike.baidu.com/item/%E8%A2%81%E4%BB%81%E5%B9%BF/7203293">袁哥</a> 在微博上发布了一道 <a href="https://weibo.com/6236276241/Myr7nFS6N">数学挑战题</a> ： <div class="note primary">计算 $(3+ \sqrt{5})^n$ 的整数末三位数，给出能口算或者可以用计算器计算的算法的第一个人，免费给一个价值 1000 元的 A9 投资分享群入群名额。 </div> <h2 id="我的解答">我的解答</h2> 刷微博时看到这道题目时，我觉得很简单啊，于是马上给出了下面的解答： 令 $y = (3 + \sqrt{5})^n$ ，两边同取对数， $\log_{10}{y} = n \log_{10}{(3 + \sqrt{5})}$ ， $y = 10^{n \log_{10}{5.23607}}$ ，$\log_{10}{5} \approx 0.7$ ，所以 $y \approx 10^{0.7n}$ 。 但问题没有这么简单，因为上述解答只在 $n = 1$ 是正确的，$n = 2$ ， $y = 10^{1.4} \approx 25$ 就不对了，因为精度不够！ 之后根据微博评论中其他人给的构造共轭数思路，分析出 $3$ 位数是周期性的，于是又提交了下面的答案： <figure> <img src="https://www.longluo.me/assets/blog/images/google-code-jam/2008/numbers/google-code-jam-2008-numbers-my-rough-solution.jpeg" alt="图1. 证明周期性"> <figcaption aria-hidden="true">图1. 证明周期性</figcaption> </figure> 但问题仍然没有这么简单，因为即使循环周期 $p = 100$ ，而 <a href="https://www.longluo.me/blog/floating-point/">双精度浮点数</a> 的有效位数也只有 $15$ 位，而 $\sqrt{5}$ 是无理数，同时由于舍入误差， $\log_{10}{(3 + \sqrt{5})}$ 很快就出现精度不够的问题，得到错误的结果。 之后袁哥发布了 <a href="https://weibo.com/6236276241/MyCgz8tEk">解答</a> ，图片太大，大家可以点开 <a href="https://www.longluo.me/assets/blog/images/google-code-jam/2008/numbers/google-code-jam-2008-numbers-yuange-solution.jpg">图片链接</a> 查看详细解答。 袁哥的题解省略了很多东西，对数学不熟悉的人可能看不太明白，我当时也没有完全看明白。根据袁哥解答我重新写了份题解，整理了思路及缺失的步骤，外加证明，有中学数学水平即可看懂，题解第一部分如下：

2023/3/23

手写数字识别：解码机器学习的背后的数学原理

By Long Luo 从古到今，人类一直希望机器能够像人一样，代替人们从事各种工作。 机器学习（Machine Learning）是一门引人入胜的领域，通过模拟人脑神经网络，使计算机能够从数据中学习和改进，以完成各种任务。 深度学习(Deep Learning) 神经网络(Neutral Network) <a href="https://space.bilibili.com/88461692">3Blue1Brown</a> 的 <a href="https://www.bilibili.com/video/BV1bx411M7Zx/">深度学习之神经网络的结构 Part 1</a> 。 在当今数字化的时代，机器学习和神经网络成为了引领人工智能发展的核心技术。其中，手写数字识别作为机器学习领域的一个经典问题，为我们深入探索神经网络的原理提供了绝佳的案例。 这篇文章将首先介绍什么是神经网络，神经网络的实现原理，之后以经典的手写数字识别为例来加强对机器学习的理解。 <h2 id="什么是神经网络">什么是神经网络？</h2> 神经系统的工作方式与身体的其他器官完全不同。在身体的许多器官中，同类型的细胞执行同样的功能，单个细胞的工作就代表整个器官的功能，器官的功能也就是其中每个细胞功能的总和。例如肝脏中的每个肝细胞都执行同样的化学合成和解毒功能，小肠上皮细胞都执行同样的吸收营养的功能，每条肌肉中的肌肉细胞都执行同样的收缩功能等。它们的功能状态受整体器官的控制，细胞之间的信息交换比较少。 与此相反，神经系统以网络的方式进行工作，神经细胞之间有频繁和复杂的信息传递，每个神经细胞的状态都根据其在网络中的位置不同而与其它神经细胞不同，单个神经细胞功能也不能代表整个神经系统的功能。 人脑神经网络是由大量的神经元组成，通过突触连接形成复杂的网络。机器学习通过人脑神经网络的启发，构建人工神经网络模型。人工神经网络由节点（神经元）和连接它们的权重组成。权重表示神经元之间的连接强度，信息通过这些连接在网络中传递和处理。 <h2 id="神经网络是如何工作的">神经网络是如何工作的？</h2> 首先，让我们了解一下神经网络的基本结构。神经网络由输入层、隐藏层和输出层组成。输入层接收手写数字的像素值作为输入，隐藏层则负责提取输入特征，输出层给出最终的识别结果。每个神经元都与上一层的所有神经元连接，并带有权重，这些权重决定了每个神经元对信息的贡献程度。 为了训练神经网络，我们需要大量的手写数字样本作为训练数据。训练过程中，神经网络会根据输入数据的真实标签与预测标签之间的误差，通过反向传播算法来更新神经元之间的权重，从而逐渐提高准确性。反向传播算法通过计算每个神经元的梯度，根据梯度的大小来调整权重，使得预测结果与真实标签更加接近。 对于手写数字识别问题，隐藏层的神经元可以学习到不同笔画、曲线等特征，输出层的神经元则对应0到9的数字标签。通过大量的样本和迭代训练，神经网络可以逐渐学习到正确的特征提取和数字分类规则，从而实现准确的手写数字识别。 除了神经网络的结构和训练方法外，还有一些优化技术可以提高手写数字识别的性能。例如，卷积神经网络（Convolutional Neural Networks，CNN）能够有效地利用图像的空间结构特征，提高了识别的准确性和效率。另外，激活函数的选择、正则化技术的应用以及适当的优化算法等都对神经网络的性能起到重要作用。 神经网络是一种受到人脑神经元启发的算法模型，通过多个层次的神经元组成，可以进行复杂的数据处理和模式识别。在手写数字识别中，我们希望机器能够通过训练学习，准确地识别手写的数字。接下来，我们将揭开神经网络的奥秘。 \[ S(x) = {\frac {1}{1 + e^{-x}}} = {\frac {e^{x}}{e^{x} + 1}} = 1 - S(-x) \]

2023/3/3

The Answers of MRI Tutorial Videos

By Frank Luo This is my answers of the MRI Tutorial Videos <a href="https://youtu.be/M7yh0To6Wbs">How MRI Works - Part 2: The Spin Echo</a> and <a href="https://youtu.be/R_4GuyJTzMo">How MRI Works - Part 3：Fourier Transform and K-Space</a> . <h2 id="part-2-the-spin-echo">Part 2: The Spin Echo</h2> <h3 id="questions">Questions</h3> <figure> <img src="https://www.longluo.me/assets/blog/images/mri/mri-part2-question-1.png" alt="Part 2 Questions 1"> <figcaption aria-hidden="true">Part 2 Questions 1</figcaption> </figure> <figure> <img src="https://www.longluo.me/assets/blog/images/mri/mri-part2-question-2.png" title="Part 2 Question 2" alt="Part 2 Question 2"> <figcaption aria-hidden="true">Part 2 Question 2</figcaption> </figure> <h3 id="answers">Answers</h3> <h4 id="question-1">Question 1：</h4> <ol type="1"> <li>The Boltzmann Magetization $M_0 = \frac{N {\gamma}^2 \hbar^2 B_0}{4 k T}$, then after elimination the units is $J/T$. </li> <li>The Polarization is $P = \frac{\gamma \hbar B_0}{2kT}$, then after elimination we can get that $P$ is a special number depends on the material, no SI units.</li> </ol> <h4 id="question-2">Question 2：</h4> <ol type="1"> <li>The polarization is $P = \frac{51-49}{100} = 0.02$ .</li> <li>The magnet field strength should be $B_0 = \frac{0.02}{0.0000034} \approx 5882T$ .</li> <li>The temperature should be $T = \frac{300 \times 0.0000034}{0.02} = 0.051K$.</li> </ol> <h4 id="question-3">Question 3：</h4> <ol type="1"> <li>Since the Boltzmann Magetization Equation is $M = M_0(1- e^{-\frac{t}{T_1}}) e^{-\frac{t}{T_2}}$ , so we can calculate the signal.</li> </ol> The signal of Tissue $A$ : $M_A = M_0(1- e^{-\frac{150}{300}}) e^{-\frac{12.5}{20}} = 0.21$ . The signal of Tissue $B$ : $M_B = M_0(1- e^{-\frac{150}{200}}) e^{-\frac{12.5}{40}} = 0.38$ . Surely Tissue $B$ will deliver more signal. <ol start="2" type="1"> <li>We have calculated that Tissue $B$ will deliver more signal if both Tissue $A$ and $B$ has the same Boltzmann Magetization.</li> </ol> If Tissue $A$ is $85\%$ of Tissue $B$, then the Tissue $A$ signal will become lesser, so Tissue $B$ deliver more signal. <ol start="3" type="1"> <li>Let function $f(t) = M_{0A}(1- e^{-\frac{TR}{T_{1A}}})e^{-\frac{t}{T_{2A}}} - M_{0B}(1- e^{-\frac{TR}{T_{1B}}})e^{-\frac{t}{T_{2B}}}$ reprent the signal of time $t$.</li> </ol> Consider the function: $f(t) = (1 - e^{-\frac{150}{200}}) e^{-\frac{t}{40}} - (1- e^{-\frac{150}{300}}) e^{-\frac{t}{20}}$ reaches its PEAK at about $t = 16$, so the $TE$ should be $TE = 32ms$.

2023/2/11

gdb 操作指南

By Long Luo <h2 id="startup">Startup</h2> <figure class="highlight plaintext"><table><tbody><tr><td class="gutter"><pre>1 2 3 4 5 </pre></td><td class="code"><pre>% gdb -help print startup help, show switches *% gdb object normal debug *% gdb object core core debug (must specify core file) %% gdb object pid attach to running process % gdb use file command to load object </pre></td></tr></tbody></table></figure> <h2 id="help">Help</h2> <figure class="highlight plaintext"><table><tbody><tr><td class="gutter"><pre>1 2 3 4 5 6 7 </pre></td><td class="code"><pre>*(gdb) help list command classes (gdb) help running list commands in one command class (gdb) help run bottom-level help for a command "run" (gdb) help info list info commands (running program state) (gdb) help info line help for a particular info command (gdb) help show list show commands (gdb state) (gdb) help show commands specific help for a show comma </pre></td></tr></tbody></table></figure> <h2 id="breakpoints">Breakpoints</h2> <figure class="highlight plaintext"><table><tbody><tr><td class="gutter"><pre>1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 </pre></td><td class="code"><pre>*(gdb) break main set a breakpoint on a function *(gdb) break 101 set a breakpoint on a line number *(gdb) break basic.c:101 set breakpoint at file and line (or function) *(gdb) info breakpoints show breakpoints *(gdb) delete 1 delete a breakpoint by number (gdb) delete delete all breakpoints (prompted) (gdb) clear delete breakpoints at current line (gdb) clear function delete breakpoints at function (gdb) clear line delete breakpoints at line (gdb) disable 2 turn a breakpoint off, but don't remove it (gdb) enable 2 turn disabled breakpoint back on (gdb) tbreak function|line set a temporary breakpoint (gdb) commands break-no ... end set gdb commands with breakpoint (gdb) ignore break-no count ignore bpt N-1 times before activation (gdb) condition break-no expression break only if condition is true (gdb) condition 2 i == 20 example: break on breakpoint 2 if i equals 20 (gdb) watch expression set software watchpoint on variable (gdb) info watchpoints show current watchpoints </pre></td></tr></tbody></table></figure>

2023/1/5

Linux 网络命令指南

By Long Luo <h2 id="网络抓包常用命令">网络抓包常用命令</h2> 详细解析和Demo版本：<a

2022/12/16

贝塞尔曲线(Bezier Curve)：优雅背后的数学原理

By Long Luo 最近在 YouTube 上看了 <a href="https://www.youtube.com/@Acegikmo/videos">Freya Holmér</a> 的 <a

2022/12/8

LeetCode 380. Insert Delete GetRandom O(1) Data Structures: Thought Process from HashMap to HashMap + Array

By Long Luo This article is the solution <a href="https://leetcode.com/problems/insert-delete-getrandom-o1/solutions/2858411/data-structures-thought-process-from-hashmap-to-hashmap-array/">Data Structures: Thought Process from HashMap to HashMap + Array</a> of Problem <a href="https://leetcode.com/problems/insert-delete-getrandom-o1/">380. Insert Delete GetRandom O(1)</a> . <h2 id="intuition">Intuition</h2> It’s easy to think of using a Hash Table to achieve $O(1)$ time complexity for $\texttt{insert}$ and $\texttt{remove}$ operations. However, we need $O(1)$ time complexity to complete the $\texttt{getRandom}$ operation. The Array structure can complete the operation of obtaining random elements in $O(1)$ time complexity, but it can’t completed the $\texttt{insert}$ and $\texttt{remove}$ operations in $O(1)$ time complexity. So How? Aha!!!

2022/11/29

LeetCode 2475. 数组中不等三元组的数目 2种 O(n) 时间复杂度算法

By Long Luo 今天 <a href="https://leetcode.cn/contest/weekly-contest-320/">LeetCode 第320场周赛</a> 中第一题是 <a href="https://leetcode.cn/problems/number-of-unequal-triplets-in-array/">2475. 数组中不等三元组的数目</a> ，本文是该题的题解，同时发表在 <a href="https://leetcode.cn/problems/number-of-unequal-triplets-in-array/solution/by-longluo-kg4a/">这里</a> 。 参考了 <a href="https://leetcode.cn/u/endlesscheng/">@灵茶山艾府</a> 的题解 <a href="https://leetcode.cn/problems/number-of-unequal-triplets-in-array/solution/fei-bao-li-zuo-fa-by-endlesscheng-9ekp/">非暴力做法</a> ，实际上我们可以不用先排序，而是先用 $\texttt{HashMap}$ 统计数组 $\textit{num}$ 元素频率。 之后遍历 $\texttt{HashMap}$ ，结果为： \[ \sum_{j = 0}^{n} (map[0] + \cdots + map[i]) \times map[j] \times (map[k] + \cdots + map[n - 1]) \] ，其中 $n$ 为 $\textit{nums}$ 的长度。 证明如下： 对于数组中的元素 $x$ ，可以得到： <ul> <li>小于 $x$ 的数有 $a$ 个；</li> <li>等于 $x$ 的数有 $b$ 个；</li> <li>大于 $x$ 的数有 $c$ 个。</li> </ul> 那么 $x$ 对最终答案的贡献是 $abc$ 。 即使 $x$ 是三元组中的最大或最小值，由于 $i, j, k$ 的对称性，很明显其实和 $x$ 是中间值都是同一个答案。 证毕！

2022/11/20

LeetCode 947. Most Stones Removed with Same Row or Column It is Literally a Graph: DFS and Union Find

By Long Luo This article is the solution <a href="https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/solutions/2812465/it-s-literally-a-graph-dfs-and-union-find/">It is Literally a Graph: DFS and Union Find</a> of Problem <a href="https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/">947. Most Stones Removed with Same Row or Column</a> . <h2 id="intuition">Intuition</h2> We can find that this is a graph theory problem with analysis. Imagine the stone on the 2D coordinate plane as the vertex of the graph, If the x-coord or the y-coord of two stones are the same, there is an edge between them. This can be show as follows: <figure> <img src="https://www.longluo.me/assets/blog/images/leetcode/leetcode-947-most-stones-removed-with-same-row-or-column-1.png" alt="947. Most Stones Removed with Same Row or Column 1"> <figcaption aria-hidden="true">947. Most Stones Removed with Same Row or Column 1</figcaption> </figure> According to the rule that stones can be removed, we should remove those points that are in the same row or column with other points as late as possible. That is, the more points in the same row or column with point A, the later point A should be removed. In this way, we can delete as many points as possible through point A. It can be found that all vertices in a connected graph can be deleted to only one vertex. <figure> <img src="https://www.longluo.me/assets/blog/images/leetcode/leetcode-947-most-stones-removed-with-same-row-or-column-2.png" alt="947. Most Stones Removed with Same Row or Column 2"> <figcaption aria-hidden="true">947. Most Stones Removed with Same Row or Column 2</figcaption> </figure> Since these vertices are in a connected graph, all vertices of the connected graph can be traversed by DFS or BFS. Therefore: the maximum number of stones that can be removed = the number of all stones - the number of connected components.

2022/11/14

LeetCode 295. Find Median from Data Stream Two Heaps with the Follow Ups

By Long Luo This article is the solution <a href="https://leetcode.com/problems/find-median-from-data-stream/solutions/2805119/two-heaps-with-the-follow-up-s-solution/">Two Heaps with the Follow Up’s Solution</a> of Problem <a href="https://leetcode.com/problems/find-median-from-data-stream/">295. Find Median from Data Stream</a> . <h2 id="intuition">Intuition</h2> We can simply use a $\texttt{ArrayList}$ to record the number and sort the list, then we can easily get the median element of the list. However, the Time Complexity will be $O(n^2 \log n)$ and the Space Complexity is $O(n)$ . It surely will be TLE and we have to find a better solution. <h2 id="heap">Heap</h2> We can use Two Priority Queues (Heaps) to maintain the data of the entire data stream. The min Heap denoted as $\textit{queueMin}$ is used to maintain the number $\textit{num} \leq \textit{median}$. The max Heap denoted as $\textit{queueMax}$ is used to maintain the number $\textit{num} \gt \textit{median}$ . <ul> <li>When the total number of data stream elements is Even: $\texttt{queueMax.size()} = \texttt{queueMin.size()}$ , the dynamic median is $\dfrac {\texttt{queueMax.peek()} + \texttt{queueMin.peek()}}{2}$ ;</li> <li>When the total number of data stream elements is Odd: $\texttt{queueMin.size()} = \texttt{queueMin.size()} + 1$ , the dynamic median is $\texttt{queueMin.peek()}$ .</li> </ul>

2022/11/12

LeetCode 1668. 最大重复子字符串不用API，比KMP更易理解简洁优雅的暴力解法

By Long Luo 今天 <a href="https://leetcode.cn/">LeetCode CN</a> 的每日一题是 <a

2022/11/3

LeetCode 334. Increasing Triplet Subsequence Why Greedy Works?

By Long Luo This article is the solution <a href="https://leetcode.com/problems/increasing-triplet-subsequence/discuss/2688263/Why-Greedy-works">Why Greedy Works?</a> of Problem <a href="https://leetcode.com/problems/increasing-triplet-subsequence/">334. Increasing Triplet Subsequence</a>. <h2 id="intution">Intution</h2> We can easily find that whether there exists a triple of indices $(i, j, k)$ such that $i < j < k$ and $nums[i] < \textit{nums}[j] < \textit{nums}[k]$ only traversing the array once, but the problem is how to make our mind into algorithms. <h2 id="brute-force">Brute Force</h2> It’s easy to use Brute Force way to solve this problem, but the time complexity is $O(n^3)$, it will TLE, so we need to find a better way. <figure class="highlight java"><table><tbody><tr><td class="gutter"><pre>1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 </pre></td><td class="code"><pre>public static boolean increasingTriplet(int[] nums) { if (nums == null || nums.length < 3) { return false; } int len = nums.length; for (int i = 0; i < len; i++) { for (int j = i + 1; j < len; j++) { for (int k = j + 1; k < len; k++) { if (nums[i] < nums[j] && nums[j] < nums[k]) { return true; } } } } return false; } </pre></td></tr></tbody></table></figure> <h3 id="analysis">Analysis</h3> <ul> <li>Time Complexity: $O(n^3)$</li> <li>Space Complexity: $O(1)$</li> </ul> <h2 id="dynamic-programming">Dynamic Programming</h2> We can also use DP method to solve it. Let $dp[i]$ represents the maximum length of a increasing sequence. \[ dp[i] = \begin{cases} 1 & dp[i] \le dp[j], 0 < j dp[j], 0 < j

2022/10/11

Long Luo's Life Notes

夏至日测地球：利用太阳影子计算地球半径

太阳温度是怎么计算出来的？

《大象的时间，老鼠的时间》读书笔记：生命节奏背后的数学规律

小港流到哪里去？

如何用一根棍子测出地球有多大？复刻埃拉托色尼的春分实验

2007江苏高考数学第20题解析：一道通向黄金分割数的数列压轴题

Google经典面试题: 鸡蛋应该怎么扔？

2010年江苏高考数学压轴题解析：巧用余弦定理与数学归纳法

2011年清华大学自主招生数学题解析：一道经典数列题的解法与思路

2006年江西高考理科数学压轴题解析：递推、放缩与不等式结构

一道初中数学极值题的多种解法：柯西不等式、几何法、函数法详解

扔几个骰子，怎么算出期望？——拼多多校招笔试算法题的数学故事

拼多多校招笔试算法题：一行公式搞定“多多的魔术盒子”

斯特林公式(Stirling's Formula)：我一个阶乘表达式，怎么就和圆扯上关系了呢？

我爱做题：2010年江西高考理科数学压轴题

热机的效率上限在哪里？解析卡诺循环（Carnot Cycle）

为什么 2024 年会有 366 天？

数学之美：几何视角下的高斯积分(Gaussian Integral)

从最小二乘法到正态分布：高斯是如何找到失踪的谷神星的？

正态分布(Normal Distribution)公式为什么长这样？

高速公路编号背后的数学密码

2024阿里巴巴全球数学竞赛预选赛试题及解答

库函数 (libm) 是如何计算三角函数值的？

payne hanek 归约算法

音乐背后的数学

素描背后的物理

cody waite

浮点数

Remez Algorithm

参数归约算法(Argument Range Reduction)：如何在浮点数环境下计算超大数字的三角函数值？

素描背后的数学

发生在计算机内存里的进化：解密遗传算法(Genetic Algorithm)

CORDIC算法：一种高效计算三角函数值的方法

墨卡托的魔术：地图是如何欺骗你的眼睛的？

PID 算法到底在干什么？工程师最常用的控制方法

解密卡尔曼滤波(Kalman Filter)算法：深入解析卡尔曼滤波算法原理与在线可视化实例

从记忆到洞察：轻松掌握泰勒展开式(Taylor Series)的记忆技巧

哪个更大呢？ $2^{100!}$ 还是 $2^{100}!$ ？

Google经典编程竞赛题：计算 $(3 + \sqrt{5})^n$ 的小数点前三位数

手写数字识别：解码机器学习的背后的数学原理

The Answers of MRI Tutorial Videos

gdb 操作指南

Linux 网络命令指南

贝塞尔曲线(Bezier Curve)：优雅背后的数学原理

LeetCode 380. Insert Delete GetRandom O(1) Data Structures: Thought Process from HashMap to HashMap + Array

LeetCode 2475. 数组中不等三元组的数目 2种 O(n) 时间复杂度算法

LeetCode 947. Most Stones Removed with Same Row or Column It is Literally a Graph: DFS and Union Find

LeetCode 295. Find Median from Data Stream Two Heaps with the Follow Ups

LeetCode 1668. 最大重复子字符串 不用API，比KMP更易理解简洁优雅的暴力解法

LeetCode 334. Increasing Triplet Subsequence Why Greedy Works?

LeetCode 1668. 最大重复子字符串不用API，比KMP更易理解简洁优雅的暴力解法