米米的博客

去年 9 月，MathJax 发布了 3.0 版本，相较于 2.0 版本进行了完全的重写。3.0 版本带来了许多闪亮的特性，其最为显著的改进便是渲染速度提升。此前 KaTeX 宣传比 MathJax2 速度快很多，但 MathJax3 发布后，两者已经不分伯仲。除此之外，MathJax 增加了对 Node.js 端的数学公式渲染的支持。此前这一功能需要通过 mathjax-node 进行繁琐的配置才能实现，而现在官方提供了大量的 Demo，只需要数行代码便可以达到与前端完全一致的渲染效果。在 Hexo 这样基于 Node.js 的博客系统中，同样可以方便地实现后端的数学公式渲染。借助于 MathJax，可以在 Hexo 生成过程中就将所有文章中的数学公式渲染为 svg 格式的图片。这样做的优点是不需要加载任何前端脚本，就可以显示数学公式，显著提高页面加载速度。

欢迎使用笔者开发的插件：hexo-filter-mathjax

在旧款的 Mac 上，每次开机启动时，会播放「噔～」的一声启动音效，伴随着苹果的 LOGO 显示在屏幕上。随着 Mac 的不断更新，这一行为也发生了变化。例如，在 OS X 10.10 (Yosemite) 版本中，苹果的 LOGO 下方加了一个进度条，看上去开机时间变慢了许多；而在较新版本的 Mac 中，启动音效消失了 —— 苹果默认禁用了这一特性。还好只是禁用，而不是完全移除，通过执行以下命令，又可以找回经典的 Mac 启动音效：

1

sudo nvram StartupMute=%00

去年的圆周率日，笔者解析了一段神奇的求圆周率代码，可以求出任意精度的。今年正发愁不知道写些什么，偶然间看到一道来自北大数院公众号的题目，索性分享过来：

使用 1 至 20 间至多四个整数（可以相同），利用加、减、乘、除、乘方、对数和阶乘，构造出一个算式，使其计算出一个尽可能接近的数。规定：

• 每个整数在算式中只能用一次；
• 运算必须在有限步之内完成；
• 提供的整数不能拼凑，例如不能由 1 和 10 拼出 110；
• 并且，乘方、对数都是二元运算，不提供自然对数底等常数，也不提供其它函数；
• 阶乘是唯一允许的一元运算。

小朋友，你是否有很多问号？快拿起笔和纸你最喜欢的编程语言试试吧！

本文同时作为北京大学《数据结构与算法》课程论文提交。转载请注明出处。

算法（Algorithm）一词来源于公元九世纪的波斯数学家、天文学家及地理学家花拉子米（Muhammad ibn Musa al-Khwarizmi）（「Algorithm」一词本身兴起于 1950 年左右。虽然对其起源的考证有很多不同的观点，但一种较为可靠的说法是「Algorism」，由此可以追溯到花拉子米。比较有趣的是，「代数」（Algebra）一词亦与花拉子米有关 —— 这来源于他的一本与代数没有什么联系的著作）。而世界上最早的算法，出现的甚至比这更早 —— 欧几里得的辗转相除法，诞生于公元三世纪。今日我们所说的算法，可以参见高德纳（Donald Ervin Knuth）在他的著作《计算机程序设计艺术（The Art of Computer Programming）》里的描述（可参阅《计算机程序设计艺术（中文版）第一卷第三版：基本算法》的第 3 至 4 页）：

• 输入：一个算法必须有零个或以上输入量。
• 输出：一个算法应有一个或以上输出量，输出量是算法计算的结果。
• 明确性：算法的描述必须无歧义，以保证算法的实际执行结果是精确地匹配要求或期望，通常要求实际运行结果是确定的。
• 有限性：依据图灵的定义，一个算法是能够被任何图灵完全系统模拟的一串运算，而图灵机只有有限个状态、有限个输入符号和有限个转移函数（指令）。而一些定义更规定算法必须在有限个步骤内完成任务。
• 有效性：又称可行性。能够实现，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。

本文将要介绍的二十世纪十大算法，最早由 Jack Dongarra 和 Francis Sullivan 在 2000 年提出（SIAM 上的一篇报道使其广泛传播）。他们选择了「对 20 世纪科学与工程的发展和实践影响最大的 10 种算法」，分别是：

• 蒙特卡洛方法（Monte Carlo method），John von Neumann, Stan Ulam 和 Nick Metropolis 在 1946 年提出
• 线性规划的单纯形法（Simplex method for linear programming），George Dantzig 在 1947 年提出
• Krylov 子空间迭代法（Krylov subspace iteration methods），Magnus Hestenes, Eduard Stiefel 和 Cornelius Lanczos 在 1950 年提出
• Householder 形式化矩阵计算（Decompositional approach to matrix computations），Alston Householder 在 1951 年提出
• 优化的 Fortran 编译器（Fortran optimizing compiler），John Backus 在 1957 年提出
• QR 分解（QR algorithm），J.G.F. Francis 在 1959-61 年提出
• 快速排序（Quicksort），Tony Hoare 在 1962 年提出
• 快速傅里叶变换（Fast Fourier transform），James Cooley 和 John Tukey 在 1965 年提出
• 整数关系探测算法（Integer relation detection algorithm），Helaman Ferguson 和 Rodney Forcade 在 1977 年提出
• 快速多极算法（Fast multipole algorithm），Leslie Greengard 和 Vladimir Rokhlin 在 1987 年提出

下面将逐一介绍这些算法。为了明确地表达思想，这里会给出一些示例代码。