《程序设计方法学》实验指导书.docx

《《程序设计方法学》实验指导书.docx》由会员分享，可在线阅读，更多相关《《程序设计方法学》实验指导书.docx（53页珍藏版）》请在优知文库上搜索。

1、程序设计方法学实验指导桂林理工大学“程序设计方法学”课程组编2017年8月实验一、分支和循环结构的简单程序设计2实验二、三递归算法、迭代算法及其比较3实验四、数组与栈的基本操作4实验五、归并排序与折半查找6附录A：RaPtor可视化程序设计概述71.RaPtOr是什么？72 .为什么要使用RaPtOr进行程序设计？73 .Raptor的安装84 .几个简单的Raptor程序8实例1.输出字符串aHe1.1.owor1.d!w8实例2：求两个整数中的较大值13实例3：求1+2+3+.+10的和22实验一、分支和循环结构的简单程序设计1.实验目的(1)熟悉可视化计算工具RaPIOr环境。(2)掌握

2、具有选择、循环语句的简单程序设计方法。(3)掌握基于可视化计算工具RaPtor的“子过程(子函数)”的使用方法。2 .实验准备(1)认真阅读本实验指导书“可视化计算工具RaPtOr概述”部分的内容，以及教材第2章的内容，了解第四章“算法”的基础知识。(2)熟悉可视化计算工具Raptor的使用。3 .实验内容使用RaPtor可视化计算工具，实现顺序、选择、循环3种程序结构的简单设计。(1)顺序结构程序设计：设计一个RaPsr程序，计算并输出两个正整数a和b的和，a和b的值由用户输入。(2)选择结构程序设计：设计一个RaP1.Or程序，计算两个整数a和b的最大值并输出，其中a和b的值由用户输入。(

3、3)循环结构程序设计：使用循环结构，设计一个Raptor程序，计算并输出1+2+3+100的的结果。(4)三个数最大值的判定：设计一个RaPtOr程序，输入三个数a、b和c,求最大值并输出。(5)编写Raptor迭代程序求n!。4 .实验步骤学生在实验老师的指导下自主完成，并提交实验报告。实验二、三递归算法、迭代算法及其比较1.实验目的(1)进一步熟悉可视化计算工具RaPtor环境；(2)掌握使用可视化计算工具Raptor编写递归及迭代程序的基本方法;(3)能够使用RaPtor工具对算法的复杂性进行简单分析。2 .实验准备(1)认真阅读木实验指导书“可视化计算工具Raptor概述”部分的内容，

4、以及教材第4章有关“算法”部分的内容；(2)进一步熟悉可视化计算工具RaPtor的使用。*3 .实验内容(1)设计raptor程序，输出右图金字塔图形:要求从键盘上可以输入任意金字塔层数。(2)用递归方式编写RaPtOr程序计算n!,对比实验-中的迭代求解方式，给出对比结果。(3)使用RaPtor可视化计算工具，编写梵天塔程序，包含主程序和子程序。(4)使用RaP1.Or可视化计算工具，编写并比较斐波那契数列(兔子问题)的递归和迭代算法。提示：Raptor有一个重要功能，它能计算对计算时间有消耗的基本符号的执行次数。在RaPtOr程序的运行结果中，它会统计出含有表达式的语句的执行次数。如图3.

5、1所示。；彳领台11旦g图3.1某个RaPtOr程序的运行结果从上图中可以看到结果中显示：“完成.运算次数为98”，这就是说执行了98次含有表达式的语句，含有表达式的语句的计算次数与程序的运行时间是成正比的，因此可以根据Raptor的统计结果分析程序的运行时间。采用上述方法，比较你所设计的求斐波那契数列的迭代和递归算法的运行时间，分析为什么会出现这样的结果？4 .实验步骤学生在实验老师的指导下自主完成，并提交实验报告。实验四、数组与栈的基本操作1.实验目的（1）掌握使用可视化计算工具Raptor创建一维数组和二维数组的方法。（2）理解数组“越界”的概念。（3）掌握顺序遍历一维、二维数组的基本方

6、法。（4）掌握查找有序一维、二维数组某个元素的基本方法。（5）能够使用算法复杂度的概念对求解同一类问题的不同算法进行评估。（6）掌握栈的基本概念。（7）掌握栈的PUSh和PoP操作，并能够使用数组模拟栈的操作。2 .实验准备（1）认真阅读“附录ARaPtOr可视化程序设计概述”的内容。（2）查找RaPtOr帮助文档，了解子图的使用方法.（3）阅读第4.2节内容。（4）阅读本教材第4.3节内容。（5）复习本教材第9.5节的内容。3 .实验内容（1）字符数组中单空格替换为双空格设计一个程序，完成以下功能。功能1：创建一个一维数组，数组内容如下：123456789IamT0m功能2：设计一个算法将单

7、个空格替换为双空格，即将数组拓展为12345678910HIamT0in.（2）二维数组中元素的查找设计一个程序，完成以下功能。功能1：创建一个长度为4行5列的二维数组，数组内容如图4.1所示。13479245810568111279131516图4.1数组元素功能2：设计一个算法，在数组中查找数值为8的元素，并输出其下标（行数和列数）。（3）假设表达式中允许包含3种括号：圆括号、方括号和大括号，这3种括号可以以任意的顺序嵌套,最里层的括号中可以加入字符，如（a+b）、a+b+c等是正确的格式，而a+b）、a-b等均为不正确的格式，也就是说处于同一层次的括号要相互匹配。设计一个程序，利用栈来判

8、断输入的表达式是否为正确的格式。4 .实验步骤学生在实验老师的指导下自主完成，并提交实验报告。实验五、归并排序与折半查找1.实验目的（1）熟练掌握二路归并排序算法。（2）熟练掌握折半查找算法。2 .实验准备（1）复习第9.4节、第9.5节的内容。（2）阅读第4.2.6节内容。3 .实验内容（1）子数组的合并算法。（2）二路归并排序。（3）折半查找。（4）背包问题。4 .实验步骤学生在实验老师的指导下自主完成，并提交实验报告。附录A：RaPtor可视化程序设计概述1 .Raptor是什么？Raptor(theRapidA1.gorithmicPrototypingToo1.forOrderedR

9、easoning用于有序推理的快速算法原型工具)是一种基于流程图的编程开发环境。流程图是系列的可连接的图形符号的集合，每一种符号代表一个可被执行的特定类型的指令，符号之间的连接决定指令的执行顺序。当你使用RaPur解决问题的时候，这些概念会越来越清晰。RaPtOr是由美国空军学院的MartinC.CarIiSIC博士带头开发的，其他的设计人员包括TerryA.Wi1.sonJeffreyW.HumphriesIUSStevenMHadfie1.d等,MartinC.Car1.is1.e博士目前为美国空军学院计算机科学系的一名教授。Raptor最初是为美国空军学院计算机科学系设计的，但是它的使用

10、已经得到了广泛的普及，目前该软件至少被17个不同国家用于计算机教学。Dr.MartinC.Car1.is1.e2 .为什么要使用Raptor进行程序设计？佐治亚理工学院(GeorgiaInstituteofTechno1.ogy)计算机学院的ShaCkeIfOrd和1.eB1.anc教授曾经注意到这样一个现象，在“计算概论”课程中使用一种特定的编程语言容易干扰并分散学生对于算法问题求解核心部分的注意力。教师都希望把时间用在他们认为学生最可能遇到困难的问题上，因此他们往往把授课的重点集中在语法上，这是他们希望学生能够克服的困难。(例如：在C语言环境中，错误的将关系运算符“=”当成了赋值符号“=或

11、者在语句结束时忘记了加分号等)。此外，北卡罗来纳大学的费尔德(Fe1.der)教授认为，大多数学生是视觉化的学习者，而教师们则往往倾向于提供口头讲授。据研究发现，大约有75%到83%的学生为可视化的学习者。因此对大多数初学者来说，传统的编程语言或伪代码由于具有高度的文本化而非可视化的性质，从而无法为他们提供直觉的算法表达框架。Raptor是被专门设计用于应对语法困难以及非视觉环境的缺陷的，Raptor允许学生通过连接基本的图形符号来创建算法，在RaPtOr环境中执行算法，还可以观察算法的步步的执行过程。通过RaPtor环境，可以观察到当前的程序执行到了哪个部分，可以看到所有的变量当前的内容。此

12、外，RaPIor还提供了一个基于AdaGraPh的简单的图形库，学生通过该图形库，不仅可以将算法视觉化，而且也可以将他们要解决的问题视觉化。MartinC.Car1.is1.e教授曾为美国空军学院的学生讲授“计算概论”课程，在该课程中有12个小时的算法方面的课程，一开始的时候，这一部分是使用Ada95和Mat1.ab进行讲授的。从2003年夏季开始，他们改用了Raptor讲授这一部分课程。在最后的结课考试中，他们追踪了需要学生设计算法来解决的三个问题，学生可以使用任何方式来表达他们的算法（Ada,Mat1.ab,流程图等等）。在这样的前提下，他们发现学生们更喜欢使用可视化的描述,而且那些学习过

13、使用Raptor进行算法设计的学生在考试中发挥的更加出色。使用Raptor进行程序设计主要基于以下几个原因：（1） RaPtOr开发环境可以最大限度地减少编写出正确的程序所需要的语法要求。（2） Raptor开发环境是可视化的。Raptor程序是一种一次执行一个图形符号的有向图，因此它可以帮助用户跟踪RAPTOR程序的指令流执行过程。（3） RaPtor是为了便于使用而设计的（相对于其他的免杂的开发环境，RaPtor开发环境非常简单，（4）对于初学者来说，使用RaP1.Or进行程序设计出现的调试和报错消息更易于理解。（5）使用Raptor的目的是进行算法设计和运行验证，这个目标不要求你了解像C

14、+或JAVA这样重量级的编程语言。3 .Raptor的安装可以在Raptor官方网站ht:/raptor.naUincar1.is1.e.COm/下载RaPtOr的安装文件，该网站上有几个不同的安装版本，推荐使用最新的安装版本，只需点击“Down1.oad1.atestVerSion”即可。该网站上还有一个便携版本，这个版本可以安装在U盘上使用。安装过程非常简单，只需双击安装文件，按照提示进行操作即可。4 .几个简单的Raptor程序下面介绍3个简单的Raptor程序实例，目的是通过这些实例使同学们对RaPtOr程序设计有一个基本的认识。实例1：输出字符串“He1.1.owor1.d!w打开R

15、aptor软件之后会弹出两个对话框，一个是Raptor的开始界面（如附图AT）,另一个是用于显示Raptor程序输出结果的界面（如附图A-2）：附图-1.Raptor的开始界面附图A-2显示Raptor程序输出结果界面附图A-I的左半部分是Raptor的六种基本符号：赋值(Assignment)、调用(Ca1.1)、输入(InPU。、输出(OUtPU。、选择(Se1.ection)和循环(1.OOP)O图的中间是主函数(main),它是程序执行的入口，框图start和框图end分别表示程序的开始和结束。在一个简单的He1.1.o,wor1.d!,程序中，涉及到两个基本符号，即赋值(ASSignment)和输出(OUtPUt)(当然也可以只用输出(OUt