米米的博客

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

使用 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.
防震锤的工作原理是与之相同的 —— 其核心有着可移动的配重。当电池里面的凝胶状物质变为固体时，它就无法移动。此刻弹跳而起的电池，与锤子从钉子上弹跳开的方式一致。

前言

辉光数码管是一种利用气体辉光放电显示数字的电子元件。玻璃管中包括一个金属丝网制成的阳极和多个阴极，阴极做成数字形状，加高压后管内气体发光，即可显示出数字。下图是苏联生产的 IN-14 辉光管，为节省成本，它显示的「2」和「5」用的是同样的模具，只是颠倒过来了。

图片来自：https://en.wikipedia.org/wiki/Nixie_tube#/media/File:ИH-14_(IN-14)_Nixie_Tubes_Displaying_"25".jpg

辉光管的缺点也很明显，它的使用寿命很有限，并且需要高压才能点亮，因而逐渐被淘汰。今天辉光管仍有小规模的生产，但辉光管的意义更多的是以复古风格体现出对早期科技文化的怀旧，而不是实用价值。在许多小说、游戏和影视作品中，辉光管都作为蒸汽朋克（Steampunk）风格的代表出现。动漫《命运石之门》中的「世界线变动率探测仪」便是这样一例。这在原剧中出现了多次，有网友将其复刻了出来：

在游戏《传送门 2》中，同样出现了类似辉光管的显示装置。不过它的尺寸比较大，已经接近霓虹灯了。霓虹灯的发光原理与辉光管类似，都是依靠气体放电。非常有趣的是，辉光管往往与蒸汽朋克联系在一起，而霓虹灯则是赛博朋克的必备元素。

利用辉光数码管和单片机，即可制作出蒸汽朋克感的智能家居。主控采用 Arduino 或者 ESP32，借助于它们强大的功能，可以简洁而优雅地控制辉光管显示时间、温度等数字信息。通过进一步地开发配套的手机应用，即可通过 Wi-Fi 和蓝牙方便地展示任何自定义内容。

在前面的文章自己打造一台恩尼格玛密码机中，介绍了使用 Arduino Mega 2560 实现一个简易 Enigma 机的方法。这个型号的 Arduino 单片机拥有 50 多个数字 IO，因此可以妥善地处置按键输入，并控制大量的发光二极管（键盘灯）及数码管。
但是，其它型号的 Arduino 就不一定能完成这个任务了 —— 例如 Arduino Leonardo 只有 20 个数字 IO。那么，有没有办法拓展这些输出接口呢？答案是肯定的。借助于移位寄存器，Arduino 可以将串行信号转为并行，以此通过较少的引脚来控制多路输出。

首先我们来看看一看移位寄存器的工作原理。这里涉及到数字电路中 D 触发器的特性。D 触发器在时钟的上升沿触发，触发后其输出 Q 锁定为此时数据输入引脚 D 的状态，直到下一次触发。

在下图所示的电路中，每一个时钟脉冲后，每个 D 触发器都会把输入的数据「送」到下一级的 D 触发器中。