福建师范大学协和学院
本科实验报告
课程名称： 《算法设计与分析》 学院（系）： 专 业： 班 级： 学 号： 学生姓名：
实验项目
实验项目实验项目名称 序号 序号 1 一 2 3 4 二 5 6 三 7 8 四 9 五 10 11 12 六 13 七 14 15 16 八 17 18 九 0/背包问题 回溯法求解巡游问题 回溯法求解0/1背包问题 分支与限界求解0/1背包 随机算法 近似算法 1 1 1 1 1 单源最短路径的dijstra算法 多段图最短路径（动态规划） 最优资源分配（动态规划） KMP模式串匹配 1 1 1 1 分治法求棋盘覆盖问题 贪婪法求解普通背包问题 1 1 分治找K大元素 平面最近点对 1 1 成绩 学时 预习 0.5 0.5 1 1 指导教师 操作 实验 基数排序 合并排序 寻找主元素 递归求排列 综合实验（题目抽取方式决定） 0 统计 总成绩： 1
《算法设计与分析》实验报告填写要求
一、本课程共需完成实验项目十八个（包含综合性实验项目一个），分八次实验完成（其
中综合实验项目课外完成，期末统一收取评分，综合实验占实验成绩50％）。每一次实验均须提交一份实验预习报告和一份实验报告，批改后下发的实验报告请保存起来，期末上交。
二、实验报告书写要求：
1. 实验目的和要求：明确实验的内容和具体任务；
2. 列出源程序，备注说明程序的基本结构，包括程序中各部分的功能。 3. 说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂性，并给出
计算过程。
4. 实验结果与分析：给出不少于3组数据测试算法，并将每组测试数据的运行结
果列出，并对调试源程序的结果进行分析，杜绝只罗列不分析；
5. 讨论、建议、质疑：针对实验中碰到的问题进行组内以及组外讨论，遇到不能
解决的问题时向指导老师请教，并将问题的提出以及解决的过程写入实验报告，以作为以后学习的参考。问题要具体描述，避免抽象地罗列、笼统地讨论； 6. 全部文字叙述内容要求简明扼要，思路清楚； 7. 实验日期、同组员姓名写清楚。
三、要求实验报告字迹工整、文字简练、数据齐全、计算正确，分析充分、具体、定量。对于抄袭实验报告和编篡原始数据的行为，一经发现，以零分处理，并根据相关条例给予处分。
2
福建师范大学协和学院实验预习报告
指导教师签字： 成绩：
实 验 一 排序验证与设计实验
任务描述：
? 项目一 基数排序 （验证实验）
实验要求
1．要求利用基数排序的思想完成n个正整数排序，完全理解算法的思想 2．了解程序的执行过程，正确分析算法的时间复杂性
3．参照课本68-70页代码，完成代码编写并调试正确，给出三组10个整数以上的测试数据进行测试并得出正确结果。
? 项目二 合并排序 （验证实验） 实验要求
1．要求利用合并排序的思想完成n个正整数排序，完全理解算法的思想 2．了解程序的执行过程，正确分析算法的时间复杂性
3．参照课本中的程序，完成代码编写并调试正确，给出三组6个整数以上的测试数据进行测试并得出正确结果。
? 项目三 找主元素（设计实验）
问题描述：
在数组中，有一半以上的元素相同，设计一个算法，以Ｏ（n）时间找到这个元素。（可用非递归，也可用递归） 实验要求
1．设计出正确的算法，以Ｏ(n)时间找到主元素 2．了解程序的执行过程，正确分析算法的时间复杂性
3．，完成代码编写并调试正确，对以下三种数据要求测试通过： 第一组：1，1，1，2，3，4，1 第二组：1，2，2，2，3，2，4 第三组：1，3，4，2，2，2，2
3
预习内容：
一、实验目的和要求
二、实验原理和内容（每个项目分析出拟用到的算法思路）
项目一：
项目二：
项目三：
4
三、项目实现的主要源代码 项目一：
项目二：
项目三：
5
福建师范大学协和学院实验报告
实验日期： 年 月 日 星期 组员姓名：
指导教师签字： 成绩：
实 验 一 排序验证与设计实验
? 项目一 基数排序 （验证实验）
一、 重要的程序说明（说明程序的基本结构以及程序中各部分的功能）
二、 算法复杂性分析与计算（说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂
性，并定出计算过程）
三、 程序运行测试结果列举：
6
四、程序调试过程中遇到的错误，如何讨论、有何建议与质疑
五、思考题
试想想，这样的排序算法有什么局限性？能对所有的算例都就用这种算法吗？
? 项目二 合并排序 （验证实验）
一、 重要的程序说明（说明程序的基本结构以及部分的功能）
7
二、 算法复杂性分析与计算（说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂
性，并定出计算过程）
三、 程序运行测试结果列举：
四、程序调试过程中遇到的错误，如何讨论、有何建议与质疑
五、思考题
为什么合并排序是思想是基于比较类排序里面最快的，它成功的地方在哪儿？
? 项目三 寻找主元素 （设计实验）
一、 重要的程序说明（说明程序的基本结构以及各部分的功能）
8
二、 算法复杂性分析与计算（说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂
性，并定出计算过程）
三、 程序运行测试结果列举：
四、程序调试过程中遇到的错误，如何讨论、有何建议与质疑
9
福建师范大学协和学院实验预习报告
指导教师签字： 成绩：
实 验 二 递归与分治验证与设计实验
任务描述：
实验项目四 递归求排列问题 （验证实验） 一、问题描述：
在一个具有n个元素的数组中，运用递归生成全排列，并输出。 二、实验要求
1．根据课本上P82页子函数，补充相应的主函数，完成程序 2．了解程序的执行过程，正确分析算法的时间复杂性
3．对三组数据要求测试通过（每组数据用4个整数测试）： 4．记录实验过程，规范完成实验报告。
实验项目五 分治找k大元素（设计实验） 一、问题描述：
在一个具有个元素的数组中，找出第二大元素，并计算时间杂性（要求O(n)时间） 二、实验要求
1．设计出正确的算法，以Ｏ(n)时间找到第二大元素 2．了解程序的执行过程，正确分析算法的时间复杂性
3．，完成代码编写并调试正确，对三组数据要求测试通过（第组数据不少于20个）： 4．记录实验过程，规范完成实验报告。
预习内容：
一、实验目的和要求
二、实验原理和内容（每个项目分析出拟用到的算法思路）
10
项目四：
项目五：
三、项目拟实现的主要源代码 项目四：
项目五：
11
福建师范大学协和学院实验报告
实验日期： 年 月 日 星期 组员姓名：
指导教师签字： 成绩：
实 验 二 递归与分治设计实验
? 项目四 递归求排列 （验证实验）
一、 重要的程序说明（说明程序的基本结构以及程序中各部分的功能）
二、 算法复杂性分析与计算（说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂
性，并定出计算过程）
三、 程序运行测试结果列举：
12
四、程序调试过程中遇到的错误，如何讨论、有何建议与质疑
五、思考题
试想想，递归思想有什么样的优缺点，在调试过程中，随着数据量的增大，调试过程与结果有没有变化？为什么？
? 项目五 分治求K大元素 （设计实验）
一、 重要的程序说明（说明程序的基本结构以及部分的功能）
13
二、 算法复杂性分析与计算（说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂
性，并定出计算过程）
三、 程序运行测试结果列举：
四、程序调试过程中遇到的错误，如何讨论、有何建议与质疑
五、思考题
这种求K大元素与前面学过的合并排序有无关联？仔细想一想他们的本质。
14
福建师范大学协和学院实验预习报告
指导教师签字： 成绩：
实 验 三 分治法验证与设计实验
任务描述：
实验项目六 求平面最近点对（验证实验） 一、问题描述：
平面内有若干点，利用分治法，以O(nlogn)时间求出平面内直线距离最近的一对点，并求出它们的距离。 二、实验要求
1．了解程序的执行过程，正确分析算法的时间复杂性
2. 完成代码编写并调试正确，对三组数据要求测试通过（每组数据点不少于10个）： 3．记录实验过程，规范完成实验报告。
实验项目七 分治法求棋盘覆盖问题 （设计实验） 一、问题描述：
在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
二、实验要求
1．利用分治法完成程序设计，输出棋盘覆盖矩阵
2．说明算法原理以及程序的执行过程，正确分析算法的时间复杂性 3．对4×4，8×8棋盘进行测试。 4．记录实验过程，规范完成实验报告。
15
预习内容：
一、实验目的和要求
二、实验原理和内容（每个项目分析出拟用到的算法思路）
项目六：
项目七：
三、项目拟实现的主要源代码 项目六：
16
项目七：
17
福建师范大学协和学院实验报告
实验日期： 年 月 日 星期 组员姓名：
指导教师签字： 成绩：
实 验 三 分治法验证与设计实验
? 项目六 分治法求平面最近点对（验证实验）
一、 重要的程序说明（说明程序的基本结构以及程序中各部分的功能）
二、 算法复杂性分析与计算（说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂
性，并定出计算过程）
18
三、 程序运行测试结果列举：
四、程序调试过程中遇到的错误，如何讨论、有何建议与质疑
五、思考题
为什么用分治法求平面最近点对时间效率会高些，这样的思想还能用于解决什么样的实际问题？试举出2～3个实例说明一下。
? 项目七 分治求棋盘覆盖问题 （设计实验）
一、 重要的程序说明（说明程序的基本结构以及部分的功能）
19
二、 算法复杂性分析与计算（说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂
性，并定出计算过程）
三、 程序运行测试结果列举：
四、程序调试过程中遇到的错误，如何讨论、有何建议与质疑
20
福建师范大学协和学院实验预习报告
指导教师签字： 成绩：
实 验 四 贪婪法验证实验
任务描述：
实验项目九 背包问题（验证实验） 一、问题描述：
载重量为M的背包，重量为wi、价值为pi的物体，1?i?n，把物体装满背包，使背包内的物体价值最大，物体可以分割的背包问题
二、实验要求
1．了解程序的执行过程，正确分析算法的时间复杂性
2. 完成代码编写并调试正确，对三组数据要求测试通过（每组物体不少于10件）： 3．记录实验过程，规范完成实验报告。 实验项目十 单源最短路径问题 （验证实验） 一、问题描述：
在图10的有向赋权图中，求顶点a到其它所有顶点的最短距离。
b e 1 9 1 2 6 2 4 3 5 a c f h 4 3 4 1 3 7 d g
图10
二、实验要求
1．利用贪婪算法，结果课本上P123源码完成程序设计，输出结果 2．说明算法原理以及程序的执行过程，正确分析算法的时间复杂性 3．对上图中的有向图进行测试。 4．记录实验过程，规范完成实验报告。
21
预习内容：
一、实验目的和要求
二、实验原理和内容（每个项目分析出拟用到的算法思路）
项目九：
项目十：
三、项目拟实现的主要源代码 项目九：
22
项目十：
23
福建师范大学协和学院实验报告
实验日期： 年 月 日 星期 组员姓名：
指导教师签字： 成绩：
实 验 四 贪婪法验证实验
? 项目九 普通背包问题（验证实验）
一、 重要的程序说明（说明程序的基本结构以及程序中各部分的功能）
二、 算法复杂性分析与计算（说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂
性，并定出计算过程）
24
三、 程序运行测试结果列举：
四、程序调试过程中遇到的错误，如何讨论、有何建议与质疑
五、思考题
如果背包内物体不能分割，这样的方法还行得通吗？为什么？你能从中找出什么样的启发？
? 项目十 单源最短路径问题 （验证实验）
一、 重要的程序说明（说明程序的基本结构以及部分的功能）
25
二、 算法复杂性分析与计算（说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂
性，并定出计算过程）
三、 程序运行测试结果列举：
四、 程序调试过程中遇到的错误，如何讨论、有何建议与质疑
五、 思考题：
为什么这种方法求下来的路径一定是最短？试分析一下它的正确性。
26
福建师范大学协和学院实验预习报告
指导教师签字： 成绩：
实 验 五 动态规划验证与设计实验（上）
任务描述：
实验项目十一 动态规划多段图单源最短路径（验证实验） 一、问题描述：
利用动态规划求解图所示的0到9最短距离及路径。
9 1 4 5 4 8 6 6 7 7 7 8 0 2 5 9 1 6 1 8 6 8 3 3 4 3 6 5 7
二、实验要求
1．了解程序的执行过程，正确分析算法的时间复杂性 2. 完成代码编写并调试正确，对上图数据要求测试通过 3．记录实验过程，规范完成实验报告。
实验项目十二 资源最优分配问题 （设计实验） 一、问题描述：
现有5个份额的资源，分配给3个工程，其利润函数如下：
x 1 2 3 4 5 G1(x) 7 13 16 17 19 G2(x) 6 12 14 16 18 G3(x) 5 18 19 20 22 设计出合理的算法，求资源的最优分配方案。
二、实验要求
1．说明算法原理以及程序的执行过程，正确分析算法的时间复杂性 2．对上述中的实例进行测试。 3. 记录实验过程，规范完成实验报告。
27
预习内容：
一、实验目的和要求
二、实验原理和内容（每个项目分析出拟用到的算法思路）
项目十一：
项目十二：
三、项目拟实现的主要源代码 项目十一：
28
项目十二：
29
福建师范大学协和学院实验报告
实验日期： 年 月 日 星期 组员姓名：
指导教师签字： 成绩：
实 验 五 动态规划验证与设计实验（上）
项目十一 动态规划求解多段图最短路径问题
一、重要的程序说明（说明程序的基本结构以及程序中各部分的功能）
二、算法复杂性分析与计算（说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂性，
并定出计算过程）
30
三、程序运行测试结果列举：
四、程序调试过程中遇到的错误，如何讨论、有何建议与质疑
五、思考题
什么是多段图？为什么这种方法只能用于多段图？普通图能不能用动态规划来求解，为什么？
项目十二 最优资源分配方案设计 （设计实验）
一、 重要的程序说明（说明程序的基本结构以及部分的功能）
31
二、 算法复杂性分析与计算（说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂
性，并定出计算过程）
三、 程序运行测试结果列举：
四、 程序调试过程中遇到的错误，如何讨论、有何建议与质疑
32
福建师范大学协和学院实验预习报告
指导教师签字： 成绩：
实 验 六 动态规划验证与设计实验（下）
任务描述：
实验项目十三 模式串匹配问题 （设计实验） 一、问题描述：
利用动态规划的方法，设计出一算法，求出A?xyxzyxyzzy，B?xzyzxyzxyzxy的最长公共子序列。 二、实验要求
1．说明算法原理以及程序的执行过程，正确分析算法的时间复杂性 2．写出源码，对上述中的实例进行测试。 3．记录实验过程，规范完成实验报告。 实验项目十四 0/1背包问题 （验证实验） 一、问题描述：
有6个物体，其重量分别为5，3，7，2，3，4，价值分别为3，6，5，4，3，4，背包的载重量为15，利用动态规划的方法，求出在背包不超载的情况下，使背包内价值量最大的装载方法（物体不可分割）。 二、实验要求
1．说明算法原理以及程序的执行过程，正确分析算法的时间复杂性 2．写出源码，对上述中的实例进行测试。 3．记录实验过程，规范完成实验报告。
预习内容：
一、实验目的和要求
33
二、实验原理和内容（每个项目分析出拟用到的算法思路）
项目十三：
项目十四：
三、项目拟实现的主要源代码 项目十三：
34
项目十四：
35
福建师范大学协和学院实验报告
实验日期： 年 月 日 星期 组员姓名：
指导教师签字： 成绩：
实 验 六 动态规划验证与设计实验（下）
项目十三 设计动态规划算法解决模式串匹配的问题（设计实验） 一、重要的程序说明（说明程序的基本结构以及程序中各部分的功能）
二、算法复杂性分析与计算（说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂性，
并定出计算过程）
三、程序运行测试结果列举：
36
四、程序调试过程中遇到的错误，如何讨论、有何建议与质疑
项目十四 最优资源分配方案设计 （设计实验）
一、 重要的程序说明（说明程序的基本结构以及部分的功能）
二、 算法复杂性分析与计算（说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂
性，并定出计算过程）
37
三、 程序运行测试结果列举：
四、 程序调试过程中遇到的错误，如何讨论、有何建议与质疑
五、 思考题：
这种方法能解决所有的0/1背包问题吗？想想有什么条件限制没有？举例说明！
???????
38
福建师范大学协和学院实验预习报告
指导教师签字： 成绩：
实 验 七 回溯法验证与设计实验
任务描述：
实验项目十五 回溯法解决马步遍历问题（设计实验） 一、问题描述：
设计一算法，求解国际象棋中的马的周游问题：给定一8×8的棋盘，马从棋盘的某个位置出发，经过棋盘中的每一个方格恰好一次。（只需求一可行解） 二、实验要求
1．了解程序的执行过程，正确分析算法的时间复杂性 2. 完成代码编写并调试正确，对8×8棋盘数据要求测试通过 3．记录实验过程，规范完成实验报告。
实验项目十六 回溯法求解0/1背包问题 （验证实验） 一、问题描述：
给定背包的载重量M＝20，有6个物体，价值分别为11，8，15，18，12，6，重量分别为5，3，2，10，4，2。利用回溯法求解上述问题。 二、实验要求
1．说明算法原理以及程序的执行过程，正确分析算法的时间复杂性 2．对上述中的实例进行测试。 3．记录实验过程，规范完成实验报告。
预习内容：
一、实验目的和要求
39
二、实验原理和内容（每个项目分析出拟用到的算法思路）
项目十五：
项目十六：
40
三、项目拟实现的主要源代码 项目十五：
项目十六：
41
福建师范大学协和学院实验报告
实验日期： 年 月 日 星期 组员姓名：
指导教师签字： 成绩：
实 验 七 回溯法验证与设计实验
项目十五 利用回溯思想设计一算法解决马步遍历问题（设计实验） 一、重要的程序说明（说明程序的基本结构以及程序中各部分的功能）
二、算法复杂性分析与计算（说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂性，
并定出计算过程）
三、程序运行测试结果列举：
42
四、程序调试过程中遇到的错误，如何讨论、有何建议与质疑
五、思考题：
用回溯方法求解问题时候最大的缺点是什么？这样的问题有没有解决的办法，如果有，应该从哪方面考虑去实现？
项目十六 回溯阖求解0/1背包问题 （验证实验）
一、 重要的程序说明（说明程序的基本结构以及部分的功能）
43
二、 算法复杂性分析与计算（说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂
性，并定出计算过程）
三、 程序运行测试结果列举：
四、 程序调试过程中遇到的错误，如何讨论、有何建议与质疑
五、 思考题：
这种方法能解决所有的0/1背包问题吗？想想有什么条件限制没有？
44
福建师范大学协和学院实验预习报告
指导教师签字： 成绩：
实 验 八 分支限界法与随机算法的验证与设计实验
任务描述：
实验项目十七 限界与剪枝求解0/1背包问题 （验证实验） 一、问题描述：
给定背包的载重量M＝20，有6个物体，价值分别为11，8，15，18，12，6，重量分别为5，3，2，10，4，2。利用回溯法求解上述问题。 二、实验要求
1．说明算法原理以及程序的执行过程，正确分析算法的时间复杂性 2．对上述中的实例进行测试。 3．记录实验过程，规范完成实验报告。
实验项目十八 对快速排序的随机性进行改进，提高其运行的平均时间效率 （设计实验） 实验要求
1．写出正确的代码，正确分析算法的时间复杂性 2．对相应的实例进行测试。 3．记录实验过程，规范完成实验报告。
实验项目十九 对PK算法进行随机性改进，减少误配率 （设计实验） 实验要求
1．写出正确的代码，正确分析算法的时间复杂性 2．对相应的实例进行测试。 3．记录实验过程，规范完成实验报告。。
45
预习内容：
一、实验目的和要求
二、实验原理和内容（每个项目分析出拟用到的算法思路）
项目十七：
项目十八：
项目十九：
46
三、项目拟实现的主要源代码 项目十七：
项目十八：
项目十九：
47
福建师范大学协和学院实验报告
实验日期： 年 月 日 星期 组员姓名：
指导教师签字： 成绩：
实 验 八 分支限界法与随机算法的验证与设计实验
项目十七 利用分支与限界法解决0/1背包问题（验证实验） 一、重要的程序说明（说明程序的基本结构以及程序中各部分的功能）
二、算法复杂性分析与计算（说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂性，
并定出计算过程）
三、程序运行测试结果列举：
48
四、程序调试过程中遇到的错误，如何讨论、有何建议与质疑
五、思考题：
用回溯方法求解问题时候最大的缺点是什么？这样的问题有没有解决的办法，如果有，应该从哪方面考虑去实现？
项目十八 对快速排序的随机性进行改进，提高其运行的平均时间效率 （设计实验） 一、 重要的程序说明（说明程序的基本结构以及部分的功能）
49
算法设计与分析实验报告手册 - -2010.2初稿
