《算法设计与分析》实验报告.doc

福建师范大学协和学院本科实验报告课程名称： 算法设计与分析 学院（系）： 专 业： 班 级： 学 号： 学生姓名： 学 号： 学生姓名： 学 号： 学生姓名： 实验项目实验序号项目序号实验项目名称实验成绩一1快速排序2合并排序3* 寻找主元素二4递归求排列5* 分治找K大元素三6平面最近点对7* 分治法求棋盘覆盖问题四8贪婪法求解普通背包问题9单源最短路径的dijstra算法五10多段图最短路径（动态规划）11* 最优资源分配（动态规划）六12* KMP模式串匹配130/背包问题七14* 回溯法求解巡游问题15回溯法求解0/1背包问题总分标题前加*号的实验题目为设计实验算法设计与分析实验报告填写要求一、本课程共需完成七次实验，由十五个实验项目组成。每一次实验需在备选项目中选择一个项目完成并提交一份实验报告，批改后下发的实验报告请保存起来，期末上交。二、实验报告书写要求：1. 实验目的和要求：明确实验的内容和具体任务；2. 列出源程序，备注说明程序的基本结构，包括程序中各部分的功能。 3. 说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂性，并给出计算过程。4. 实验结果与分析：给出不少于3组数据测试算法，并将每组测试数据的运行结果列出，并对调试源程序的结果进行分析，杜绝只罗列不分析；5. 讨论、建议、质疑：针对实验中碰到的问题进行组内以及组外讨论，遇到不能解决的问题时向指导老师请教，并将问题的提出以及解决的过程写入实验报告，以作为以后学习的参考。问题要具体描述，避免抽象地罗列、笼统地讨论；6. 全部文字叙述内容要求简明扼要，思路清楚；7. 实验日期、同组员姓名写清楚。 三、要求实验报告字迹工整、文字简练、数据齐全、计算正确，分析充分、具体、定量。对于抄袭实验报告和编篡原始数据的行为，一经发现，以零分处理，并根据相关条例给予处分。福建师范大学协和学院实验报告实验日期： 年 月 日 星期 组员姓名： 成绩： 实 验 一 递归与分治算法实验（一）l 项目一 快速排序 （验证实验）一、 重要的程序说明（说明程序的基本结构以及程序中各部分的功能，以伪代码和图的形式说明）二、 算法复杂性分析与计算（说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂性，并写出计算过程）三、 程序运行测试结果分析：四、程序调试过程中遇到的错误，如何讨论、有何建议与质疑五、思考题试想想，这样的排序算法有什么优势？能对所有的数据测试用例都使用这种算法吗？福建师范大学协和学院实验报告实验日期： 年 月 日 星期 组员姓名： 成绩： 实 验 一 递归与分治算法实验（一）l 项目二 合并排序 （验证实验）一、 重要的程序说明（说明程序的基本结构以及部分的功能，以伪代码和图的形式说明）二、 算法复杂性分析与计算（说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂性，并写出计算过程）三、 程序运行测试结果分析：四、程序调试过程中遇到的错误，如何讨论、有何建议与质疑五、思考题为什么合并排序是思想是基于比较类排序里面最快的，它成功的地方在哪儿？福建师范大学协和学院实验报告实验日期： 年 月 日 星期 组员姓名： 成绩： 实 验 一 递归与分治算法实验（一）l 项目三 寻找主元素 （设计实验）一、 重要的程序说明（说明程序的基本结构以及各部分的功能，以伪代码和图的形式说明）二、 算法复杂性分析与计算（说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂性，并写出计算过程）三、 程序运行测试结果分析：四、程序调试过程中遇到的错误，如何讨论、有何建议与质疑福建师范大学协和学院实验报告实验日期： 年 月 日 星期 组员姓名： 成绩： 实 验 二 递归与分治算法实验（二）l 项目四 递归求排列 （验证实验）一、 重要的程序说明（说明程序的基本结构以及程序中各部分的功能，以伪代码和图的形式说明）二、 算法复杂性分析与计算（说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂性，并写出计算过程）三、程序运行测试结果分析：四、程序调试过程中遇到的错误，如何讨论、有何建议与质疑五、思考题试想想，递归思想有什么样的优缺点，在调试过程中，随着数据量的增大，调试过程与结果有没有变化？为什么？福建师范大学协和学院实验报告实验日期： 年 月 日 星期 组员姓名： 成绩： 实 验 二 递归与分治算法实验（二）l 项目五 分治求K大元素 （设计实验）一、 重要的程序说明（说明程序的基本结构以及部分的功能，以伪代码和图的形式说明）二、 算法复杂性分析与计算（说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂性，并写出计算过程）三、程序运行测试结果分析：四、程序调试过程中遇到的错误，如何讨论、有何建议与质疑五、思考题这种求K大元素与前面学过的合并排序有无关联？仔细想一想他们的本质。福建师范大学协和学院实验报告实验日期： 年 月 日 星期 组员姓名： 成绩： 实 验 三 递归与分治算法实验（三）l 项目六 分治法求平面最近点对（验证实验）一、 重要的程序说明（说明程序的基本结构以及程序中各部分的功能，以伪代码和图的形式说明）二、 算法复杂性分析与计算（说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂性，并写出计算过程）三、程序运行测试结果分析：四、程序调试过程中遇到的错误，如何讨论、有何建议与质疑五、思考题为什么用分治法求平面最近点对时间效率会高些，这样的思想还能用于解决什么样的实际问题？试举出23个实例说明一下。福建师范大学协和学院实验报告实验日期： 年 月 日 星期 组员姓名： 成绩： 实 验 三 递归与分治算法实验（三）l 项目七 分治求棋盘覆盖问题 （设计实验）一、 重要的程序说明（说明程序的基本结构以及部分的功能，以伪代码和图的形式说明）二、 算法复杂性分析与计算（说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂性，并写出计算过程）三、程序运行测试结果分析：四、程序调试过程中遇到的错误，如何讨论、有何建议与质疑五、思考题如果参赛队伍数量不是2的整数幂，该如何调整算法。福建师范大学协和学院实验报告实验日期： 年 月 日 星期 组员姓名： 成绩： 实 验 四 贪婪算法实验l 项目八 普通背包问题（验证实验）一、 重要的程序说明（说明程序的基本结构以及程序中各部分的功能，以伪代码和图的形式说明）二、 算法复杂性分析与计算（说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂性，并写出计算过程）三、程序运行测试结果分析：四、程序调试过程中遇到的错误，如何讨论、有何建议与质疑五、思考题如果背包内物体不能分割，这样的方法还行得通吗？为什么？你能从中找出什么样的启发？福建师范大学协和学院实验报告实验日期： 年 月 日 星期 组员姓名： 成绩： 实 验 四 贪婪算法实验l 项目九 单源最短路径问题 （验证实验）一、 重要的程序说明（说明程序的基本结构以及部分的功能，以伪代码和图的形式说明）二、 算法复杂性分析与计算（说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂性，并写出计算过程）三、程序运行测试结果分析：四、程序调试过程中遇到的错误，如何讨论、有何建议与质疑五、思考题：为什么这种方法求下来的路径一定是最短？试分析一下它的正确性。福建师范大学协和学院实验报告实验日期： 年 月 日 星期 组员姓名： 成绩： 实 验 五 动态规划算法实验（一）l 项目十 动态规划求解多段图最短路径问题（验证试验）一、 重要的程序说明（说明程序的基本结构以及程序中各部分的功能，以伪代码和图的形式说明）二、 算法复杂性分析与计算（说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂性，并写出计算过程）三、程序运行测试结果分析：四、程序调试过程中遇到的错误，如何讨论、有何建议与质疑五、思考题如果最短路径不唯一，该如何输出全部符合要求的路径呢？福建师范大学协和学院实验报告实验日期： 年 月 日 星期 组员姓名： 成绩： 实 验 五 动态规划算法实验（一）项目十一 最优资源分配方案设计 （设计实验）一、 重要的程序说明（说明程序的基本结构以及部分的功能，以伪代码和图的形式说明）二、 算法复杂性分析与计算（说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂性，并写出计算过程）三、程序运行测试结果分析：四、程序调试过程中遇到的错误，如何讨论、有何建议与质疑五、思考题什么是多段图？为什么这种方法只能用于多段图？普通图能不能用动态规划来求解，为什么？福建师范大学协和学院实验报告实验日期： 年 月 日 星期 组员姓名： 成绩： 实 验 六 动态规划算法实验（二）l 项目十二 设计动态规划算法解决模式串匹配的问题（设计实验）一、 重要的程序说明（说明程序的基本结构以及程序中各部分的功能，以伪代码和图的形式说明）二、 算法复杂性分析与计算（说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂性，并写出计算过程）三、程序运行测试结果分析：四、程序调试过程中遇到的错误，如何讨论、有何建议与质疑福建师范大学协和学院实验报告实验日期： 年 月 日 星期 组员姓名： 成绩： 实 验 六 动态规划算法实验（二）项目十三 0/1背包问题 （验证实验）一、 重要的程序说明（说明程序的基本结构以及部分的功能，以伪代码和图的形式说明）二、 算法复杂性分析与计算（说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂性，并写出计算过程）三、程序运行测试结果分析：四、程序调试过程中遇到的错误，如何讨论、有何建议与质疑五、思考题：这种方法能解决所有的0/1背包问题吗？想想有什么条件限制没有？举例说明！福建师范大学协和学院实验报告实验日期： 年 月 日 星期 组员姓名： 成绩： 实 验 七 回溯算法实验l 项目十四 利用回溯思想设计一算法解决马步遍历问题（设计实验）一、 重要的程序说明（说明程序的基本结构以及程序中各部分的功能，以伪代码和图的形式说明）二、 算法复杂性分析与计算（说明程序中各部分所用的算法或原理，计算出算法时间和空间复杂性，并写出计算过程）三、程序运行测试结果分析：四、程序调试过程中遇到的错误，如何讨论、有何建议与质疑五、思考题：用回溯方法求解问题时候最大的缺点是什么？这样的问题有没有解决的办法，如果有，应该从哪方面考虑去实现？福建师范大学协和学院实验报告实验日期