计算机科学导论实验指导书

计算机科学导论

实验指导

桂林电子科技大学

“计算机科学导论”课程组编写

2016年8月

目录

实验一、分支和循环结构的简单程序设计................................2

实验二、存储程序式计算机的简单程序设计..............................3

实验三、递归算法、迭代算法及其比较.................................5

实验四、数组与栈的基本操作.........................................7

实验五、归并排序与折半查找........................................9

实验六、简单的卡通与游戏实验.....................................10

附录A：Raptor可视化程序设计概述..................................13

1.Raptor是什么？.............................................13

2.为什么要使用Raptor进行程序设计？..........................13

3.Raptor的安装...............................................14

4.几个简单的Raptor程序......................................14

实例1：输出字符串“Helloworld!w........................14

实例2：求两个整数中的较大值..............................19

实例3：求1+2+3+....+10的和...............................28

附录B：Vcomputer存储程序式计算机概述.............................31

1.Vcompter存储程序式计算机虚拟机软件简介...................31

2.Vcomputer机器的结构和指令................................31

3.Vcomputer机器上的汇编指令集..............................32

4.汇编程序编写过程中的注意事项..............................32

5.机器指令（十六进制代码）编写过程中的注意事项...............33

6.存储程序式计算机模拟平台的功能............................33

7.计算机模拟平台的注意事项..................................33

附录C：教材中的问题及实验（供参考）...............................34

实验一、分支和循环结构的简单程序设计

1.实验目的

(1)熟悉可视化计算工具Raptor环境。

(2)掌握具有选择、循环语句的简单程序设计方法.

(3)掌握基于可视化计算工具Raptor的“子过程(子函数)”的使用方法。

2.实验准备

(1)认真阅读本实验指导书“可视化计算工具Raptor概述”部分的内容，以及教材第2

章的内容，了解第四章“算法”的基础知识。

(2)熟悉可视化计算工具Raptor的使用。

3.实验内容

使用Raptor可视化计算工具，实现顺序、选择、循环3种程序结构的简单设计。

(1)顺序结构程序设计：设计一个Raptor程序，计算并输出两个正整数a和b的和，a和

b的值由用户输入。

(2)选择结构程序设计：设计一个Raptor程序，计算两个整数a和b的最大值并输出，其

中a和b的值由用户输入。

(3)循环结构程序设计:使用循环结构，设计一个Raptor程序，计算并输出1+2+3+....+100

的的结果。

4.实验步骤

学生在实验老师的指导下自主完成，并提交实验报告。

实验二'存储程序式计算机的简单程序设计

1.实验目的

（1）熟悉Vcomputer存储程序式计算机虚拟机环境，理解指令系统的组成，掌握机器指令

的格式和理解程序的执行过程。

2.实验准备

（1）认真阅读本实验指导书"Vcomputer存储程序式计算机概述”部分的内容，以及教材

第3章的内容。

（2）熟悉Vcomputer存储程序式计算机虚拟机环境，完成教材习题三第17题（3.17）至第

34题的作业，为上机验证作好准备。

3.实验内容

（1）使用Vcomputer存储程序式计算机仿真软件，分析软件所带的3个实例（解释每一条

指令及整个程序的作用），分别将机器代码的程序转换为汇编语言的程序，或将汇编语言的

程序翻译为机器指令。

；机器指令代码（16进制数）

2007

2101

2202

2300

5221

5331

5232

8212

8008

9000

;汇编语言程序

LOADR0,01

LOADR1,FF

LOADR2,02

LABEL1:ADDR3,R1,RO

JMPR3,LABEL2

ADDR4,R1,R2

JMPR4,LABEL2

SHLRO,01

JMPR2,LABEL2

SHLRO,08

NOTRO

JMPRI,LABEL1

LABEL2:HALT

；机器指令代码(16进制数)

2001

21FF

2202

5310

8318

5412

8418

6001

8218

6008

7000

8106

9000

(2)使用Vcomputer存储程序式计算机仿真软件，验证教材习题三第17题(3.17)至第

34题作业的答案。

4.实验步骤

学生在实验老师的指导下自主完成，并提交实验报告。

实验三、递归算法、迭代算法及其比较

1.实验目的

（1）进一步熟悉可视化计算工具Raptor环境；

（2）掌握使用可视化计算工具Raptor编写递归及迭代程序的基本方法;

（3）能够使用Raptor工具对算法的复杂性进行简单分析。

2.实验准备

（1）认真阅读本实验指导书“可视化计算工具Raptor概述”部分的内容，以及教材第4

章有关“算法”部分的内容；

（2）进一步熟悉可视化计算工具Raptor的使用。

3.实验内容

（1）使用Raptor可视化计算工具，编写并比较斐波那契数列（兔子问题）的递归和迭代算法。

提示：Raptor有一个重要功能，它能计算对计算时间有消耗的基本符号的执行次数。

在Raptor程序的运行结果中，它会统计出含有表达式的语句的执行次数。如图3.1所示。

图3.1某个Raptor程序的运行结果

从上图中可以看到结果中显示："11symbolsevaluated这就是说执行了11次含有表达

式的语句，含有表达式的语句的计算次数与程序的运行时间是成正比的，因此可以根据

Raptor的统计结果分析程序的运行时间。

采用上述方法，比较你所设计的求斐波那契数列的迭代和递归算法的运行时间，分析为什么

会出现这样的结果？

4.实验步骤

学生在实验老师的指导下自主完成，并提交实验报告。

实验四、数组与栈的基本操作

1.实验目的

(1)掌握使用可视化计算工具Raptor创建一维数组和二维数组的方法。

(2)理解数组“越界”的概念。

(3)掌握顺序遍历一维、二维数组的基本方法。

(4)掌握查找有序一维、二维数组某个元素的基本方法。

(5)能够使用算法复杂度的概念对求解同一类问题的不同算法进行评估。

(6)掌握栈的基本概念。

(7)掌握栈的push和pop操作，并能够使用数组模拟栈的操作。

2.实验准备

(1)认真阅读“附录ARaptor可视化程序设计概述”的内容。

(2)查找Raptor帮助文档，了解子图的使用方法。

(3)阅读第4.2节内容。

(4)阅读本教材第4.3节内容。

(5)复习本教材第9.5节的内容。

3.实验内容

(1)字符数组中单空格替换为双空格

设计一个程序，完成以下功能。

功能1：创建一个一维数组，数组内容如下:

123456789

IamT0m

功能2：设计一个算法将单个空格替换为双空格，即将数组拓展为

1234567891011

IamT0m

(2)二维数组中元素的查找

设计一个程序，完成以下功能。

功能I：创建一个长度为4行5列的二维数组，数组内容如图4.1所示。

13479

245810

5681112

79131516

图4.1数组元素

功能2：设计一个算法，在数组中查找数值为8的元素，并输出其下标(行数和列数)。

(3)假设表达式中允许包含3种括号：圆括号、方括号和大括号，这3种括号可以以任意

的顺序嵌套,最里层的括号中可以加入字符,如{[(a+b)]}、[{a+b+c}]等是正确的格式，而

[a+b)、{[a-b}]等均为不正确的格式，也就是说处于同一层次的括号要相互匹配。设计一个

程序，利用栈来判断输入的表达式是否为正确的格式。

4.实验步骤

学生在实验老师的指导下自主完成，并提交实验报告。

实验五、归并排序与折半查找

1.实验目的

(1)熟练掌握二路归并排序算法。

(2)熟练掌握折半查找算法。

2.实验准备

(1)复习第9.4节、第9.5节的内容。

(2)阅读第4.2.6节内容。

3.实验内容

(1)子数组的合并算法。

(2)二路归并排序。

(3)折半查找。

(4)背包问题。

4.实验步骤

学生在实验老师的指导下自主完成，并提交实验报告。

实验六、简单的卡通与游戏实验

L实验目的

(1)熟悉可视化计算工具Raptoro

(2)掌握Raptor中的6种符号的使用。

(3)掌握Raptor图形库的基本操作。

2.实验准备

(1)了解Raptor的绘图操作、键盘操作、鼠标操作、文本操作和窗口操作。

(2)熟悉Raptor的6种符号的使用方法。

(3)熟悉使用Windows自带的画图工具，并能够使用标尺、网格线、状态栏等找到特定点

的坐标。

(4)了解使用ColorSchemerstudio工具搭配不同的颜色。

3.实验内容

(1)绘制HelloKitty

绘制如图5.1所示的HelloKitty»

图5.1HelloKitty图示

(2)绘制一朵花

绘制花图案，如图5.2所示。

图9.3绘制小花

(3)设计一个“找茬”游戏

设计一个找茬游戏，图片示例如图5.3所示。

(a)找茬游戏图1

(b)找茬游戏图2

图5.3找茬游戏图片

4.实验步骤

学生在实验老师的指导下自主完成，并提交实验报告。

附录A：Raptor可视化程序设计概述

1.Raptor是什么？

Raptor(theRapidAlgorithmicPrototypingToolforOrderedReasoning—用于

有序推理的快速算法原型工具)是一种基于流程图的编程开发环境。流程图是一系列的可连

接的图形符号的集合，每一种符号代表一个可被执行的特定类型的指令，符号之间的连接决

定指令的执行顺序。当你使用Raptor解决问题的时候，这些概念会越来越清晰。

Raptor是由美国空军学院的MartinC.Carlisle博士带头开发的，其他的设计人员包

括TerryA.Wilson>JeffreyW.Humphries以及StevenM.Hadfield等,MartinC.Carlisle

博士目前为美国空军学院计算机科学系的一名教授。Raptor最初是为美国空军学院计算机

科学系设计的，但是它的使用已经得到了广泛的普及，目前该软件至少被17个不同国家用

于计算机教学。

Dr.MarlinC.Carlisle

2.为什么要使用Raptor进行程序设计？

佐治亚理工学院(GeorgiaInstituteofTechnology)计算机学院的Shackelford和

LeBlanc教授曾经注意到这样一个现象，在“计算概论”课程中使用一种特定的编程语言容

易干扰并分散学生对于算法问题求解核心部分的注意力。教师都希望把时间用在他们认为学

生最可能遇到困难的问题上，因此他们往往把授课的重点集中在语法上，这是他们希望学生

能够克服的困难。(例如：在C语言环境中，错误的将关系运算符“==”当成了赋值符号

或者在语句结束时忘记了加分号等)。

此外，北卡罗来纳大学的费尔德(Felder)教授认为，大多数学生是视觉化的学习者，

而教师们则往往倾向于提供口头讲授。据研究发现，大约有75%到83%的学生为可视化的

学习者。因此对大多数初学者来说，传统的编程语言或伪代码由于具有高度的文本化而非可

视化的性质，从而无法为他们提供直觉的算法表达框架.

Raptor是被专门设计用于应对语法困难以及非视觉环境的缺陷的，Raptor允许学生通

过连接基本的图形符号来创建算法，在Raptor环境中执行算法，还可以观察算法的一步步

的执行过程。通过Raptor环境，可以观察到当前的程序执行到了哪个部分，可以看到所有

的变量当前的内容。止匕外，Raptor还提供了一个基于AdaGraph的简单的图形库，学生通过

该图形库，不仅可以将算法视觉化，而且也可以将他们要解决的问题视觉化。

MartinC.Carlisle教授曾为美国空军学院的学生讲授“计算概论”课程，在该课程

中有12个小时的算法方面的课程，一开始的时候，这一部分是使用Ada95和Matlab进行

讲授的。从2003年夏季开始，他们改用了Raptor讲授这一部分课程。在最后的结课考试中，

他们追踪了需要学生设计算法来解决的三个问题，学生可以使用任何方式来表达他们的算法

（Ada,Matlab,流程图等等）。在这样的前提下，他们发现学生们更喜欢使用可视化的描述,

而且那些学习过使用Raptor进行算法设计的学生在考试中发挥的更加出色。

使用Raptor进行程序设计主要基于以下几个原因：

（1）Raptor开发环境可以最大限度地减少编写出正确的程序所需要的语法要求。

（2）Raptor开发环境是可视化的。Raptor程序是一种一次执行一个图形符号的有向图，

因此它可以帮助用户跟踪RAPTOR程序的指令流执行过程。

（3）Raptor是为了便于使用而设计的（相对于其他的复杂的开发环境，Raptor开发环

境非常简单）。

（4）对于初学者来说，使用Raptor进行程序设计出现的调试和报错消息更易于理解。

（5）使用Raptor的目的是进行算法设计和运行验证，这个目标不要求你了解像C++或

JAVA这样重量级的编程语言。

3.Raptor的安装

可以在Raptor官方网站http://raptor,martincarlisle,com/下载，Raptor的安装文件,

该网站上有几个不同的安装版本，推荐使用最新的安装版本，只需点击"Downloadlatest

versionw即可。该网站上还有一个便携版本，这个版本可以安装在U盘上使用。安装过程

非常简单，只需双击安装文件，按照提示进行操作即可。

4.几个简单的Raptor程序

下面介绍3个简单的Raptor程序实例，目的是通过这些实例使同学们对Raptor程序设

计有一个基本的认识。

实例1；输出字符串"Hell。world!”

打开Raptor软件之后会弹出两个对话框，一个是Raptor的开始界面（如附图A-1）,

另一个是用于显示Raptor程序输出结果的界面（如附图A-2）：

附图A-lRaptor的开始界面

附图A-2显示Raptor程序输出结果界面

附图A-1的左半部分是Raptor的六种基本符号:赋值(Assignment)、调用(Call)、输

入(Input)、输出(Output)、选择(Selection)和循环(Loop)。图的中间是主函数(main),它

是程序执行的入口，框图start和框图end分别表示程序的开始和结束。

在一个简单的"Hello,world!"程序中，涉及到两个基本符号，即赋值(Assignment)

和输出(Output)(当然也可以只用输出(Output)符号，这里是为了了解这两种基本符号)。

输出“Hello,World!”字符串，基本思路是先将该字符串存储在某个地方，然后对其

进行输出。如何存储该字符串呢？这里就需要用到赋值符号。附图A-3是插入赋值符号后

的效果。

附图A-3插入赋值符号

在附图A-2中，只需单击左半部分的Assignment符号框，然后将其拖动到start与end

之间即可。接下来是将字符串“Hello,World!”赋值给某个变量的过程。

当双击赋值符号框之后，会弹出如附图A-4的对话框，该对话框是赋值语句对话框，

可以通过它将“Hello,World!"字符串赋值给某个变量（该字符串被存储在内存中的某个空

间内，可以通过该变量来访问这段内存空间）。在“set”后面的文本框中输入变量的名称，

可以用它来访问字符串"Hello,World!”，在“to”后面的文本框中输入想要存储的值,即

“Hello,World!”,然后单击“done”即可。这里要注意一点,输入的字符串需要加双引号，

效果如附图A-5所示。

附图A-4赋值语句对话框

附图A-5将字符串“Hell。,World!"赋值给变量s

接下来就可以完成对字符串进行输出了，为了进行输出，需要Output符号框,与对Assignment

符号框的操作一样，可以采用同样的方式将Output符号框拖动到Assignment符号框与end

之间，效果如附图A-6所示。

附图A-6加入Output符号框

接下来，双击Output符号框，会弹出输出语句对话框，如附图A-7所示。

附图A-7输出语句对话框

因为要输出的是“Hello,World!”，而“Hello,World!v已赋值给了变量s,因此只需输出s

即可，在输出语句对话框的空白处输入s,单击“done”按钮，得到的完整的Raptor程序如

附图A-8所示。

附图A-8完整的Raptor程序

设计好了完整的Raptor程序之后,接下来就可以运行程序了，可以通过两种方式运行Raptor

程序。一种是点击图7中红色箭头所指的图标;另一种方式是单击Run下拉菜单下的Execute

tocompletion选项即可，在程序运行之后会在程序输出对话框中显示程序运行结果，如图

9所示。

附图A-9程序的运行结果

正如附图A-9显示的那样，程序输出了我们想要的结果。“Runcomplete”提示程序成功的

得到了执行，若程序执行失败，会提示“Error”。后面的“4symbolsevaluated”表示的

是程序中表达式语句的执行次数。根据Raptor的这一功能，我们可以粗略的分析算法的复

杂度。

选择开始界面中的File选项，选择下拉菜单中的save按钮，对Raptor文件进行保存,

Raptor文件的后缀名是.rap。而“Saveas”选项允许用户将Raptor文件以指定的名称保

存到指定的位置。

实例2：求两个整数中的较大值

在第一个例子中介绍了一个简单的输出程序，其中包括赋值(Assignment)与输出

(Output)符号框，接下来介绍一个求两个整数的较大值的程序，该程序包含更多的符号框。

若求两个数a和b的较大值，与第1个例子中直接使用赋值符号不同，此处使用输入符

号框(Input),在使用输入符号框的情况下，在程序执行到输入符号框时，用户输入的值即为

变量的值。插入输入符号框的结果如附图A-10。

附图A-10插入a和b的输入符号框

双击输入符号框(Input),会弹出如附图A-11所不的窗口，其中在"EnlerPrompthere”部分

要求我们输入提示文本，也就是对将要输入的变量进行说明，比如变量类型、范围等等，

“EnterVariablehere”部分要求输入变量名，该变量用于存储我们输入的变量值。此处要输

入的是一个整数，因此在提示文本部分可以输入"Pleaseenteravalueforvariablea:",用a来

存储待输入的变量值，因此在下半部分的文本框中输入a；对变量b进行相同的操作，并点

击done按钮，得到的结果如附图A-12所示。

附图A-11为输入符号框输入提示文本和变量名

附图A-12定义输入符号框

接下来使用一种新的符号框一调用(Call),通过该符号框可以调用一个能够完成特定功能的

子过程，该子过程也被称为子函数。加入调用符号框之后，结果如附图AT3所示。

插入调用符号框是为了调用一个子过程，在调用该子过程之前需要先定义它，可以要求该子

过程能够完成两个整数的比较，并返回比较的结果。定义子过程的方法如下，首先右击

main（如附图A-13的红色箭头所示），在弹出的选项中选择AddProcedure,弹出的对话框

如附图AT4所示。

附图A-14插入子过程

若子过程取名为compare,即在ProcedureName下面的文本框中输入compare,compare需

要参数，参数既是要进行处理的数据，也就是要进行比较的数值，

Parameter!.......Parameters代表参数，参数分为两种类型：输入类型（input）和输出

类型（output）,可以通过在参数后边的框中进行选择相应的类型。在compare子过程中，

可以设置三个参数r,a和b（此处参数名称可以选择用其他的合法字符表示，不仅限于r,

a,b）。将第一个参数设置为输出（output）类型，用于保存比较后所得到的结果，剩下的

两个参数为输入（input）类型，用于保存将要进行比较的数值。结果如附图A-15所示。

CreateProcedure

Namesmust,beginwithletteir,exidcoxit.a.in

onlylet.terszrtwnbersand.xutderscores.

Examples：

Diraw_Boxes

Firtd__SmaJLlest.

ProcedureName

|compax'e

Parameter1(orblank)|Iztpxit.VOntpvit

13r

Parameter2(orblank)Inpnt|"""Output

1a

Parameter3(orblank)VInput\"Ontpxit

[b-

Parameter4(orblank)VInp\xt|~Output

r

Pararrketer5(orblank)VIrtpnt.|"Output

r

Parameter6(orblank)Tnpxit.|~~Output.

r

OkICancel

N

附图A-15定义子过程的名称和参数

点击ok按钮，可以得到如附图A-16所示的子过程。

接下来需要对该子过程进行定义，此处需要选择(Selection)符号，因为进行的是比较，需

要根据不同的情况进行转移(比如，若a>b,下一步该如何操作？，a<b又该如何操作？)。

两个数a、b进行大小比较的时候可以分为两种情况，第一种是a<=b,在这种情况下，可以将

a、b中的任意一个赋值给r,此处可以将b赋值给r；第二种是a>b,在这种情况下，较大

值为a。

单击选择(selection)符号框，将其拖动到start之后，双击selection中的菱形，弹出附图

A-18的输入选择条件对话框，在该对话框中，需要输入分支条件，在此输入a>b(当然也可

以输入a<=b,不同的选择对应的分支不同)，点击“done”按钮，结果如附图A-19所示。

附图A-18输入选择条件对话框

附图A-19输入分支条件

在附图AT9中，当a>b成立时，也就是对应左分支(Yes),此时较大值为a,用r保存结果，

因此要插入赋值符号框并将a赋值给r；当a>b不成立时，也就是右分支(No),此时也要插

入赋值符号框将b赋值给r。单击赋值(Assignment)符号框，将其拖动到Yes和No对应箭

头的下方，并进行赋值，结果如附图A-20所示。

附图A-20分支选择后的结果

定义好“子过程”，接下来通过调用(call)符号框来调用该子过程，单击附图AT3中的调用

符号框，会弹出附图A-21中的对话框。

附图A-21输入调用的子过程对话框

在附图A-21中要求输入需要调用的子过程，要调用的是已经定义过的compare子过程，可

以在图中看到提示，最开始的部分是子过程的名称(如OpenGraphWindow),括号里边的

内容是子过程的参数，这里要注意的一点是参数匹配，这里所说的匹配包括参数个数、参数

顺序和参数类型。输入compare(m,a,b),点击done按钮得到的结果如附图A-22所示。

附图A-22调用子过程

在compare(m,a,b)中，m对应的是子过程中的r,而r是用来存储输出的结果的，在调用子

过程结束时，会将r的值传递给m。最后定义一个名为result的变量来存储最终的结果并

将其输出，因此需要插入赋值符号，并将m的值赋给result并输出result,这也就是我们

最终要得到的完整Raptor程序，结果如附图A-23所示。

附图AT3完整的程序

点击运行程序按钮，当程序执行到第一个输入符号框时，会弹出如附图A-24所示的输入变

量对话框，这里要求我们输入a的数值（可以输入一个整数，比如8）,输入数值后，点击0K

按钮，程序会继续向下执行（后边会遇到要求我们为b输入数值）。观察程序的运行过程，可

以看到对子过程的调用。最终的运行结果如附图A-25所示。

附图A-24为变量输入数值

*MasterConsole

FontFontSizeEditHelp

--一Runcomplete.11symbolsevaluated.—

附图A-25变量a为8,变量b为12时程序的运行结果

实例3：求1+2+3+....+10的和

在上面的两个简单的例子中，介绍了基本的输入输出符号以及分支符号，在本例中引入另一

种重要的符号，即循环符号。

首先在程序中加入三个变量i,j和sum,用sum表示最终求得的结果；i即为当前进行累加

的值，又是当前统计的累加的变量个数，因此i的初始值为1;j为变量的总数，因为本例

中一共有10个变量，因此j的值为10。具体的操作在前面的两个例子中都有过详细的说明,

此处不再赘述。结果见附图A-26。

附图A-26给三个变量赋值

接下来是程序中最重要的部分，也就是引入循环符号。循环符号需要一个判断条件，利用该

条件是否成立来判断要循环是否继续。在该例中要计算10个数的累加，因此当i的值大于

10时循环即结束。否则继续执行累加。

单击循环(Loop)符号将其拖入sum赋值符号的下方，结果如附图A-27所示。

附图A-27加入循环符号

双击循环符号的菱形部分，会弹出如附图A-28的对话框，该对话框要求输入循环是否继续

进行的条件，由于此处做的是对10个数进行累加，因此可以输入i〉j(i的初始值为1,j

当i>j时.，说明已经进行了10次累加，循环结束，并输出计算结果；如果i〈=j,那么累加

还未结束，接下来要继续进行累加。累加的实现方式如下：首先，sum=sum+i,这是进行第

i次累加，在进行第i次累加之前，sum存储的是前i-1次累加的结果（i从1递增到i-1）,

然后加上i,即可得到前i次累加的结果；其次，因为下一次要进行的是第i+1次累加，还

要判断i的值是否大于j以确定循环是否继续进行，因此还要执行i=i+l操作。加入这两步

操作并输出sum即可得到完整的Raptor程序。完整的Raptor程序如附图A-29所示。程序

的运行结果如附图A-30所示。

附图A-29完整的raptor程序附图A-30程序的运行结果

附录B：Vcomputer存储程序式计算机概述

1.Vcompter存储程序式计算机虚拟机软件简介

Vcompter存储程序式计算机虚拟机软件的文件名为compalpha（一般要先安装java运行环

境，然后双击该软件即可运行），该软件是桂林电子科技大学“计算机科学导论”课程组开

发的一个公共教学辅助软件，是2013年高等教育出版社出版的《计算机科学导论：思想与

方法（第2版）》的配套软件。该软件由课程实验老师提供，使用该软件可以加深同学们对

存储程序式计算机（冯•诺依曼计算机）的理解。该软件的主界面如下图所示。

国存储程序式计宜机虚拟机

中央处理器物理内存机器代科十六进制编辑汇编程序文本编辑

通用寄存器地址内容

0000▲

0100

三

0200

0300

0400

0500

0600

0700

0800

0900

0A00

程序计数器

0B00

加0C00

0D00

指令寄存器0E00

0F00

0000

1000

1100

1200

中央处理器单步执行1300

1400

1500

1600

中央处理器初始化

1700▼

计篁机操作系统命令模拟需

打开机器代吗十六迸制文件

机器代叫程序装叠到物理内存汇编程序转换为机器代叫

新建机器代码十六进制文件

开始机拟执行机器代码十六进制机器代用反汇编

保存机器代玛十六进制文件

2.Vcomputer机器的结构和指令

Vcomputer共有256个主存单元（分别用十六进制00〜FF表示），6个通用寄存器（0~5）,1

个程序计数器和1个指令寄存器。

机器的指令共有9条，每条指令的长度均为2个字节（用十六进制表示共4位）。指令的第

1个十六进制数字为操作码；指令的后3个十六进制数字为操作数，如附表B-1所示：

附表BTVComputer机器的指令集

操作码操作数描述

1RXY将主存XY单元中的数取出，存入寄存器R中。如1543,将主存43单元中的

数取出，存入寄存器5中

2RXY将数XY存入寄存器R中。如2543,将43（十六进制数）存入寄存器5中

3RXY将寄存器R中的数取出，存入内存地址为XY的单元中

40RS将寄存器R中的数存入寄存器S中

5RST将寄存器S与寄存器T中用补码表示的数相加，结果存入寄存器R中

6R0X将寄存器R中的数左移X位（先将R中的十六进制数转换为二进制数，再左

移X位），移位后，用0填充腾空的位

7R00将寄存器R中的数按位取反。如7100,将寄存器1中的数按位取反，将结果

存入寄存器1中

8RXY若寄存器R与寄存器0中的值相同，则将数据XY（转移地址）存入程序计数

器；否则，程序按原来的顺序继续执行

9000停机，9000

3.Vcomputer机器上的汇编指令集

Vcomputer机器的汇编指令共9条，与其机器指令一一对应，如附表B-2所示：

附表B-2Vcomputer机器的汇编指令与机器指令对照表

操作码操作数汇编指令描述

1RXYLoadR,[XY][R]：=[XY]

2RXYLoadR,XY[R]:=XY

3RXYStoreR,[XY][XY]:=[R]

40RSMovR,S[S]:=[R]

5RSTAddR,S,T[R]：=[S]+m

6R0XShiR,X[R]：=[R]左移X位，移位后，用0填充腾空的位

7R00NotR[R]:=[R]中的值按位取反

8RXYJmpR,XY程序计数器[PC]：=XY,IF[R]=[R0]；else[PC]:=[PC]+2

9000Halt停机

4.汇编程序编写过程中的注意事项

汇编程序编写过程中有以下注意事项：

（1）注释

汇编程序可以包含注释，注释含一行中从分号起到该行结束的所有符号。

（2）白空格

汇编程序文本中的白空格包括空格符（SPACE键），制表符（TAB键），换行符（ENTER

键）.

（3）语句标号

汇编语句可以有标号，标号只能以字母开头，后面只能跟字母，数字，下划线。标号后

面必须跟冒号，标号与冒号之间不能有白空格。例如，“label:”这样的标号定义不符合

规定。标号后面的冒号与操作码之间可以有多个白空格。

（4）分隔符

操作码与第一个操作数之间至少包含一个白空格.操作数之间通过逗号分隔，操作数与

逗号，逗号与操作数之间可以有多个白空格。

（5）数值

数值全部用十六进制表示。

（6）字母大小写

VComputer机器的汇编语句不区分字母的大小写。

5.机器指令（十六进制代码）编写过程中的注意事项

（1）在机器代码（十六进制代码）文件的编写过程中，注意，一行只能写1个指令，

共4位（16进制数）；

（2）在机器代码（十六进制代码）文件中，1个指令编写好后，换行写另一个指令。

6.存储程序式计算机模拟平台的功能

本平台的设计基于Vcomputer的指令，并有如下功能：

（1）能够对汇编程序进行编辑、保存或打开新的文件（TXT文件）；

（2）能够对机器指令按十六进制的形式进行编辑、保存或打开新的文件（TXT文件）;

（3）能够将汇编程序转化为十六进制的机器代码；

（4）能够将十六进制的机器代码转化为汇编程序；

（5）能够将机器代码程序装载到物理内存；

（6）能够模拟程序在机器中的执行过程；

（7）可以模拟程序在机器中单步运行过程；

（8）可以对中央处理器进行初始化操作（即对CPU中的各类寄存器置零）；

（9）任何时候都可以直接修改物理内存的内容；

（10）任何时候都可以直接修改程序计数器（PC）中的值（单步执行（一步完成）时,

首先，根据程序计数器中修改后的地址，将相应的机器指令取出，存入指令寄存器中；其次,

执行存入指令寄存器中的新指令；最后，将程序计算器的值+2）；

（11）指令寄存器中的值不能修改（初始值为空）。

7.计算机模拟平台的注意事项

若无法正常打开或保存文件，请按以下方式设置IE：工具-Xnlernat选项，安全，自定

义级别-＞对没有标记为安全的ActiveX控件进行初始化和脚本运行-＞启用-＞确定。

附录C：教材中的题目(问题)及实验

第二章学科的基本问题

实验2.1汉诺塔问题

1实验目的与要求

(1)理解计算学科的基本问题，能够对学科中的经典问题进行分类。

(2)掌握递归方法的概念和基本思想。

(3)使用Raptor设计一个程序，采用递归方法求解汉诺塔问题。

2实验题目

汉诺塔问题。如附图CT所示，有X、Y、Z三根柱子。X柱子上按从小到大的顺序堆放

了N个盘子，要把所有的盘子从X柱移动到Z柱，移动过程中可以借助Y柱。移动时有如下

要求：

(1)一次只能移动一个盘子。

(2)不允许把大盘放在小盘上面。

(3)盘子只能放在三根柱子上。

XYZ

附图C-1汉诺塔

3问题分析

汉诺塔问题是一个典型的用递归方法来求解的问题。递归是计算学科中的一个重要概

念。所谓递归，就是将一个较大的问题归约为一个或多个子问题的求解方法，要求这些子问

题在结构上与原问题相同。下面对该问题进行分析。

当N=1时，问题比较简单，只需将这唯一的盘子直接从X柱移动到Z柱。

当N=2时，则需要移动3步：

(1)把X柱上的小盘子移动到Y柱上。

(2)把X柱上的大盘子移动到Z柱上。

(3)把Y柱上的小盘子移动到Z柱上。

如果N的值比较大时，需要很多步才能完成移动过程。这时可以这样考虑，利用Y柱作

为辅助，若能设法将X柱上的前N-1个盘子从X柱移动到Y柱上，则可先将X柱上最底下的

盘子从X柱移动到Z柱上，然后再将Y柱上的N-1个盘子移动到Z柱上。

如何将n-1个盘子从一个柱子移动到另一个柱子的问题是一个和原问题具有相同特征

属性的问题，只是问题的规模小1,因此可以用同样的方法求解，这就是所谓的递归过程。

可以按照这种思路，一直递归到最后只剩下一个盘子，按照移动一个盘子的方法移动，递归

结束。

4设计Raptor程序

关键是设计一个完成移动操作的子程序，将该子程序命名为move,该子程序有四个参

数，分别为三根柱子的名称和盘子的数量。如move(n,A,B,C),表示借助C柱将n个盘子从

A柱移动到B柱。

move子程序如附图C-2所示。

附图C_2move子程序

在move子程序中有详细的标注说明了程序的每一部分说完成的功能。最开始是子程序

的入口，一开始的时候我们要解决的是移动N个盘子的问题，随着递归过程的进行，问题的

规模会逐渐缩小，直至递归结束。在子程序中有一个判断条件，即n是否等于1。当n不等

于1时，会执行右分支，这个过程既是不断缩小问题规模的过程，也是不断的递归调用自身

的过程；当n=l时，是剩下最后一个盘子的情况，此时只需进行一步移动操作，程序结束。

设计好了move子程序，接下来要设计main程序。main程序完成变量的初始化以及调

用move子程序。main程序如附图C-3所示，当盘子数目等于3时程序运行结果如附图54

所示。

附图C~3main程序子图

彳MasterConsole[o|回

附图C-4盘子数量为3时程序的运行结果

实验2.2贪心算法一-数字三角形问题

1实验目的与要求

（1）了解使用贪心算法能够处理的问题。

（2）理解贪心算法的基本思想。

（3）设计一个Raptor程序使用贪心算法求解数字三角形问题。

2实验题目

数字三角形的求解。有任意一个数字三角形（如附图C-5所示），只能自第一层（顶层）向

下行走，且只能走下接的相邻两个节点（如第3层的1只能走第4层的5或1）,问能否找到

一条路径，使得路径上的权值之和最大（最大权值路径应为1->2->1->5->80（89））?

1

23

165

5182

80210192

附图C-5数字三角形案例

3问题分析

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。

也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。贪心算

法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解

或者是整体最优解的近似解。

贪心算法是通过做一系列的选择来给出某一问题的最优解。对算法中的每一个决策点，

做一个当时（看起来是）最佳的选择，然后再解决抉择之后所出现的子问题。贪心算法所做的

当前选择可能要依赖于已经做出的所有选择，但不依赖于有待于做出的选择或子问题的解，

因此贪心策略通常是自顶向下的一个一个的做出贪心选择，不断地将给定的问题实例规约为

更小的问题。

在本例的数值三角形中，从顶层开始，当向第二层行走时，依据贪心策略选择一个可以

走得通的权值最大的点；在此基础上，在向第三层行走时;还是遵循同样的原则选择一个权

值最大的点，依次类推直到走到最底层结束。

4设计Raptor程序

首先将数字三角形的节点信息