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

阅读全文 »

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

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

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

阅读全文 »

序列的最大子序列和问题,说的是:给定一个包含若干整数(正负不限)的序列,寻找其中的一个子序列,使得该自序列元素之和在所有子序列的和中最大。

这一经典的问题,可由动态规划(中的 Kadane 算法)在 $O(n)$ 的时间内解决。

如果我们将给定的序列首尾相连,成为一个环状列表。同样的问题,就变得复杂起来。不过,在巧妙的思路下,问题仍然可以在 $O(n)$ 时间内解决。

下面我们先复习一下 Kadane 算法;然后看看怎样在线性时间内,解决循环列表中的最大子序列和问题。

阅读全文 »

公认的计算机之父是阿兰·图灵在 1936 年提出了「图灵机」的概念。图灵机是一个抽象的计算模型,它可以形象地表述为:

  1. 有一个向两端无限延伸的带子,可以在上面记录内容
  2. 有一个可以在带子上擦除/写入的读写头,可以在带子上任意移动
  3. 有一个控制器,控制读写头的移动和擦除/写入操作

图灵机的表述看似纸上谈兵,但实际与现在计算机的体系结构有良好的对应,甚至可以说是所有现代计算机背后的灵魂。

  1. 带子对应于内存(当然内存不能无限大,这限制了计算机的处理能力是有上限的)
  2. 读写头可以在带子上任意移动读写对应内存的随机存取(内存的英文名字就是 Random Access Memory)
  3. 控制器对应中央处理器

在内存这条带子上,找到正确的位置以便进行存取的过程,就是所谓的「内存寻址」过程。在图灵机这个思想模型中,我们可以假设读写头可以按照要求立即在带子上找到正确的位置。但是在现实生活中,有效地内存寻址是必须要解决的问题。因此,内存寻址可谓是计算机体系结构的核心问题之一。

这篇文章主要讨论 Intel x86 架构上的内存寻址问题。纯干货,吃到撑。

阅读全文 »