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

1、本文格式为word版，下载可任意编辑计算机算法实验报告范文(例文) 1. 试验名称 本次试验的名称。 2. 问题描述 对本次试验要解决的问题的描述。 例子：处理汉诺塔问题时，描述什么是汉诺塔问题。 3. 解决思路 采纳什么方法；为什么可以采纳这个方法； 例子：处理棋盘掩盖问题时， 采纳什么方法：采纳递归分治的方法处理； 为什么可以采纳递归分治方法的缘由（p21 页图 2-6 下面一段，理解之后用自己的话表述）：由于将棋盘横、纵各一分为二之后，特别方格必定位于四个小的棋盘之一，那么剩余的其余三个小棋盘是没有方格的，假如采纳某种 l 型骨牌掩盖没有特别方格的三个小棋盘的中心相连部分（参见图 2-6

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

3、:q-1；划分基准 aq=ap；右半部分 aq+1:r； 对左半部分快速排序 quicksort(a, p, q-1); 对右半部分快速排序 quicksort(a, q+1, r)； 例子：0-1 背包问题 递归关系或者递归方程。 给出 p72 页2.递归关系中的递归表达式，并给出文字说明。 留意：伪算法描述，或者递归方程不肯定全部需要。依据问题的不同，只给出伪算法，或者只给出递归方程都可以。两者同时给出也是可以的。 5. 程序实现 依据第 4 部分，给出 c 语言（其他语言亦可）的程序实现，并进行算法时间（空间）简单度分析。 程序实现部分要包括：程序代码、 程序解释、程序运行结果（或者截图

4、）。 例子：快速排序的 partition 函数 int partition (type a, int p, int r) int i=p, j= r+1; int x = ap; /x=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） * 消失，或者整个数组 ap:r扫描完毕（即 ir）为止。 */ while(a+ix ir); 6. 总结 不用每个试验写一个总结，可以在一次课作业的最终写一个总结。当