本篇基本上是原作的翻译。转载请保留本段文字。

复杂度通常会使用大-O 记号来表示,比如快速排序的平均时间复杂度是 $O(n \log(n))$。虽然我是「理解派」,但是虽然每个算法/数据结构都理解了,不时仍有可能忘记具体某个算法/数据结构的复杂度(特别是在最好、最坏和平均情形下的复杂度)。因此制作一个速查表是蛮有必要的。

动手前先看看是否已经有轮子是一个好习惯,果不其然,我找到了原作

阅读全文 »

不论是生活中还是工作中,总有一些文件会不断产生。这些文件可能是日志文件,也可以是系统核心转储文件。如若不加清理,查询特定文件就会非常困难,抑或是过多的核心转储文件占满了磁盘空间,影响正常程序执行。

为此,我们需要有一个简单高效的方式,定期清理过期文件。

阅读全文 »

此篇缘起匡世珉知乎回答。感谢匡世珉和他的铅笔们,也感谢我自己小时候为尺规作图付出的时间。

尺规作图(ruler-and-compass construction)是古希腊数学提出的一种平面几何作图方法。除了提出作图方法,古希腊人还留下了三个尺规作图困难问题。他们是:

  • 三等分任意给定的角;
  • 对任意给定的立方体,作一个新的立方体,使得新立方体的体积是前者的 2 倍;
  • 对任意给定的圆,作一个正方形,使得圆和正方形的面积相等。

如今,这三个困扰数学家上千年的问题,均已经被证明不可解——当然,一些青 (min) 年 (ke) 还在被困扰着。

此篇将介绍上述三等分角的问题。

阅读全文 »

和实际使用中的 Python 一样,伪代码的排版很讲究缩进。书写 Python 代码,通常会使用等宽字族(打字机字族),因此缩进一板一眼十分清晰;然而,在排版算法时,经常会遇到非等宽的字族和等宽字族混用的情况——此时,缩进有时候就不那么明确了。此时,给伪代码排版加上垂直的缩进提示线能够起到很好的提示作用。

阅读全文 »

前作以最大子序列和问题为起点,引出了动态规划思想的核心框架。今日恰逢构建之法群里,讨论起一个股票买卖问题,我用动态规划解决了。和邹欣老师的交流中,我进一步发现,引入状态机后,实际上股票买卖问题是最大子序列和问题的扩展。并且,这样的扩展可以更进一步地接近动态规划的核心,因此续作此篇,讨论一下动态规划与状态机。

阅读全文 »

有段时间没写 LaTeX 相关的文章了,此篇讲一讲 xeCJK 宏包中的 Mapping 功能。

由于中文空心句号是一个小圈,容易与作为下标的数字 0 或字母 o 混淆。因此,在专业数学书籍、论文排版中,最好是使用实心句点 来代替中文空心句号。但是,使用中文空心句号编写中文 LaTeX 手稿是大家的习惯;这样一来,使用查找替换固然是一个方案,但是繁琐且容易出错。这时候,我们就可以用到 xeCJK 宏包提供的 Mapping 选项。

Mapping 实际上是借助了 TECKit 来做字符映射。xeCJK 的作者还预先定义了能够实现简体中文和正体中文相互转换的映射表。因此,使用 xeCJK 还能实现中文的简正转换。

阅读全文 »