计算机算法设计与分析课程设计剖析.doc

成 绩 评 定 表 学生姓名 吴旭东 班级学号 1309010236 专 业 信息与计算科学 课程设计题目 分治法解决棋盘覆盖问题；回溯法解决数字拆分 评 语 组长签字： 成绩 日期 20 年 月 日  课程设计任务书 学 院 理学院 专 业 信息与计算科学 学生姓名 吴旭东 班级学号 1309010236 课程设计题目 分治法解决棋盘覆盖问题；回溯法解决数字拆分 实践教学要求与任务: 要求： 1．巩固和加深对基本算法的理解和运用，提高综合运用课程知识进行算法设计与分析的能力。 2．培养学生自学参考书籍，查阅手册、和文献资料的能力。 3．通过实际课程设计，掌握利用分治法或动态规划算法，回溯法或分支限界法等方法的算法的基本思想，并能运用这些方法设计算法并编写程序解决实际问题。 4．了解与课程有关的知识，能正确解释和分析实验结果。 任务： 按照算法设计方法和原理，设计算法，编写程序并分析结果，完成如下内容： 1. 运用分治算法求解排序问题。 2. 运用回溯算法求解N后问题。 工作计划与进度安排: 第12周：查阅资料。掌握算法设计思想，进行算法设计。 第13周：算法实现，调试程序并进行结果分析。 撰写课程设计报告，验收与答辩。 指导教师： 201 年 月 日 专业负责人： 201 年 月 日 学院教学副院长： 201 年 月 日 摘要 算法分析是对一个算法需要多少计算时间和 存储空间作定量的分析。算法（Algorithm）是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在 计算机科学中，算法要用 计算机算法语言描述，算法代表用计算机解一类问题的精确、有效的方法。 字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并在一个 回溯法的基本做法是深度优先有哪些信誉好的足球投注网站，是一种组织得井井有条的、能避免不必要重复有哪些信誉好的足球投注网站的穷举式有哪些信誉好的足球投注网站算法。数字拆分问题是指将一个整数划分为多个整数之和的问题 目录 1分治法解决期盼覆问题 1 1.1问题描述 1 1.2问题分析 1 1.3算法设计 1 1.4算法实现 2 1.5结果分析 3 1.6算法分析 4 2回溯法解决数字拆分问题 6 2.1问题描述 6 2.2问题分析 6 2.3算法设计 7 2.4算法实现 7 2.5结果分析 8 参考文献 9 1分治法解决期盼覆问题 1.1问题描述 在一个2k×2k（k≥0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。显然，特殊方格在棋盘中出现的位置有4k中情形，因而有4k中不同的棋盘，图（a）所示是k=2时16种棋盘中的一个。棋盘覆盖问题要求用图（b）所示的4中不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且热河亮哥L型骨牌不得重复覆盖 1.2问题分析 用分治策略，可以设计解决棋盘问题的一个简介算法。 。 1.3算法设计 将2^k x 2^k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格三个子棋盘，将他们中的也假一个方格设为特殊方格。如果是：左上的子棋盘（若不存在特殊方格）----则将该子棋盘右下角的那个方格假设为特殊方格右上的子棋盘（若不存在特殊方格）----则将该子棋盘左下角的那个方格假设为特殊方格左下的子棋盘（若不存在特殊方格）----则将该子棋盘右上角的那个方格假设为特殊方格右下的子棋盘（若不存在特殊方格）----则将该子棋盘左上角的那个方格假设为特殊方格 当然上面四种，只可能且必定只有三个成立，那三个假设的特殊方格刚好构成一个L型骨架，我们可以给它们作上相同的标记。这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归算法解决。 1.4算法实现 #includeiostream.h int tile=1; int board[100][100]; void chessBoard(int tr, int tc, int dr, int dc, int size) { if(size==1) return; int t=tile++; int s=size/2; if(drtr+s dctc+s) chessBoard(tr, tc, dr, dc, s); else { board[tr+s-1][tc+s-1]=t; chessBoard(tr, tc, tr+s-1, tc+s-1, s); } if(drtr+s dc=tc+s) che