米米的博客

在旧款的 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 年提出

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

Ever spent ages swapping batteries in and out of remote controls to find out which ones still have power in them?
Next time, just try dropping them on a hard surface and see if they bounce.
你是否曾经花了很长时间，把电池换来换去，只是为了确定哪个电池还有电？
下次你想知道电池有没有电，只要把它们丢在坚硬的平面上，看看它们是否弹跳起来就行了。

This is because spent alkaline batteries are more likely to bounce than fresh ones, according to an American electrical engineer whose video demonstrating the phenomenon is becoming an internet sensation.
因为用完了的碱性电池比新电池更容易弹跳起来，美国一名电气工程师拍了一段视频证明了这一现象。

To test outgassing, Mr Hite dropped a weight on the battery. If there was a build up of pressure, a weight should bounce higher on one than the other. He also drilled holes in the batteries to release this pressure. There was not a 'convincing' difference in the first test, and the bad battery still bounced in the second

In his YouTube video, Lee Hite tests a series of batteries that have expired against a set which have not been used.
He demonstrates that a used battery bounces far higher than one that has only just been taken out of the packet.
在视频中，电气工程师 Lee Hite 测试了一系列用完了的电池和刚拆开包装的新电池。
他证实，用完了的电池比新电池跳得更高。

A good battery, he explains, contains a gel-like substance which solidifies as the battery discharges its electricity.
While the gel is in a semi-liquid form, it absorbs the energy when the battery hits the surface.
他解释道：这是因为新电池里面含有凝胶状物质，随着电池不断放电，这种凝胶状物质会变硬。
这种凝胶状物质处于半液体状态时，如果电池撞击坚硬表面，它可以吸收能量。

An anti-bounce hammer, which contains an internal core of moving buckshot, works in the same way.
When the gel in the battery has solidified it cannot move and the whole battery bounces, the same way that a solid hammer bounces off a nail.
防震锤的工作原理是与之相同的 —— 其核心有着可移动的配重。当电池里面的凝胶状物质变为固体时，它就无法移动。此刻弹跳而起的电池，与锤子从钉子上弹跳开的方式一致。