程序设计层

低级程序设计语言与伪代码

计算机操作

计算机是能够存储、检索和处理数据的可编程电子设备。

存储、检索和处理是计算机能够对数据执行的动作。

机器语言

机器语言：由计算机直接使用的二进制编码指令构成的语言

由于指令的数量有限，所以处理器的设计者就列出所有的指令，给每个指令分配一个二进制代码来表示它们。

处理器与它能够执行的指令之间的关系十分和谐。

每条机器语言指令只能执行一个非常低级的任务。

Pep8:一台虚拟机

机器代码因机器的不同而不同。

**虚拟机：为了模拟真实机器的重要特征而设计的假想机器。

Pep/8反映的重要特性

-内存由65536字节的存储空间，Pep/8的字长是2字节。

寄存器重点有三个

·程序计算器PC，其中包含下一条即将被执行的指令的地址

·指令寄存器IR，其中包含正在被执行的指令的一个副本

·累加器（是一个寄存器）

指令格式

一条指令由两部分组成，即8位的指令说明符和16位的操作数说明符。指令说明符说明了要执行什么操作和如何解释操作数的位置。操作数说明符存放的是操作数本身或者操作数的地址。

指令说明符的格式根据表示一个具体操作所用的比特数的不同而不同，//操作代码//的长度从4到8比特不等。4比特操作码的第5位用来制定使用哪个寄存器。寄存器A（累加器）的寄存器说明符是0.

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

·如果是000，那么指令的操作数说明符中存储的就是操作数，这种寻址模式称为立即寻址（i）。

·如果是001，那么操作数说明符中存储的是操作数所在的内存地址名称。这种寻址模式成为直接寻址（d)。

没有操作数（要处理的数据）的指令成为一元指令

一些示例指令

0000停止执行

1100将操作数载入寄存器A中

1110将寄存器A中的内容存储到操作数中

0111将操作数加到寄存器A中

1000将寄存器A中的值中减去操作数的值

01001把字符输入操作符

01010从操作数输出字符

一个程序实例

手工模拟

·从程序计数器制定的位置读取下一条指令

·译解指令并且更新程序计数器

·如果需要，获取诗句操作数

·执行指令

Pep/8模拟程序‘

装入程序：软件用于读取机器语言并把它载入内存部分

汇编语言

汇编语言给每条机器语言指令分配了一个助记指令码，程序艳可以用这些指令码代替二进制数字。

汇编器：把汇编语言程序翻译成机器代码的程序

Pep/8汇编语言

STOP 停止执行

LDA 把008B载入寄存器A

LDA 把内存单元8B中的内容载入寄存器A中

STA 把寄存器A中的内容存贮内存单元8B

ADDA 把008B加到寄存器A中

ADDA 把内存单元8B中的内容加到寄存器A中

汇编器指令

汇编器指令 翻译程序使用的指令

·ASCII 表示一个ASCII字节的字符串

`BLOCK 创建一个字节块

·WORD 创建一个字，并存值进去

·END 表示汇编语言程序的结束

Hello程序的汇编语言版本

Pep/8汇编语言允许我们直接指定字符输出，还允许我们在指令旁边添加注释

注释 为程序读者提供的解释性文字

汇编语言程序 输入 汇编器 输出 机器代码程序

一个新程序

最复杂的是，我们必须把这里的四个识别符合内存单元关联起来。

具有循环的程序

读入任意数量的值。我们通过创建计数循环代码来实现这个功能。

表达算法

我们以文字叙述形式表达了每个问题的解决方案，然后再写代码。在计算领域，解决方案的计划被称为算法。伪代码是一种语言，可以让我们以更清晰的形式表达算法。

伪代码的功能

·变量

·赋值

把一个值放到变量sum中

Set sum to 0 或sum<-1

访问sum和sum中的值

Set sum to sum+num或sum<-sum+num

·输入/输出

我们可以使用Write语句进行输入，使用Read语句进行输入

执行伪代码算法

While(商不为0）

用新的基数除十位制数

余数作为结果中的最左边一位

用商替换原来的十进制数

写伪代码算法

桌面检查：在纸上走查整个设计

翻译伪代码算法

测试

测试计划：说明如何测试程序的文档

代码覆盖（明箱）测试法：通过执行代码中的所有语句测试程序或子程序的测试方法

数据覆盖（暗箱）测试法：把代码作为一个暗箱，基于所有可能的输入数据测试程序或子程序的测试方法

测试计划实现:用测试计划中规定的测试用例验证程序是否输出了预期的结果。

问题求解与算法设计

如何解决问题

提出问题

·必须理解问题。

·找到信息和解决方案之间的联系。如果找不到直接的联系，则可能血药考虑辅助问题。最终，应该得到解决方案。

·执行方案

·分析得到的解决方案

寻找熟悉的情况

识别相似的情况在计算机领域内是非常有用的。

分治法

可以把一项任务分成若干个子任务，而子任务还可以继续划分为子任务，如此进行下去。可以反复利用分治法，直到每个子任务都是可以实现的为止。

算法

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

计算机问题求解过程

分析和说明阶段

分析

说明

算法开发阶段

开发算法

测试算法

实现阶段

编码

测试

维护阶段

使用

维护

方法总结

·分析问题

·列出主要任务

编写其余模块

·根据需要进行重组和改写

测试算法

有简单参数的算法

带有选择的算法

IF.....

.....

ELSE IF...

......

带有循环的算法

计数循环算法

三个部分 循环控制变量 测试 增量

Set count to 0

While(count<limit)

....

Set count to count+1

事件控制循环

Read a value

While (value>=0)

......

Read a value

...

嵌套结构：控制结构嵌入另一个控制结构的结构，又称为嵌套逻辑。

平方根

Read in square

Calculate the square root

Write out square and the square root

`Calculate square root

Set epsilon to 1

WHILE(epsilon>0.001)

Calculate new guess

Set epsilom to abs

抽象步骤：细节仍未明确的算法步骤

具体步骤：细节完全明确的算法步骤

复杂变量

数组

数组是同构项目的有名集合

项目在集合中的位置叫做索引

integer numbers[10]

Write "Enter 10 integer numbers,one per line"

Set position to 0

WHILE (position<10)

Read in numbers[positon]

Set position to position+1

记录

Employee employee

Set employee.name to "Frank Jones"

Set emplpueea.age to 32

搜索算法

顺序搜索

Set position to 0

Set found to FLASE

WHILE (position<10 AND found is FLASE)

IF(numbers[position]equals searchltem)

Set found to TRUE

ELSE

Set position to position + 1

有序数组中的顺序搜索

Read in many of vlaues

Write "Enter value for which to search"

Read searchltem

Set found to TRUE if searchltem is there

IF (found)

Write "Item is found"

ELSE

Write "Item is not found"

二分检索

二分检索：在有序列表中查到项目的操作，通过比较错做排除大部分检索范围

排序

选择排序

冒泡排序

插入排序

递归算法

递归：算法调用本身的能力

子程序语句

递归阶乘

递归二分检索

快速排序

几个重要思想

信息隐蔽：隐蔽模块的细节以控制对这些细节的访问的做法

抽象：复杂系统的一种模型，只包括对观察这来说必需的细节

事物命名

测试

收获

了解了机器语言和简单的汇编语言

不足

英语单词储备不足，表示代码看不懂，解释也看不懂