计算机算法设计与分析课程设计VIP

成成 绩绩 评评 定定 表表 学生姓名吴旭东班级学号1309010236 专 业信息与计算 科学 课程设计题目 分治法解决棋盘覆 盖问题；回溯法解 决数字拆分问题 评 语 组长签字： 成绩 日期 20 年 月 日 课程设计任务书课程设计任务书 学 院理学院专 业信息与计算科学 学生姓名吴旭东班级学号 1309010236 课程设计题目分治法解决棋盘覆盖问题；回溯法解决数字拆分问题 实践教学要求与任务实践教学要求与任务: : 要求：要求： 1巩固和加深对基本算法的理解和运用，提高综合运用课程知识进行算法设计 与分析的能力。 2培养学生自学参考书籍，查阅手册、和文献资料的能力。 3通过实际课程设计，掌握利用分治法或动态规划算法，回溯法或分支限界法 等方法的算法的基本思想，并能运用这些方法设计算法并编写程序解决实际问题。 4了解与课程有关的知识，能正确解释和分析实验结果。 任务：任务： 按照算法设计方法和原理，设计算法，编写程序并分析结果，完成如下内容： 1. 运用分治算法求解排序问题。 2. 运用回溯算法求解 N 后问题。 工作计划与进度安排工作计划与进度安排: : 第 12 周：查阅资料。掌握算法设计思想，进行算法设计。 第 13 周：算法实现，调试程序并进行结果分析。 撰写课程设计报告，验收与答辩。 指导教师： 201 年 月 日 专业负责人： 201 年 月 日 学院教学副院长： 201 年 月 日 摘要 算法分析是对一个算法需要多少计算时间和 存储空间作定量的分析。算法 （Algorithm）是解题的步骤，可以把算法定义成解一确定类问题的任意一种特 殊的方法。在 计算机科学中，算法要用 计算机算法语言描述，算法代表用计 算机解一类问题的精确、有效的方法。 分治法字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更 多的相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题 可以简单的直接求解，原问题的解即子问题的解的合并。在一个 2k*2k 的棋 盘上，恰有一个放歌与其他方格不同，且称该棋盘为特殊棋盘。 回溯法的基本做法是深度优先搜索，是一种组织得井井有条的、能避免不 必要重复搜索的穷举式搜索算法。数字拆分问题是指将一个整数划分为多个整 数之和的问题。利用回溯法可以很好地解决数字拆分问题。将数字拆分然后回 溯，从未解决问题。 关键词：分治法，回溯法，棋盘覆盖，数字拆分 目录 1 1 分治法解决期盼覆问题分治法解决期盼覆问题.1 1 1.1 问题描述 .1 1.2 问题分析 .1 1.3 算法设计 .1 1.4 算法实现 .2 1.5 结果分析 .3 1.6 算法分析 .4 2 2 回溯法解决数字拆分问题回溯法解决数字拆分问题 .6 6 2.1 问题描述 .6 2.2 问题分析 .6 2.3 算法设计 .7 2.4 算法实现 .7 2.5 结果分析 .8 参考文献 .9 1 分治法解决期盼覆问题 1.1 问题描述 在一个 2k2k（k0）个方格组成的棋盘中，恰有一个方格与其他方格不 同，称该方格为特殊方格。显然，特殊方格在棋盘中出现的位置有 4k 中情形， 因而有 4k 中不同的棋盘，图（a）所示是 k=2 时 16 种棋盘中的一个。棋盘覆盖 问题要求用图（b）所示的 4 中不同形状的 L 型骨牌覆盖给定棋盘上除特殊方格 以外的所有方格，且热河亮哥 L 型骨牌不得重复覆盖 1.2 问题分析 用分治策略，可以设计解决棋盘问题的一个简介算法。 当 k0 时，可以将 2k *2k 棋盘分割为 4 个 2k-1 * 2k-1 子棋盘。由棋盘 覆盖问题得知，特殊方格必位于 4 个较小的子棋盘中，其余 3 个子棋盘中无特 殊方格。为了将 3 个无特殊方格的子棋盘转化为特殊棋盘可以将一个 L 型骨牌 覆盖这 3 个较小棋盘的会合处，所以，这 3 个子棋盘上被 L 型覆盖的方格就成 为给棋盘上的特殊方格，从而将原问题转化为 4 个较小规模的棋盘覆盖问题。 递归的使用这种分割，直至棋盘简化为 1*1 棋盘为止。 。 1.3 算法设计 将 2k x 2k 的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个 中的一个，构造剩下没特殊方格三个子棋盘，将他们中的也假一个方格设为特 殊方格。如果是： 左上的子棋盘（若不存在特殊方格）-则将该子棋盘右下角的那个方格假设 为特殊方格 右上的子棋盘（若不存在特殊方格）-则将该子棋盘左下角的那个方格假设 为特殊方格 左下的子棋盘（若不存在特殊方格）-则将该子棋盘右上角的那个方格假设 为特殊方格 右下的子棋盘（若不存在特殊方格）-则将该子棋盘左上角的那个方格假设 为特殊方格 当然上面四种，只可能且必定只有三个成立，那三个假设的特殊方格刚好构成 一个 L 型骨架，我们可以给它们作上相同的标记。这样四个子棋盘就分别都和 原来的大棋盘类似，我们就可以用递归算法解决。 。 1.4 算法实现 #include int tile=1; int board100100; void chessBoard(int tr, int tc, int dr, int dc, int size) if(size=1) return; int t=tile+; int s=size/2; if(dr=tr+s else boardtr+stc+s=t; chessBoard(tr+s, tc+s, tr+s, tc+s, s); int main() int size; coutsize; int index_x,index_y; coutindex_xindex_y; chessBoard(0,0,index_x,index_y,size); for(int i=0;isize;i+) for(int j=0;jsize;j+) coutboardijt; cout0 解得此递归方程可得 T(k) = O（4k） 。由于覆盖一个 2k *2k 棋盘所需的 L 型 牌个数为（4k 1）/3,故算法 ChessBoard 是一个在渐进意义下最优的算法. 2 回溯法解决数字拆分问题 2.1 问题描述 整数的分划问题。 如，对于正整数 n=6，可以分划为： 6 5+1 4+2, 4+1+1 3+3, 3+2+1, 3+1+1+1 2+2+2, 2+2+1+1, 2+1+1+1+1 1+1+1+1+1+1+1 用户从键盘输入 n （范围 110） 。 2.2 问题分析 很明显这是一道关于数的组合的问题，但形成组合的数是有一定的限制的。仔 细分析一下题目，我们可以得到以下的结论： (1)每一组数之和必须等于 n； (2)每一组数的个数是不固定的； (3)等式中后一个数的大小必定大于或等于前一个数，因为这样做的目的有两 个：一是 能够避免等式的重复，例如 n=2 2=1+1 n=3 3=1+2 3=1+1+1 3=2+1 ( 可以看出为与 1+2 是同一种拆分，因此该式子不能算 ) 另一个目的是可以减少不必要的搜索，提高程序效率。 我们可以将待拆分的数对应路径图中的路口，将可拆分的数对应分叉的编号， 这样对于 每个路口而言，它所拥有的分叉号是变化的，规律是：分叉的起始值取决于前 一次所取数， 分叉的终止值取决于该路口数的中值。 2.3 算法设计 在进行算法设计时我们必须要注意两点： 一是本问题需要解决如何记录某一路径中可取数的问题，为了解决这一问题， 本程序加入了一个新的数组 b，用来记录每一步所取的数。 二是当某一条路走完以后，我们必须回到某一个路口，而路口的值始终保持原 来的数， 因此在递归调用中我们所使用的实际参数应是独立的。本例中使用的 是形式参数 m，实际参数是 a k ，这样无论在某一级中 ak的值怎样变化，m 的值是始终不变的。 2.4 算法实现 #include #include void splitN(int n,int m);/n 是需要拆分的数，m 是拆分的进度。 int x1024=0,total=0 ;/total 用于计数拆分的方法数，x用于存储解 int main() int n ; printf(please input the natural number n:); scanf(%d, splitN(n,1); printf(There are %d ways to split natural number %d.n,total,n); system(PAUSE); return 0 ; void splitN(int n,int m) /n 是需要拆分的数，m 是拆分的进度。 int rest,i,j; for(i=1;i=xm-1) /拆分的数大于或等于前一个从而保证不重复 xm=i ;/将这个数计入结果中。 rest=n-i ;/剩下的数是 n-i，如果已经没有剩下的了，并且进度(总 的拆分个数)大于 1，说明已经得到一个结果。 if(rest=0 printf(%dt,total); for(j=1;jm;j+) printf(%d+,xj); printf(%dn,xm); else spli