《计算机算法》实验报告例文(例文).doc

1、计算机算法实验报告例文(例文)1.实验名称 本次实验的名称。2.问题描述 对本次实验要解决的问题的描述。例子：处理汉诺塔问题时，描述什么是汉诺塔问题。3.解决思路 采用什么方法；为什么可以采用这个方法； 例子：处理棋盘覆盖问题时， 采用什么方法：采用递归分治的方法处理； 为什么可以采用递归分治方法的原因（P21 页图 2-6 下面一段，理解之后用自己的话表述）：由于将棋盘横、纵各一分为二之后，特殊方格必然位于四个小的棋盘之一，那么剩余的其余三个小棋盘是没有方格的，如果采用某种 L 型骨牌覆盖没有特殊方格的三个小棋盘的中心相连部分（参见图 2-6 的 b），则三个小棋盘都各有 1 个特殊方格所覆

2、盖。因此，这样处理之后，原来大棋盘覆盖的问题，就转化为四个小棋盘覆盖的问题，因此可以采用分治策略进行递归处理。4.算法设计与分析p 给出算法设计的基本思想，如：伪算法描述，递归方程等。并分析p 算法的时间复杂度（空间复杂度）。注意，一定要有文字说明。例子：快速排序 伪算法描述 QuickSort(int a, int p, int r) 如果待排序数组 a中只有一个元素则直接返回； 如果待排序数组 a中不止一个元素，则进行如下处理 对数组 ap:r进行 Partition 划分，使得 ap:r以 ap为标准，划分为三个部分，即：左半部分 ap:q-1；划分基准 aq=ap；右半部分 aq+1:

3、r； 对左半部分快速排序 QuickSort(a, p, q-1);对右半部分快速排序 QuickSort(a, q+1, r)； 例子：0-1 背包问题 递归关系或者递归方程。给出 P72 页“2.递归关系”中的递归表达式，并给出文字说明。注意：伪算法描述，或者递归方程不一定全部需要。根据问题的不同，只给出伪算法，或者只给出递归方程都可以。两者同时给出也是可以的。5.程序实现 依据第 4 部分，给出 C 语言（其他语言亦可）的程序实现，并进行算法时间（空间）复杂度分析p 。程序实现部分要包括：程序代码、程序注释、程序运行结果（或者截图）。例子：快速排序的 partition 函数 int P

4、artition (Type a, int p, int r) int i=p, j= r+1;int _ = ap;/_=ap是对数组 a 进行划分的标准； /_以下循环将数组 ap:r以 ap为标准进行划分，在划分完毕之后，_ap调整到数组 ap:r的中间位置 q，有 aq=ap；q 左边所有的_元素均小于 ap，即 ap:q-1中的任意元素都小于 ap；q 右边_所有的元素均大于 ap，即 aq+1:r中的元素都大于 ap。_/while(true) /_i 用来从数组 ap:r的左边向右边扫描，如果 a+i中的元素总是 _小于基准元素的，则是符合划分标准的，因此，不用额外处理， _循环

5、一直继续,直到第一个不满足划分标准的 a+i（即 a+i>=i）_出现，或者整个数组 ap:r扫描完毕（即 i总结 不用每个实验写一个总结，可以在一次课作业的最后写一个总结。当然，如果需要，在每一个实验结尾都写一个总结也是可以的。总结的目的是自己知识学习的总结、解决问题的总结、编程的总结等等。的确也是我想说的。1.实验名称本次实验的名称。2.问题描述对本次实验要解决的问题的描述。例子：处理汉诺塔问题时，描述什么是汉诺塔问题。3.解决思路采用什么方法；为什么可以采用这个方法； 例子：处理棋盘覆盖问题时，采用什么方法：采用递归分治的方法处理；为什么可以采用递归分治方法的原因（P21页图2-6

6、下面一段，理解之后用自己的话表述）：由于将棋盘横、纵各一分为二之后，特殊方格必然位于四个小的棋盘之一，那么剩余的其余三个小棋盘是没有方格的，如果采用某种L型骨牌覆盖没有特殊方格的三个小棋盘的中心相连部分（参见图2-6的b），则三个小棋盘都各有1个特殊方格所覆盖。因此，这样处理之后，原来大棋盘覆盖的问题，就转化为四个小棋盘覆盖的问题，因此可以采用分治策略进行递归处理。4.算法设计与分析p 给出算法设计的基本思想，如：伪算法描述，递归方程等。并分析p 算法的时间复杂度（空间复杂度）。注意，一定要有文字说明。 例子：快速排序 伪算法描述QuickSort(int a, int p, int r) 如

7、果待排序数组a中只有一个元素则直接返回； 如果待排序数组a中不止一个元素，则进行如下处理 对数组ap:r进行Partition划分，使得ap:r以ap为标准，划分为三个部分，即：左半部分ap:q-1；划分基准aq=ap；右半部分aq+1:r； 对左半部分快速排序QuickSort(a, p, q-1);对右半部分快速排序QuickSort(a, q+1, r)； 例子：0-1背包问题递归关系或者递归方程。给出P72页“2.递归关系”中的递归表达式，并给出文字说明。 注意：伪算法描述，或者递归方程不一定全部需要。根据问题的不同，只给出伪算法，或者只给出递归方程都可以。两者同时给出也是可以的。5.

8、程序实现依据第4部分，给出C语言（其他语言亦可）的程序实现，并进行算法时间（空间）复杂度分析p 。程序实现部分要包括：程序代码、程序注释、程序运行结果（或者截图）。 例子：快速排序的partition函数 int Partition (Type a, int p, int r) int i=p, j= r+1; int _ = ap; /_=ap是对数组a进行划分的标准；/_以下循环将数组ap:r以ap为标准进行划分，在划分完毕之后，_ap调整到数组ap:r的中间位置q，有aq=ap；q左边所有的_元素均小于ap，即ap:q-1中的任意元素都小于ap；q右边_所有的元素均大于ap，即aq+1:r中的元素都大于ap。_/while(true) /_i用来从数组ap:r的左边向右边扫描，如果a+i中的元素总是 _小于基准元素的，则是符合划分标准的，因此，不用额外处理， _循环一直继续,直到第一个不满足划分标准的a+i（即a+i>=i） _出现，或者整个