第六章——低级程序设计语言与伪代码

6.1 计算机操作

计算机的定义：计算机是能够储存、检索和处理数据的可编程电子设备
故而，储存、检索和处理是计算机能够对数据执行的操作。

6.2 机器语言

机器语言（machine language）:由计算机直接使用的二进制编码指令构成的语言

第一章中曾提到过，机器语言是最初人们编写指令所需的语言。后来才有其他程序设计语言的诞生，书中也提到，每条机器语言指令只能执行一个非常低级的任务。

机器语言处理过程中，每个微小的步骤都必须被明确地编码，故而有句话说得好：编程永远比看上去要难。

虚拟机：Pep/8

教材借助Pep/8虚拟机帮助理解机器语言的具体表现形式。首先其内存单元是65536字节的储存空间组成，Pep/8中字长为2字节或者16比特。

Pep/8的指令格式为两部分组成：8位的指令说明符和16位的操作说明符。
其中指令说明符（指令的第一个字节）说明了要执行什么操作和如何解释操作数的位置。
而操作数说明符（指令的第二和第三个字节）存放的则是操作数本身或者是操作数地址。有些指令没有操作数说明符。

3比特的寻址模式说明符表示了怎样解析指令中的操作数部分。

如果寻址模式是000,那么指令的操作数说明符中存储的就是操作数。这种寻址模式称为立即寻址(i) 。
如果寻址模式是001,那么操作数说明符中存储的是操作数所在的内存地址名称。这种寻址模式称为直接寻址(d) 。

立即寻址模式和直接寻址模式之间的差别十分重要，因为++它决定了操作中涉及的数据存储或将要被存储的位置。++

没有操作数（要处理的数据）的指令称为一元指令，这些指令没有操作说明符 → 一元指令的长度是1个字节而并非3字节

一些示例指令

操作码	指令含义
0000	停止执行
1100	将操作数载入寄存器A中
1110	将寄存器A的内容储存到操作数中
0111	将操作数加到寄存器A中
1000	在寄存器A的值中减去操作数的值
01001	把字符输入操作数
01010	从操作数输出字符

6.3 一个程序示例

前面提到过：机器语言处理过程中，每个微小的步骤都必须被明确地编码

而书中用最简单的机器语言程序向我们生动的解释了这句话的具体含义，其操作如下：

行为	二进制指令	十六进制指令
Write'H'	01010000 0000000001001000	50 0048
Write'e'	01010000 0000000001100101	50 0065
Write'l'	01010000 0000000001101100	50 006C
Write'l'	01010000 0000000001101100	50 006C
Write'o'	01010000 0000000001101111	50 006F
Stop	00000000	00

而在Python中只需要一条指令即可：

print('Hello')

机器语言作为最低级的程序设计语言的原因一目了然。

6.4 汇编语言

汇编语言（assembly language）：一种低级语言，用助记码表示特定计算机的机器语言部分。
汇编器（assembler）：把汇编语言程序翻译成机器代码的程序。

如下为Pep/8汇编语言：

助记忆码	操作数、寻址地址说明符	指令的含义
STOP		停止执行
LDA	0x008B,i	把008B载入寄存器A
LDA	0x008B,d	把内存单元8B中的内容载入寄存器A
STA	0x008B,d	把寄存器A中的内容存入内存单元8B
ADDA	0x008B,i	把008B加到寄存器A中
ADDA	0x008B,d	把内存单元8B中的内容加到寄存器A中
SUBA	0x008B,i	从寄存器A中减去008B
SUBA	0x008B,d	从寄存器A中减去内存单元8B中的内容
BR		分支到操作数说明符中指定的位置
CHARI	0x008B,d	读取一个字符，把它存入内存单元8B中
CHARO	0x008B,i	输出字符B
CHARO	0x008B,d	输出存储在内存单元8B中的字符
DECI	0x008B,d	读取一个十进制数，把它存储在内存单元8B中
DECO	0x008B,i	输出十进制数139（即十六进制的8B）
DECO	0x008B,d	输出存储在内存单元8B中的十进制数

6.4.3 Hello程序的汇编语言版本

注释：为程序读者提供的解释性文字
Pep/8汇编语言中，注释符为;类似于Python中的#

CHARO 0x0048,i; Output an 'H'
CHARO 0x0065,i; Output an 'e'
CHARO 0x006C,i; Output an 'l'
CHARO 0x006C,i; Output an 'l'
CHARO 0x006F,i; Output an 'o'
STOP
.END

这段代码即为输出Hello的程序源代码。
而书中又举例了一个程序，并引导了具有分支的程序和具有循环结构的程序。在这里并不一一赘述。其类似与Python中的判断和循环语句。

6.5 表达算法

算法是解决方案的计划或概要，或者是解决问题的逻辑步骤顺序。在中学中我们也学了逻辑语句，即如下图。

伪代码（pseudocode）：一种表达算法的语言

在6.5.1（伪代码的功能）的学习中，我们主要学习了伪代码的表达方式：复制、输入输出、选择以及重复
在6.5.2（执行伪代码）学习中则详细介绍了伪代码的执行
在6.5.3（写伪代码）中则介绍了伪代码编辑方法
在6.5.4（翻译伪代码算法）中则介绍了伪代码的翻译问题。

6.6 测试

测试计划：说明如何测试程序的文档
代码覆盖（明箱）测试法：通过执行代码中的所有语句测试程序或子程序的测试方法
数据覆盖（暗箱）测试法：把代码作为一个暗箱，基于所有可能的输入测试程序或子程序的测试方法。
测试计划实现：用测试计划中规定的测试用例验证程序是否输出了预期的结果。

第七章——问题求解与算法设计

7.1 如何解决问题

算法（algorithm）：在有限的时间内用有限的数据解决问题或子问题的明确指令集合

7.2 有简单参数的算法

嵌套结构（nested structure）：控制结构嵌入另一个控制结构的结构，又称为嵌套逻辑

7.7 几个重要思想

信息隐蔽（information hiding）：隐蔽模块的细节以控制对这些细节的访问的做法。
抽象（abstraction）：复杂系统的一种模型，只包括对观察者来说的必须章节。
数据抽象（data abstraction）：把数据的逻辑视图和它的实现分离开。
过程抽象（procedural abstraction）：把动作的逻辑视图和它的现实分离开。
控制抽象（control abstraction）：把控制结构的逻辑视图和它的现实分离开。
控制结构（control structure）：用于改变正常的顺序控制流的语句。