《算法设计与分析》实验预习报告 - 副本

《《算法设计与分析》实验预习报告 - 副本》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、福建师范大学协和学院本科实验预习手册课程名称：《算法设计与分析》21实验项目实验序号项目序号实验项目名称一1快速排序2合并排序3*寻找主元素二4递归求排列5*分治找K大元素三6平面最近点对7*分治法求棋盘覆盖问题四8贪婪法求解普通背包问题9单源最短路径的dijstra算法五10多段图最短路径（动态规划）11*最优资源分配（动态规划）六12*KMP模式串匹配130/背包问题七14*回溯法求解巡游问题15回溯法求解0/1背包问题21实验一递归与分治算法实验（一）任务描述：项目一快速排序（验证实验）实验要求1．要求利用快速排序的思想完成

2、n个正整数排序，完全理解算法的思想2．了解程序的执行过程，正确分析算法的时间复杂性3．完成代码编写并调试正确，给出三组若干个整数以上的测试数据进行测试并得出正确结果。项目二合并排序（验证实验）实验要求1．要求利用合并排序的思想完成n个正整数排序，完全理解算法的思想2．了解程序的执行过程，正确分析算法的时间复杂性3．完成代码编写并调试正确，给出三组若干个整数以上的测试数据进行测试并得出正确结果。项目三寻找主元素（设计实验）问题描述：在数组中，有一半以上的元素相同，设计一个算法，以Ｏ（n）时间找到这个元素。（可用非递归，也可用递归）实

3、验要求1．设计出正确的算法，以Ｏ(n)时间找到主元素2．了解程序的执行过程，正确分析算法的时间复杂性3．，完成代码编写并调试正确，对以下三组数据（随机生成）要求测试通过：　　　21预习内容：一、实验原理和内容（每个项目分析出拟用到的算法思路）项目一：项目二：项目三：21一、项目实现的主要源代码项目一：项目二：项目三：21实验二递归与分治算法实验（二）任务描述：项目四递归求排列问题（验证实验）一、问题描述：在一个具有n个元素的数组中，运用递归生成全排列，并输出。二、实验要求1．完成程序2．了解程序的执行过程，正确分析算法的时间复杂性

4、3．对三组数据要求测试通过（每组数据用4个较大整数测试）：　　4．记录实验过程，规范完成实验报告。项目五分治找k大元素（设计实验）一、问题描述：在一个具有个元素的数组中，找出第二大元素，并计算时间杂性（要求O(n)时间）二、实验要求1．设计出正确的算法，以Ｏ(n)时间找到第二大元素2．了解程序的执行过程，正确分析算法的时间复杂性3．，完成代码编写并调试正确，对三组数据要求测试通过（第组数据不少于1000个）：　　4．记录实验过程，规范完成实验报告。21预习内容：一、实验原理和内容（每个项目分析出拟用到的算法思路）项目四：项目五：二

5、、项目拟实现的主要源代码项目四：项目五：21实验三递归与分治算法实验（三）任务描述：项目六求平面最近点对（验证实验）一、问题描述：平面内有若干点，利用分治法，以O(nlogn)时间求出平面内直线距离最近的一对点，并求出它们的距离。二、实验要求1．了解程序的执行过程，正确分析算法的时间复杂性2.完成代码编写并调试正确，对三组数据要求测试通过（每组数据点不少于1000个）：3．记录实验过程，规范完成实验报告。项目七分治法求棋盘覆盖问题（设计实验）一、问题描述：在一个2k×2k个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一

6、特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。二、实验要求1．利用分治法完成程序设计，输出棋盘覆盖矩阵2．说明算法原理以及程序的执行过程，正确分析算法的时间复杂性3．对64×64，128×128棋盘进行测试。　　4．记录实验过程，规范完成实验报告。21预习内容：一、实验原理和内容（每个项目分析出拟用到的算法思路）项目六：项目七：21一、项目拟实现的主要源代码项目六：项目七：21实验四贪婪算法实验任务描述：项目八背包问

7、题（验证实验）一、问题描述：载重量为的背包，重量为、价值为的物体，，把物体装满背包，使背包内的物体价值最大，物体可以分割的背包问题二、实验要求1．了解程序的执行过程，正确分析算法的时间复杂性2.完成代码编写并调试正确，对三组数据要求测试通过（每组物体不少于50件）：3．记录实验过程，规范完成实验报告。项目九单源最短路径问题（验证实验）一、问题描述：在下图中的有向赋权图中，求顶点到其它所有顶点的最短距离。图二、实验要求1．利用贪婪算法，完成程序设计，输出结果2．说明算法原理以及程序的执行过程，正确分析算法的时间复杂性3．对上图中的有

8、向图进行测试。　　4．记录实验过程，规范完成实验报告。21预习内容：一、实验原理和内容（每个项目分析出拟用到的算法思路）项目八：项目九：21一、项目拟实现的主要源代码项目八：项目九：21实验五动态规划算法实验（一）任务描述：项目十动态规划多段图单源