计算机科学与技术系上机实验报告.docx
- 文档编号:17290025
- 上传时间:2023-07-23
- 格式:DOCX
- 页数:12
- 大小:20.54KB
计算机科学与技术系上机实验报告.docx
《计算机科学与技术系上机实验报告.docx》由会员分享,可在线阅读,更多相关《计算机科学与技术系上机实验报告.docx(12页珍藏版)》请在冰点文库上搜索。
计算机科学与技术系上机实验报告
贵州大学计算机科学与技术学院
计算机科学与技术系上机实验报告
课程名称:
算法设计与分析
班级:
实验日期:
YYYY-MM-DD
姓名:
学号:
指导教师:
程欣宇
实验序号:
一
实验成绩:
一、实验名称
分治算法实验-棋盘覆盖问题
二、实验目的及要求
1、熟悉递归算法编写;
2、理解分治算法的特点;
3、掌握分治算法的基本结构。
三、实验环境
VisualC++
四、实验内容
根据教材上分析的棋盘覆盖问题的求解思路,进行验证性实验;
要求完成棋盘覆盖问题的输入、分治求解、输出。
有余力的同学尝试消去递归求解。
五、算法描述及实验步骤
分治算法原理:
分治算法将大的分解成形状结构相同的子问题,并且不断递归地分解,直到子问题规模小到可以直接求解。
棋盘覆盖问题描述:
在一个2kx2k个方格组成的棋盘中恰有一个方格与其他的不同称为特殊方格,想要求利用四种L型骨牌(每个骨牌可覆盖三个方格)不相互重叠覆盖的将除了特殊方格外的其他方格覆盖。
实验步骤:
1、定义用于输入和输出的数据结构;
2、完成分治算法的编写;
3、测试记录结构;
4、有余力的同学尝试不改变输入输出结构,将递归消除,并说明能否不用栈,直接消除递归,为什么?
六、调试过程及实验结果
详细记录程序在调试过程中出现的问题及解决方法。
记录程序执行的结果。
七、总结
对上机实践结果进行分析,问题回答,上机的心得体会及改进意见。
八、附录
源程序(核心代码)清单或使用说明书,可另附纸
贵州大学计算机科学与技术学院
计算机科学与技术系上机实验报告
课程名称:
算法设计与分析
班级:
实验日期:
YYYY-MM-DD
姓名:
学号:
指导教师:
程欣宇
实验序号:
二
实验成绩:
一、实验名称
动态规划实验-滑雪问题
二、实验目的及要求
1、学会使用在线测评的算法题目评分系统;
2、通过直观的应用问题,加深对动态规划算法的理解;
三、实验环境
任意C或C++编写调试工具,北京大学ICPC在线测评系统POJ
四、实验内容
1、找到题号为1088的题目-滑雪,阅读题目,建立其最优解的递归表达式;
3、使用备忘录式的动态规划算法,实现本题;
4、进行简单测试,完成之后提交到POJ系统。
五、算法描述及实验步骤
动态规划算法原理:
分治算法将大的问题变成小的问题来解决,但是如果划分过程中出现重叠子问题,就可能导致大量的重复计算。
为了避免这些重复的计算,可以考虑的一个办法就是动态规划算法。
为了使用动态规划算法,问题还必须具备最优子结构,即问题的最优解包含了子问题的最优解。
滑雪问题描述:
Michael喜欢滑雪百这并不奇怪,因为滑雪的确很刺激。
可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。
Michael想知道载一个区域中最长底滑坡。
区域由一个二维数组给出。
数组的每个数字代表点的高度。
下面是一个例子
12345
161718196
152425207
142322218
131211109
一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度减小。
在上面的例子中,一条可滑行的滑坡为24-17-16-1。
当然25-24-23-...-3-2-1更长。
事实上,这是最长的一条。
Input
输入的第一行表示区域的行数R和列数C(1<=R,C<=100)。
下面是R行,每行有C个整数,代表高度h,0<=h<=10000。
Output
输出最长区域的长度。
实验步骤:
1、建立滑雪问题的解的递归表达式
请建立!
2、构造算法框架
请构造!
3、分析出算法复杂度
请分析!
六、调试过程及实验结果
详细记录程序在调试过程中出现的问题及解决方法。
记录程序执行的结果。
七、总结
对上机实践结果进行分析,问题回答,上机的心得体会及改进意见。
八、附录
源程序(核心代码)清单或使用说明书,可另附纸
贵州大学计算机科学与技术学院
计算机科学与技术系上机实验报告
课程名称:
算法设计与分析
班级:
实验日期:
YYYY-MM-DD
姓名:
学号:
指导教师:
程欣宇
实验序号:
三
实验成绩:
一、实验名称
贪心算法实验-包装问题
二、实验目的及要求
1、使用在线测评的算法题目评分系统来测试所写代码;
2、通过直观的应用问题,加深对贪心算法的理解;
三、实验环境
任意C或C++编写调试工具,北京大学ICPC在线测评系统POJ
四、实验内容
1、登陆POJ系统,找到题号为1017的题目-包装;
2、阅读题目,分析出求解该问题的思路;
3、使用贪心算法,实现本题;
4、进行简单测试,完成之后提交到POJ系统。
五、算法描述及实验步骤
贪心算法原理:
贪心算法通过一系列的选择来达到子问题的解。
它所做的每一步选择都是当前状态下局部最好选择,即贪心选择。
这种启发式的策略虽不能总是奏效,但大多数情况下确能达到预期目的,得到最优解。
要使用贪心算法,问题必须具备两个基本要素。
贪心选择性质和最优子结构性质。
贪心选择性质指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。
通常采用自顶向下的方式进行,这样每做一次贪心选择就将所求问题化为规模更小的子问题。
当然,前提是所求问题本身的最优解包含其子问题的最优解,即具有最优子结构性质。
包装问题描述:
有一个工厂生产一种长宽为1*1、2*2、3*3、4*4、5*5、6*6的产品,这些产品交付到客户手中都是用6*6的包裹包装。
因为费用问题,工厂希望使用最少的包裹寄送给订购货物的客户。
一个好的程序能够根据订单找到最少需要的包裹数量。
你被要求写这样一个程序。
输入
输入文件由若干行组成,每一行市一个订单,所有的订单都由6个整数组成,分别对应1*1产品到6*6产品的需求量。
输入文件的最后一行由6个0组成。
输出
输出文件的每一行对应输入文件的每一行,它包含了最少需要的包裹数量。
输入示例
004001//4个3*3的产品和1个6*6的产品
751000//7个1*1的产品、5个2*2的产品和1个3*3的产品
000000//0结束
输出示例
2//至少需要2个包裹
1//至少需要1个包裹
实验步骤:
1、建立包装问题的解题思路
请建立!
2、构造算法框架
请构造!
3、分析出算法复杂度
请分析!
六、调试过程及实验结果
详细记录程序在调试过程中出现的问题及解决方法。
记录程序执行的结果。
七、总结
对上机实践结果进行分析,问题回答,上机的心得体会及改进意见。
八、附录
源程序(核心代码)清单或使用说明书,可另附纸
贵州大学计算机科学与技术学院
计算机科学与技术系上机实验报告
课程名称:
算法设计与分析
班级:
实验日期:
YYYY-MM-DD
姓名:
学号:
指导教师:
程欣宇
实验序号:
四
实验成绩:
一、实验名称
回溯算法实验-频道分配问题
二、实验目的及要求
1、使用在线测评的算法题目评分系统来测试所写代码;
2、通过直观的应用问题,加深对回溯算法的理解;
三、实验环境
任意C或C++编写调试工具,北京大学ICPC在线测评系统POJ
四、实验内容
1、登陆POJ系统,找到题号为1129的题目-频道分配;
2、阅读题目,分析出求解该问题的思路;
3、使用回溯算法,实现本题;
4、进行简单测试,完成之后提交到POJ系统。
五、算法描述及实验步骤
回溯算法原理:
回溯法是一个既带有系统性又带有跳跃性的搜索算法,用它可以系统地搜索一个问题的所有解或任一解。
它在问题的解空间树中,按深度优先的策略,从根结点出发搜索解空间树。
算法搜索至解空间树的任一结点时,先判断该结点是否包含问题的解。
如果肯定不包含,则跳过对以该结点为根的子树的搜索,逐层向其祖先结点回溯。
否则,进入该子树,继续按深度优先策略搜索。
回溯法求问题的所有解时,要回溯到根,且根结点的所有子树都已经被搜索遍才结束。
回溯法求问题的一个解时,只要搜索到问题的一个解就可结束。
频道分配问题描述:
当一个无线站广播覆盖一个非常大的区域时,需要使用转发器转发增强信号。
然而,每个转发器使用的频道数必须仔细的选择,以使得相邻的转发器之间不会相互干扰。
它们相互不干扰的条件是相邻的转发器使用不同的频道。
因为无线频谱是非常稀有的资源,因此,所给的转发器网络使用的频道数量必须最小化。
你需要写一个程序读出转发器网络的描述,然后算出最小需要的频道数量。
注意:
邻接关系具有对称性,如果A邻接B,则B邻接A。
另外,因为转发器网络是平面的,所以通道不会交叉。
输入
输入由若干转发器网络的地图组成。
每个地图的第一个行是转发器数量(1至26,用0表示输入结束)。
每个转发器由字母A至Z标识,每行列出和一个转发器邻接的相邻转发器。
输出
对于每一个转发器网络地图,输出最少占用的频道数量(注意单复数)。
例子输入
2
A:
B:
4
A:
BC
B:
ACD
C:
ABD
D:
BC
4
A:
BCD
B:
ACD
C:
ABD
D:
ABC
0
例子输出
1channelneeded.
3channelsneeded.
4channelsneeded.
实验步骤:
1、建立频道分配问题的解题思路
请建立!
2、构造算法框架
请构造!
3、分析出算法复杂度
请分析!
六、调试过程及实验结果
详细记录程序在调试过程中出现的问题及解决方法。
记录程序执行的结果。
七、总结
对上机实践结果进行分析,问题回答,上机的心得体会及改进意见。
八、附录
源程序(核心代码)清单或使用说明书,可另附纸
贵州大学计算机科学与技术学院
计算机科学与技术系上机实验报告
课程名称:
算法设计与分析
班级:
实验日期:
YYYY-MM-DD
姓名:
学号:
指导教师:
程欣宇
实验序号:
五
实验成绩:
一、实验名称
分支限界法实验-抓住那头奶牛
二、实验目的及要求
1、使用在线测评的算法题目评分系统来测试所写代码;
2、通过直观的应用问题,加深对分支限界算法的理解;
三、实验环境
任意C或C++编写调试工具,北京大学ICPC在线测评系统POJ
四、实验内容
1、登陆POJ系统,找到题号为3278的题目-抓住那头奶牛;
2、阅读题目,分析出求解该问题的思路;
3、使用分支限界算法,实现本题;
4、进行简单测试,完成之后提交到POJ系统。
五、算法描述及实验步骤
分支界限算法原理:
分支界限法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。
问题的解空间树是表示问题解空间的一棵有序树。
在搜索问题的解空间树时,分支界限法与回溯法的主要区别在于它们对当前扩展结点所采用的扩展方式不同。
在分支界限法中,每一个活结点只有一次机会扩展结点。
活结点一旦成为扩展结点,便一次性产生其所有儿子结点。
在这些儿子结点中,舍弃掉不可行解或导致非最优解的儿子结点,其余儿子结点被加入活结点表中。
此后,从活结点表中取下一结点成为当前扩展结点,并重复此结点扩展过程,直到找出所求解或活结点表为空时为止。
抓奶牛问题描述:
农夫约翰被告知逃跑的奶牛的位置,并且要求立即去抓住她。
约翰开始的位置在数轴上位置N(0≤N≤100,000),而奶牛的位置在同样一个数轴上的K(0≤K≤100,000)。
约翰有两种移动方式:
步行和瞬间移动。
*步行:
从任意一点X移动到X+1或者X-1,花一分钟。
*瞬间移动:
从任意一点X移动到2X,花一分钟。
如果奶牛没有意识到被抓捕,也就不会移动,最短时间是多少?
农夫会抓到奶牛?
输入
一行:
用空格分开的两个整数:
N和K
输出
一行:
农夫抓到奶牛需要的最少分钟数。
例子输入
517
例子输出
4
实验步骤:
1、建立抓奶牛问题的解题思路
请建立!
2、构造算法框架
请构造!
3、分析出算法复杂度
请分析!
六、调试过程及实验结果
详细记录程序在调试过程中出现的问题及解决方法。
记录程序执行的结果。
七、总结
对上机实践结果进行分析,问题回答,上机的心得体会及改进意见。
八、附录
源程序(核心代码)清单或使用说明书,可另附纸
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机科学 技术 上机 实验 报告