计算机算法设计及分析课程设计报告

1、.1成 绩 评 定 表学生吴旭东班级*1309010236专 业信息与计算科学课程设计题目分治法解决棋盘覆盖问题；回溯法解决数字拆分问题评语组长签字：成绩日期20 年 月 日课程设计任务书学 院理学院专 业信息与计算科学学生吴旭东班级*1309010236课程设计题目分治法解决棋盘覆盖问题；回溯法解决数字拆分问题实践教学要求与任务:要求：1稳固和加深对根本算法的理解和运用，提高综合运用课程知识进展算法设计与分析的能力。2培养学生自学参考书籍，查阅手册、和文献资料的能力。3通过实际课程设计，掌握利用分治法或动态规划算法，回溯法或分支限界法等方法的算法的根本思想，并能运用这些方法设计算法并编写程序

2、解决实际问题。4了解与课程有关的知识，能正确解释和分析实验结果。任务：按照算法设计方法和原理，设计算法，编写程序并分析结果，完成如下容：1.运用分治算法求解排序问题。2. 运用回溯算法求解N后问题。工作方案与进度安排:第12周：查阅资料。掌握算法设计思想，进展算法设计。第13周：算法实现，调试程序并进展结果分析。撰写课程设计报告，验收与辩论。指导教师： 201 年 月 日专业负责人：201 年 月 日学院教学副院长：201 年 月 日.1摘要算法分析是对一个算法需要多少计算时间和 存储空间作定量的分析。算法Algorithm是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在

3、计算机科学中，算法要用 计算机算法语言描述，算法代表用计算机解一类问题的准确、有效的方法。分治法字面上的解释是“分而治之，就是把一个复杂的问题分成两个或更多的一样或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。在一个2k*2k的棋盘上，恰有一个放歌与其他方格不同，且称该棋盘为特殊棋盘。 回溯法的根本做法是深度优先搜索，是一种组织得井井有条的、能防止不必要重复搜索的穷举式搜索算法。数字拆分问题是指将一个整数划分为多个整数之和的问题。利用回溯法可以很好地解决数字拆分问题。将数字拆分然后回溯，从未解决问题。关键词：分治法，回溯法，棋盘覆盖，数

4、字拆分目录 TOC h z t 课题,2,大课题,1 HYPERLINK l _Toc4520590881分治法解决期盼覆问题 PAGEREF _Toc452059088 h 1HYPERLINK l _Toc4520590891.1问题描述 PAGEREF _Toc452059089 h 1HYPERLINK l _Toc4520590901.2问题分析 PAGEREF _Toc452059090 h 1HYPERLINK l _Toc4520590911.3算法设计 PAGEREF _Toc452059091 h 1HYPERLINK l _Toc4520590921.4算法实现 PAGE

5、REF _Toc452059092 h 2HYPERLINK l _Toc4520590931.5结果分析 PAGEREF _Toc452059093 h 3HYPERLINK l _Toc4520590941.6算法分析 PAGEREF _Toc452059094 h 4HYPERLINK l _Toc4520590952回溯法解决数字拆分问题 PAGEREF _Toc452059095 h 6HYPERLINK l _Toc4520590962.1问题描述 PAGEREF _Toc452059096 h 6HYPERLINK l _Toc4520590972.2问题分析 PAGEREF _

6、Toc452059097 h 6HYPERLINK l _Toc4520590982.3算法设计 PAGEREF _Toc452059098 h 7HYPERLINK l _Toc4520590992.4算法实现 PAGEREF _Toc452059099 h 7HYPERLINK l _Toc4520591002.5结果分析 PAGEREF _Toc452059100 h 8HYPERLINK l _Toc452059101参考文献 PAGEREF _Toc452059101 h 9.11分治法解决期盼覆问题1.1问题描述在一个2k2kk0个方格组成的棋盘中，恰有一个方格与其他方格不同，称该

7、方格为特殊方格。显然，特殊方格在棋盘中出现的位置有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型覆盖的方格就成为给棋盘上的特殊方

8、格，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归的使用这种分割，直至棋盘简化为1*1棋盘为止。1.3算法设计将2k * 2k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格三个子棋盘，将他们中的也假一个方格设为特殊方格。如果是：左上的子棋盘假设不存在特殊方格则将该子棋盘右下角的那个方格假设为特殊方格右上的子棋盘假设不存在特殊方格则将该子棋盘左下角的那个方格假设为特殊方格左下的子棋盘假设不存在特殊方格则将该子棋盘右上角的那个方格假设为特殊方格右下的子棋盘假设不存在特殊方格则将该子棋盘左上角的那个方格假设为特殊方格当然上面四种，只可能且必定只有三个成立，那三个

9、假设的特殊方格刚好构成一个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,

10、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 inde*_*,inde*_y;coutind

11、e*_*inde*_y;chessBoard(0,0,inde*_*,inde*_y,size);for(int i=0;isize;i+)for(int j=0;jsize;j+)coutboardijt;cout0解得此递归方程可得T(k)=O4k。由于覆盖一个2k*2k棋盘所需的L型牌个数为4k1/3,故算法ChessBoard是一个在渐进意义下最优的算法.2回溯法解决数字拆分问题2.1问题描述 整数的分划问题。 如，对于正整数n=6，可以分划为：65+14+2,4+1+13+3,3+2+1,3+1+1+12+2+2,2+2+1+1,2+1+1+1+11+1+1+1+1+1+1用户从键盘

12、输入n围110。2.2问题分析很明显这是一道关于数的组合的问题，但形成组合的数是有一定的限制的。仔细分析一下题目，我们可以得到以下的结论： (1)每一组数之和必须等于n；(2)每一组数的个数是不固定的； (3)等式中后一个数的大小必定大于或等于前一个数，因为这样做的目的有两个：一是 能够防止等式的重复，例如n=22=1+1n=33=1+2 3=1+1+1 3=2+1 (可以看出为与1+2是同一种拆分，因此该式子不能算) 另一个目的是可以减少不必要的搜索，提高程序效率。我们可以将待拆分的数对应路径图中的路口，将可拆分的数对应分叉的编号，这样对于每个路口而言，它所拥有的分叉号是变化的，规律是：分叉

13、的起始值取决于前一次所取数，分叉的终止值取决于该路口数的中值。2.3算法设计在进展算法设计时我们必须要注意两点：一是本问题需要解决如何记录*一路径中可取数的问题，为了解决这一问题，本程序参加了一个新的数组b，用来记录每一步所取的数。二是当*一条路走完以后，我们必须回到*一个路口，而路口的值始终保持原来的数，因此在递归调用中我们所使用的实际参数应是独立的。本例中使用的是形式参数m，实际参数是ak，这样无论在*一级中ak的值怎样变化，m的值是始终不变的。2.4算法实现*include*includevoid splitN(int n,int m);/n是需要拆分的数，m是拆分的进度。int *10

14、24=0,total=0 ;/total用于计数拆分的方法数，*用于存储解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=*m-1) /拆分的数大于或等于前一个从而保证不重复 *m=i ;/将这个数计入结果中。 rest=n-i ;/剩下的数是n-i，如果已经没有剩下的了，并且进度(总的拆分个数)大于1，说明已经得到一个结果。 if(rest=0&m1) total+; printf(%dt,total); for(j=