合肥工业大学
课程实验报告
第二篇:《计算机算法》实验报告模板
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. 总结
不用每个实验写一个总结,可以在一次课作业的最后写一个总结。当然,如果需要,在每一个实验结尾都写一个总结也是可以的。总结的目的是自己知识学习的总结、解决问题的总结、编程的总结等等。