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

上传人:xins****2008 文档编号:201317582 上传时间:2023-04-19 格式:DOC 页数:22 大小:164KB
收藏 版权申诉 举报 下载
《算法设计与分析》实验预习报告 - 副本_第1页
第1页 / 共22页
《算法设计与分析》实验预习报告 - 副本_第2页
第2页 / 共22页
《算法设计与分析》实验预习报告 - 副本_第3页
第3页 / 共22页
资源描述:

《《算法设计与分析》实验预习报告 - 副本》由会员分享,可在线阅读,更多相关《《算法设计与分析》实验预习报告 - 副本(22页珍藏版)》请在装配图网上搜索。

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

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

3、,对以下三组数据(随机生成)要求测试通过:预习内容:一、 实验原理和内容(每个项目分析出拟用到的算法思路)项目一:项目二:项目三:二、 项目实现的主要源代码项目一:项目二:项目三:实 验 二 递归与分治算法实验(二)任务描述:项目四 递归求排列问题 (验证实验)一、问题描述:在一个具有n个元素的数组中,运用递归生成全排列,并输出。二、实验要求1完成程序2了解程序的执行过程,正确分析算法的时间复杂性3对三组数据要求测试通过(每组数据用4个较大整数测试):4记录实验过程,规范完成实验报告。项目五 分治找k大元素(设计实验)一、问题描述:在一个具有个元素的数组中,找出第二大元素,并计算时间杂性(要求

4、O(n)时间)二、实验要求1设计出正确的算法,以(n)时间找到第二大元素2了解程序的执行过程,正确分析算法的时间复杂性3,完成代码编写并调试正确,对三组数据要求测试通过(第组数据不少于1000个):4记录实验过程,规范完成实验报告。预习内容:一、 实验原理和内容(每个项目分析出拟用到的算法思路)项目四:项目五:二、 项目拟实现的主要源代码项目四:项目五: 实 验 三 递归与分治算法实验(三)任务描述:项目六 求平面最近点对(验证实验)一、问题描述:平面内有若干点,利用分治法,以O(nlogn)时间求出平面内直线距离最近的一对点,并求出它们的距离。二、实验要求1了解程序的执行过程,正确分析算法的

5、时间复杂性2. 完成代码编写并调试正确,对三组数据要求测试通过(每组数据点不少于1000个):3记录实验过程,规范完成实验报告。项目七 分治法求棋盘覆盖问题 (设计实验)一、问题描述:在一个2k2k 个方格组成的棋盘中,恰有一个方格与其他方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。在棋盘覆盖问题中,要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。二、实验要求1利用分治法完成程序设计,输出棋盘覆盖矩阵2说明算法原理以及程序的执行过程,正确分析算法的时间复杂性3对6464,128128棋盘进行测试。4记录实验过程,规范完成实

6、验报告。预习内容:一、 实验原理和内容(每个项目分析出拟用到的算法思路)项目六:项目七:二、 项目拟实现的主要源代码项目六:项目七: 实 验 四 贪婪算法实验任务描述:项目八 背包问题(验证实验)一、问题描述:载重量为的背包,重量为、价值为的物体,把物体装满背包,使背包内的物体价值最大,物体可以分割的背包问题二、实验要求1了解程序的执行过程,正确分析算法的时间复杂性2. 完成代码编写并调试正确,对三组数据要求测试通过(每组物体不少于50件):3记录实验过程,规范完成实验报告。 项目九 单源最短路径问题 (验证实验)一、问题描述:在下图中的有向赋权图中,求顶点到其它所有顶点的最短距离。图二、实验

7、要求1利用贪婪算法,完成程序设计,输出结果2说明算法原理以及程序的执行过程,正确分析算法的时间复杂性3对上图中的有向图进行测试。4记录实验过程,规范完成实验报告。预习内容:一、 实验原理和内容(每个项目分析出拟用到的算法思路)项目八:项目九:二、 项目拟实现的主要源代码项目八:项目九: 实 验 五 动态规划算法实验(一)任务描述:项目十 动态规划多段图单源最短路径(验证实验)一、问题描述:利用动态规划求解图所示的0到9最短距离及路径。二、实验要求1了解程序的执行过程,正确分析算法的时间复杂性2. 完成代码编写并调试正确,对上图数据要求测试通过3记录实验过程,规范完成实验报告。项目十一 资源最优

8、分配问题 (设计实验)一、问题描述:现有5个份额的资源,分配给3个工程,其利润函数如下: x 1 2 3 4 5713 16 17 19612 14 16 18518 19 20 22设计出合理的算法,求资源的最优分配方案。二、实验要求1说明算法原理以及程序的执行过程,正确分析算法的时间复杂性2对上述中的实例进行测试。3. 记录实验过程,规范完成实验报告。预习内容:一、 实验原理和内容(每个项目分析出拟用到的算法思路)项目十:项目十一:二、 项目拟实现的主要源代码项目十:项目十一: 实 验 六 动态规划算法实验(二)任务描述:项目十二 模式串匹配问题 (设计实验)一、问题描述:利用动态规划的方

9、法,设计出一算法,求出,的最长公共子序列。二、实验要求1说明算法原理以及程序的执行过程,正确分析算法的时间复杂性2写出源码,对上述中的实例进行测试。3记录实验过程,规范完成实验报告。项目十三 0/1背包问题 (验证实验)一、问题描述:有6个物体,其重量分别为5,3,7,2,3,4,价值分别为3,6,5,4,3,4,背包的载重量为15,利用动态规划的方法,求出在背包不超载的情况下,使背包内价值量最大的装载方法(物体不可分割)。二、实验要求1说明算法原理以及程序的执行过程,正确分析算法的时间复杂性2写出源码,对上述中的实例进行测试。3记录实验过程,规范完成实验报告。预习内容:一、 实验原理和内容(

10、每个项目分析出拟用到的算法思路)项目十二:项目十三:二、 项目拟实现的主要源代码项目十二:项目十三:实 验 七 回溯算法实验任务描述:项目十四 回溯法解决马步遍历问题(设计实验)一、问题描述:设计一算法,求解国际象棋中的马的周游问题:给定一88的棋盘,马从棋盘的某个位置出发,经过棋盘中的每一个方格恰好一次。(只需求一可行解)二、实验要求1了解程序的执行过程,正确分析算法的时间复杂性2. 完成代码编写并调试正确,对88棋盘数据要求测试通过3记录实验过程,规范完成实验报告。 项目十五 回溯法求解0/1背包问题 (验证实验)一、问题描述:给定背包的载重量M20,有6个物体,价值分别为11,8,15,18,12,6,重量分别为5,3,2,10,4,2。利用回溯法求解上述问题。二、实验要求1说明算法原理以及程序的执行过程,正确分析算法的时间复杂性2对上述中的实例进行测试。3记录实验过程,规范完成实验报告。预习内容:一、 实验原理和内容(每个项目分析出拟用到的算法思路)项目十四:项目十五:二、 项目拟实现的主要源代码项目十四:项目十五:21

展开阅读全文
温馨提示:
1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

copyright@ 2023-2025  zhuangpeitu.com 装配图网版权所有   联系电话:18123376007

备案号:ICP2024067431-1 川公网安备51140202000466号


本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知装配图网,我们立即给予删除!