实验任务指导书(实验报告版)

《实验任务指导书(实验报告版)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、贵州大学计算机科学与技术学院计算机科学与技术系上机实验报告课程名称：算法设计与分析班级：实验日期：YYYY-MM-DD姓名：学号：指导教师：程欣宇实验序号：一实验成绩：一、实验名称分治算法实验-棋盘覆盖问题二、实验目的及要求1、熟悉递归算法编写；2、理解分治算法的特点；3、掌握分治算法的基本结构。三、实验环境VisualC++四、实验内容根据教材上分析的棋盘覆盖问题的求解思路，进行验证性实验；要求完成棋盘覆盖问题的输入、分治求解、输出。有余力的同学尝试消去递归求解。五、算法描述及实验步骤分治算法原理：分治算法将大的分

2、解成形状结构相同的子问题，并且不断递归地分解，直到子问题规模小到可以直接求解。棋盘覆盖问题描述：在一个2kx2k个方格组成的棋盘中恰有一个方格与其他的不同称为特殊方格，想要求利用四种L型骨牌（每个骨牌可覆盖三个方格）不相互重叠覆盖的将除了特殊方格外的其他方格覆盖。实验步骤：1、定义用于输入和输出的数据结构；2、完成分治算法的编写；3、测试记录结构；4、有余力的同学尝试不改变输入输出结构，将递归消除，并说明能否不用栈，直接消除递归，为什么？六、调试过程及实验结果详细记录程序在调试过程中出现的问题及解决方法。记录程序执行

3、的结果。七、总结对上机实践结果进行分析，问题回答，上机的心得体会及改进意见。八、附录源程序（核心代码）清单或使用说明书，可另附纸贵州大学计算机科学与技术学院计算机科学与技术系上机实验报告课程名称：算法设计与分析班级：实验日期：YYYY-MM-DD姓名：学号：指导教师：程欣宇实验序号：二实验成绩：一、实验名称动态规划实验-滑雪问题二、实验目的及要求1、学会使用在线测评的算法题目评分系统；2、通过直观的应用问题，加深对动态规划算法的理解；三、实验环境任意C或C++编写调试工具，北京大学ICPC在线测评系统POJ四、实验内

4、容1、找到题号为1088的题目-滑雪,阅读题目，建立其最优解的递归表达式；3、使用备忘录式的动态规划算法，实现本题；4、进行简单测试，完成之后提交到POJ系统。五、算法描述及实验步骤动态规划算法原理：分治算法将大的问题变成小的问题来解决，但是如果划分过程中出现重叠子问题，就可能导致大量的重复计算。为了避免这些重复的计算，可以考虑的一个办法就是动态规划算法。为了使用动态规划算法，问题还必须具备最优子结构，即问题的最优解包含了子问题的最优解。滑雪问题描述：Michael喜欢滑雪百这并不奇怪，因为滑雪的确很刺激。可是为了获

5、得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子12345161718196152425207142322218131211109一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。Input输入的第一行表示区域的行数R和列数C(1<

6、=R,C<=100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。Output输出最长区域的长度。实验步骤：1、建立滑雪问题的解的递归表达式请建立！2、构造算法框架请构造！3、分析出算法复杂度请分析！六、调试过程及实验结果详细记录程序在调试过程中出现的问题及解决方法。记录程序执行的结果。七、总结对上机实践结果进行分析，问题回答，上机的心得体会及改进意见。八、附录源程序（核心代码）清单或使用说明书，可另附纸贵州大学计算机科学与技术学院计算机科学与技术系上机实验报告课程名称：算法设计与分析班级：实验日

7、期：YYYY-MM-DD姓名：学号：指导教师：程欣宇实验序号：三实验成绩：一、实验名称贪心算法实验-包装问题二、实验目的及要求1、使用在线测评的算法题目评分系统来测试所写代码；2、通过直观的应用问题，加深对贪心算法的理解；三、实验环境任意C或C++编写调试工具，北京大学ICPC在线测评系统POJ四、实验内容1、登陆POJ系统，找到题号为1017的题目-包装；2、阅读题目，分析出求解该问题的思路；3、使用贪心算法，实现本题；4、进行简单测试，完成之后提交到POJ系统。五、算法描述及实验步骤贪心算法原理：贪心算法通过一系

8、列的选择来达到子问题的解。它所做的每一步选择都是当前状态下局部最好选择，即贪心选择。这种启发式的策略虽不能总是奏效，但大多数情况下确能达到预期目的，得到最优解。要使用贪心算法，问题必须具备两个基本要素。贪心选择性质和最优子结构性质。贪心选择性质指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。通常采用自顶向下的方式进行，这样