第一章 基本概念
1.1 算法
算法是贯穿在所有计算机程序设计中的一个基本概念。
让我们来看一个经典算法：
欧几里得算法
给定两个正整数 m 和 n， 求它们的最大公因子，即能够同时整除 m 和 n 的 最大正整数。
E0.[确保 m >= n] 如果 m < n，交换 m <--> n。 E1.[求余数] 以 n 除 m 并令 r 为所得余数。
E2.[余数为零？] 若 r = 0，算法结束， n 即为答案。
E3.[减少] 置 m <- n, n <- r，并返回步骤 E1。
这就是一个算法。算法的现代意义十分类似于菜谱，进程，方法，技术，过程，例程，但“算法”一词包含有那么一点不同的东西。一个算法只不过是一组有穷的规则，这些规则给出求解特定类型问题的运算序列；但除此之外，一个算法还有五个重要特征。
- 有限性。一个算法在有限步骤之后必然要终止。
- 确定性。一个算法的每个步骤都必须精确的定义；要执行的动作每一步都必须严格地和无歧义地描述清楚。
- 输入。一个算法有零个或多个输入，此即在算法开始之前最初赋给它的量。
- 输出。一个算法有一个或多个输出：和输入有特点关系的量。
- 可行性。一个算法一般可以认为是能行的，其含义是指它的所有运算必须是充分基本的。
我们应当说明，就实用而言，有限性的限制实际上是不够的。一个有用的算法不知要求步骤有限，而且要求非常有限的、合理的步骤数。
算法分析的一般思想是选取一个特定的算法，然后来确定它的定量的特性；有时我们还要研究一个算法在某种意义下是否最优。至于算法理论完全是另一个学科，它主要讨论计算特定量的有效算法的存在或不存在。
1.2 数学准备
1.2.1 数学归纳法
1.2.2 幂和对数
1.2.3 和与积
1.2.4 整数函数和初等数论
1.2.5 排列和阶乘
1.2.6 二项式系数
1.2.7 调和数
1.2.8 斐波那契数
1.2.9 生成函数
1.2.10 一个算法的分析
1.2.11 渐进表示
1.3 MIX
1.3.1 MIX 的描述
MIX 是世界上第一台多不饱和的计算机，类似于大多数的机器，它有一个标识号码——1009。
MIX 有一个独特的性质，即它同时既是二进制的，又是十进制的。 MIX 的程序员不必实际地知道他们是正在以二进制还是十进制对一台计算机进行程序设计。
字：信息的基本单位是字节。每个字节包含不确定数量的信息，但它必须能保存至少64个不同的值。即是说，我们知道，0 与 63 之间的任何数都可包含在一个字节内。其次每个字节至多含有 100 个之间的值。在一台二进制的计算机上，一个字节因而必须由 6 个二进制组成。在一台十进制的计算机上，每个字节有两位数字。
寄存器：MIX 中共有 9 个寄存器；
- A 寄存器（累加器）由五个字节和一个符号组成。
- X 寄存器（扩充）类似地，也由五个字节和一个符号组成。
- I 寄存器（变址寄存器）I1, I2, I3, I4, I5 和 I6 各拥有两个字节和一个符号。
- J 寄存器（转移地址）拥有两个字节，它的符号总为 + 。
我们将在寄存器名字前边冠以“r”来标识一个 MIX 寄存器。因此“rA”指寄存器 A。
除了寄存器外， MIX 包含
- 一个溢出开关
- 一个比较指示器 LESS EQUAL GREATER
- 内存（4000 字的存储单元，每个字有 5 个字节和 1 个符号）
指令格式： 用作指令的计算机字有下列形式：
| 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| ± | A | A | I | F | C |
最右边的字节 C ，是指出执行什么操作的操作码。例如，C=8 指明操作 LDA，即“装入 A 寄存器”。
F 字节保存对操作码的修改。它通常是一个字段说明(L:R) = 8L + R；例如，如果 C= 8 和 F = 11，则这个操作是“以(1:3)字段装入 A 寄存器”。有时 F 也用于其他目的；例如，对于输入输出指令，F 是相关的输入和输出设备编号。
1.3.2 MIX 汇编语言
1.3.3 对排列的应用
1.4 某些基本程序设计技术
1.4.1 子程序
当在一个程序中的若干个不同的地方，都要执行同一个确定的任务时，通常不希望在每个地方都重复编码。为避免这种重复的情况，这种编码可以只放在一个地方，而且在这个子程序完成之后，可以附加少量额外的指令，以便适当重新开始外部的程序。子程序与主程序之间控制的转移，称为子程序的链接。
MAX100 STJ EXIT
ENT3 100
JMP 2F
1H CMPA X, 3
JGE *+ 3
2h ENT2 0, 3
LDA X, 3
DEC3 1
J3P 1B
EXIT JMP *1.4.2 共行程序
子程序是更一般的称为共行程序的程序组成部分的特殊情况。共行程序之间有一个完美对称的关系，它们彼此调用。