计算机算法设计与分析专业课程设计.doc
《计算机算法设计与分析专业课程设计.doc》由会员分享,可在线阅读,更多相关《计算机算法设计与分析专业课程设计.doc(15页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、成 绩 评 定 表学生姓名吴旭东班级学号专 业信息与计算科学课程设计题目分治法解决棋盘覆盖问题;回溯法解决数字拆分问题评语组长签字:成绩日期 20 年 月 日课程设计任务书学 院理学院专 业信息与计算科学学生姓名吴旭东班级学号课程设计题目分治法解决棋盘覆盖问题;回溯法解决数字拆分问题实践教学规定与任务:规定:1巩固和加深对基本算法理解和运用,提高综合运用课程知识进行算法设计与分析能力。2培养学生自学参照书籍,查阅手册、和文献资料能力。3通过实际课程设计,掌握运用分治法或动态规划算法,回溯法或分支限界法等办法算法基本思想,并能运用这些办法设计算法并编写程序解决实际问题。4理解与课程关于知识,能对
2、的解释和分析实验成果。任务:按照算法设计办法和原理,设计算法,编写程序并分析成果,完毕如下内容:1. 运用分治算法求解排序问题。2. 运用回溯算法求解N后问题。工作筹划与进度安排:第12周:查阅资料。掌握算法设计思想,进行算法设计。第13周:算法实现,调试程序并进行成果分析。撰写课程设计报告,验收与答辩。指引教师: 201 年 月 日专业负责人:201 年 月 日学院教学副院长:201 年 月 日摘要算法分析是对一种算法需要多少计算时间和 存储空间作定量分析。算法(Algorithm)是解题环节,可以把算法定义成解一拟定类问题任意一种特殊办法。在 计算机科学中,算法要用 计算机算法语言描述,算
3、法代表用计算机解一类问题精准、有效办法。分治法字面上解释是“分而治之”,就是把一种复杂问题提成两个或更多相似或相似子问题,再把子问题提成更小子问题直到最后子问题可以简朴直接求解,原问题解即子问题解合并。在一种2k*2k棋盘上,恰有一种放歌与其她方格不同,且称该棋盘为特殊棋盘。 回溯法基本做法是深度优先搜索,是一种组织得井井有条、能避免不必要重复搜索穷举式搜索算法。数字拆分问题是指将一种整数划分为各种整数之和问题。运用回溯法可以较好地解决数字拆分问题。将数字拆分然后回溯,从未解决问题。核心词:分治法,回溯法,棋盘覆盖,数字拆分目录1分治法解决期盼覆问题11.1问题描述11.2问题分析11.3算法
4、设计11.4算法实现21.5成果分析31.6算法分析42回溯法解决数字拆分问题62.1问题描述62.2问题分析62.3算法设计72.4算法实现72.5成果分析8参照文献91分治法解决期盼覆问题 1.1问题描述在一种2k2k(k0)个方格构成棋盘中,恰有一种方格与其她方格不同,称该方格为特殊方格。显然,特殊方格在棋盘中浮现位置有4k中情形,因而有4k中不同棋盘,图(a)所示是k=2时16种棋盘中一种。棋盘覆盖问题规定用图(b)所示4中不同形状L型骨牌覆盖给定棋盘上除特殊方格以外所有方格,且热河亮哥L型骨牌不得重复覆盖1.2问题分析用分治方略,可以设计解决棋盘问题一种简介算法。当k0时,可以将2k
5、*2k棋盘分割为4个2k-1*2k-1子棋盘。由棋盘覆盖问题得知,特殊方格必位于4个较小子棋盘中,别的3个子棋盘中无特殊方格。为了将3个无特殊方格子棋盘转化为特殊棋盘可以将一种L型骨牌覆盖这3个较小棋盘会合处,因此,这3个子棋盘上被L型覆盖方格就成为给棋盘上特殊方格,从而将原问题转化为4个较小规模棋盘覆盖问题。递归使用这种分割,直至棋盘简化为1*1棋盘为止。1.3算法设计将2k x 2k棋盘,先提成相等四块子棋盘,其中特殊方格位于四个中一种,构造剩余没特殊方格三个子棋盘,将她们中也假一种方格设为特殊方格。如果是:左上子棋盘(若不存在特殊方格)-则将该子棋盘右下角那个方格假设为特殊方格右上子棋盘
6、(若不存在特殊方格)-则将该子棋盘左下角那个方格假设为特殊方格左下子棋盘(若不存在特殊方格)-则将该子棋盘右上角那个方格假设为特殊方格右下子棋盘(若不存在特殊方格)-则将该子棋盘左上角那个方格假设为特殊方格固然上面四种,只也许且必然只有三个成立,那三个假设特殊方格刚好构成一种L型骨架,咱们可以给它们作上相似标记。这样四个子棋盘就分别都和本来大棋盘类似,咱们就可以用递归算法解决。1.4算法实现#includeint tile=1;int board100100;void chessBoard(int tr,int tc,int dr,int dc,int size)if(size=1)retur
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 算法 设计 分析 专业课程
限制150内