深 圳 大 学 实 验 报 告

课程名称 计算机基础 项目名称 算法设计工具 学 院 生命与海洋科学学院 专 业 生命与海洋科学学院 指导教师 梁正平 报 告 人 学号 实验时间 2015.12.08 提交时间 2015.12.15

教务处制

一、实验目的与要求

1．加深对算法设计和流程图的认识和理解；

2．掌握算法设计工具Raptor的基本工作环境；

3．掌握顺序结构、选择结构和循环结构的设计方法；

4．掌握Raptor的子图和子程序设计方法。

二、实验内容与方法

三、实验步骤与过程

四、实验结论或体会

2、教师批改学生实验报告时间应在学生提交实验报告时间后10日内。

第二篇：《计算机算法》实验报告模板

1. 实验名称

本次实验的名称。

2. 问题描述

对本次实验要解决的问题的描述。

例子：处理汉诺塔问题时，描述什么是汉诺塔问题。

3. 解决思路

采用什么方法；为什么可以采用这个方法；

例子：处理棋盘覆盖问题时，

采用什么方法：采用递归分治的方法处理；

为什么可以采用递归分治方法的原因（P21页图2-6下面一段，理解之后用自己的话表述）：由于将棋盘横、纵各一分为二之后，特殊方格必然位于四个小的棋盘之一，那么剩余的其余三个小棋盘是没有方格的，如果采用某种L型骨牌覆盖没有特殊方格的三个小棋盘的中心相连部分（参见图2-6的b），则三个小棋盘都各有1个特殊方格所覆盖。因此，这样处理之后，原来大棋盘覆盖的问题，就转化为四个小棋盘覆盖的问题，因此可以采用分治策略进行递归处理。

4. 算法设计与分析

给出算法设计的基本思想，如：伪算法描述，递归方程等。并分析算法的时间复杂度（空间复杂度）。注意，一定要有文字说明。

例子：快速排序

伪算法描述

QuickSort(int a[], int p, int r)

{

如果待排序数组a[]中只有一个元素则直接返回；

如果待排序数组a[]中不止一个元素，则进行如下处理

{

对数组a[p:r]进行Partition划分，使得a[p:r]以a[p]为标准，划分为三个部分，即： 左半部分a[p:q-1]；划分基准a[q]=a[p]；右半部分a[q+1:r]；

对左半部分快速排序QuickSort(a, p, q-1);

对右半部分快速排序QuickSort(a, q+1, r)；

}

}

例子：0-1背包问题

递归关系或者递归方程。

给出P72页“2.递归关系”中的递归表达式，并给出文字说明。

注意：伪算法描述，或者递归方程不一定全部需要。根据问题的不同，只给出伪算法，或者只给出递归方程都可以。两者同时给出也是可以的。

5. 程序实现

依据第4部分，给出C语言（其他语言亦可）的程序实现，并进行算法时间（空间）复杂度分析。

程序实现部分要包括：程序代码、程序注释、程序运行结果（或者截图）。

例子：快速排序的partition函数

int Partition (Type a[], int p, int r)

{

int i=p, j= r+1;

int x = a[p]; //x=a[p]是对数组a进行划分的标准；

/* 以下循环将数组a[p:r]以a[p]为标准进行划分，在划分完毕之后，

* a[p]调整到数组a[p:r]的中间位置q，有a[q]=a[p]；q左边所有的

* 元素均小于a[p]，即a[p:q-1]中的任意元素都小于a[p]；q右边

* 所有的元素均大于a[p]，即a[q+1:r]中的元素都大于a[p]。

* /

while(true){

/* i用来从数组a[p:r]的左边向右边扫描，如果a[++i]中的元素总是

* 小于基准元素的，则是符合划分标准的，因此，不用额外处理，

* 循环一直继续,直到第一个不满足划分标准的a[++i]（即a[++i]>=i）

* 出现，或者整个数组a[p:r]扫描完毕（即i<r）为止。

*/

while(a[++i]<x && i<r);

??

6. 总结

不用每个实验写一个总结，可以在一次课作业的最后写一个总结。当然，如果需要，在每一个实验结尾都写一个总结也是可以的。总结的目的是自己知识学习的总结、解决问题的总结、编程的总结等等。