福建师范大学协和学院
本科实验预习手册
课程名称：
《算法设计与分析》
f实验项目
实验序号
项目序号
实验项目名称
1一234二56三78四910五1112六1314七15
快速排序合并排序寻找主元素递归求排列分治找K大元素平面最近点对分治法求棋盘覆盖问题贪婪法求解普通背包问题单源最短路径的dijstra算法多段图最短路径（动态规划）最优资源分配（动态规划）KMP模式串匹配0背包问题回溯法求解巡游问题回溯法求解01背包问题
1
f实验一任务描述：
项目一快速排序（验证实验）实验要求
递归与分治算法实验（一）
1．要求利用快速排序的思想完成
个正整数排序，完全理解算法的思想2．了解程序的执行过程，正确分析算法的时间复杂性3．完成代码编写并调试正确，给出三组若干个整数以上的测试数据进行测试并得出正确结果。
项目二合并排序（验证实验）实验要求1．要求利用合并排序的思想完成
个正整数排序，完全理解算法的思想2．了解程序的执行过程，正确分析算法的时间复杂性3．完成代码编写并调试正确，给出三组若干个整数以上的测试数据进行测试并得出正确结果。项目三寻找主元素（设计实验）问题描述：在数组中，有一半以上的元素相同，设计一个算法，以Ｏ（
）时间找到这个元素。（可用非递归，也可用递归）实验要求1．设计出正确的算法，以Ｏ
时间找到主元素2．了解程序的执行过程，正确分析算法的时间复杂性3．，完成代码编写并调试正确，对以下三组数据（随机生成）要求测试通过：
2
f预习内容：
一、实验原理和内容（每个项目分析出拟用到的算法思路）项目一：
项目二：
项目三：
3
f二、项目实现的主要源代码项目一：
项目二：
项目三：
4
f实验二任务描述：
递归与分治算法实验（二）
项目四递归求排列问题（验证实验）一、问题描述：在一个具有
个元素的数组中，运用递归生成全排列，并输出。二、实验要求1．完成程序2．了解程序的执行过程，正确分析算法的时间复杂性3．对三组数据要求测试通过（每组数据用4个较大整数测试）：4．记录实验过程，规范完成实验报告。
项目五分治找k大元素（设计实验）一、问题描述：在一个具有个元素的数组中，找出第二大元素，并计算时间杂性（要求O
时间）二、实验要求1．设计出正确的算法，以Ｏ
时间找到第二大元素2．了解程序的执行过程，正确分析算法的时间复杂性3．，完成代码编写并调试正确，对三组数据要求测试通过（第组数据不少于1000个）r