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

成 绩 评 定 表学生姓名吴旭东班级学号专 业信息与计算科学课程设计题目分治法解决棋盘覆盖问题；回溯法解决数字拆分问题评语组长签字：成绩日期 20 年 月 日课程设计任务书学 院理学院专 业信息与计算科学学生姓名吴旭东班级学号课程设计题目分治法解决棋盘覆盖问题；回溯法解决数字拆分问题实践教学规定与任务:规定：1巩固和加深对基本算法理解和运用，提高综合运用课程知识进行算法设计与分析能力。2培养学生自学参照书籍，查阅手册、和文献资料能力。3通过实际课程设计，掌握运用分治法或动态规划算法，回溯法或分支限界法等办法算法基本思想，并能运用这些办法设计算法并编写程序解决实际问题。4理解与课程关于知识，能对的解释和分析实验成果。任务：按照算法设计办法和原理，设计算法，编写程序并分析成果，完毕如下内容：1. 运用分治算法求解排序问题。2. 运用回溯算法求解N后问题。工作筹划与进度安排:第12周：查阅资料。掌握算法设计思想，进行算法设计。第13周：算法实现，调试程序并进行成果分析。撰写课程设计报告，验收与答辩。指引教师： 201 年 月 日专业负责人：201 年 月 日学院教学副院长：201 年 月 日摘要算法分析是对一种算法需要多少计算时间和 存储空间作定量分析。算法（Algorithm）是解题环节，可以把算法定义成解一拟定类问题任意一种特殊办法。在 计算机科学中，算法要用 计算机算法语言描述，算法代表用计算机解一类问题精准、有效办法。分治法字面上解释是“分而治之”，就是把一种复杂问题提成两个或更多相似或相似子问题，再把子问题提成更小子问题直到最后子问题可以简朴直接求解，原问题解即子问题解合并。在一种2k*2k棋盘上，恰有一种放歌与其她方格不同，且称该棋盘为特殊棋盘。 回溯法基本做法是深度优先搜索，是一种组织得井井有条、能避免不必要重复搜索穷举式搜索算法。数字拆分问题是指将一种整数划分为各种整数之和问题。运用回溯法可以较好地解决数字拆分问题。将数字拆分然后回溯，从未解决问题。核心词：分治法，回溯法，棋盘覆盖，数字拆分目录1分治法解决期盼覆问题11.1问题描述11.2问题分析11.3算法设计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*2k棋盘分割为4个2k-1*2k-1子棋盘。由棋盘覆盖问题得知，特殊方格必位于4个较小子棋盘中，别的3个子棋盘中无特殊方格。为了将3个无特殊方格子棋盘转化为特殊棋盘可以将一种L型骨牌覆盖这3个较小棋盘会合处，因此，这3个子棋盘上被L型覆盖方格就成为给棋盘上特殊方格，从而将原问题转化为4个较小规模棋盘覆盖问题。递归使用这种分割，直至棋盘简化为1*1棋盘为止。1.3算法设计将2k x 2k棋盘，先提成相等四块子棋盘，其中特殊方格位于四个中一种，构造剩余没特殊方格三个子棋盘，将她们中也假一种方格设为特殊方格。如果是：左上子棋盘（若不存在特殊方格）-则将该子棋盘右下角那个方格假设为特殊方格右上子棋盘（若不存在特殊方格）-则将该子棋盘左下角那个方格假设为特殊方格左下子棋盘（若不存在特殊方格）-则将该子棋盘右上角那个方格假设为特殊方格右下子棋盘（若不存在特殊方格）-则将该子棋盘左上角那个方格假设为特殊方格固然上面四种，只也许且必然只有三个成立，那三个假设特殊方格刚好构成一种L型骨架，咱们可以给它们作上相似标记。这样四个子棋盘就分别都和本来大棋盘类似，咱们就可以用递归算法解决。1.4算法实现#includeint 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(drtr+s & dctc+s)chessBoard(tr，tc，dr，dc，s);elseboardtr+s-1tc+s-1=t;chessBoard(tr，tc，tr+s-1，tc+s-1，s);if(dr=tc+s)chessBoard(tr，tc+s，dr，dc，s);elseboardtr+s-1tc+s=t;chessBoard(tr，tc+s，tr+s-1，tc+s，s);if(dr=tr+s & dc=tr+s & dc=tc+s)chessBoard(tr+s，tc+s，dr，dc，s);elseboardtr+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型牌个数为（4k1）/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=22=1+1n=33=1+2 3=1+1+1 3=2+1 (可以看出为与1+2是同一种拆分，因而该式子不能算) 另一种目是可以减少不必要搜索，提高程序效率。 咱们可以将待拆分数相应途径图中路口，将可拆分数相应分叉编号，这样对于每个路口而言，它所拥有分叉号是变化，规律是：分叉起始值取决于前一次所取数，分叉终结值取决于该路口数中值。 2.3算法设计在进行算法设计时咱们必要要注意两点：一是本问题需要解决如何记录某一途径中可取数问题，为理解决这一问题，本程序加入了一种新数组b，用来记录每一步所取数。二是当某一条路走完后来，咱们必要回到某一种路口，而路口值始终保持本来数，因而在递归调用中咱们所使用实际参数应是独立。本例中使用是形式参数m，实际参数是ak，这样无论在某一级中ak值如何变化，m值是始终不变。2.4算法实现#include#includevoid 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,&n); 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&m1) total+; printf(%dt,total); for(j=1;jm;j+) printf(%d+,xj); printf(%dn,xm); else splitN(rest,m+1);/否则将剩余数进行进度为m+1拆分。 xm=0;/取消本次成果，进行下一次拆分。环境恢复，即回溯 2.5成果分析 参照文献1 张子阳.NET之美第一版机械工业出版社2 Mark MichaelisC#本质论第四版人民邮电出版社3 MoreWindows白话典型算法之七大排序第二版4 王晓东计算机算法设计与分析第四版电子工业出版社