必威体育精装版算法设计与分析.doc

精品 Word 可修改 欢迎下载 必威体育精装版 精品 Word 欢迎下载 可修改 精品 Word 可修改 欢迎下载 算法分析与设计 2021~2021年度 第1学期 课程学习报告 院系： 学号： 姓名： 任课教师： 成绩评定： 完成日期：2022年 12月 30 日 递归与分治 在任何可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，解题所需要的计算时间也就越少从而比较容易处理。要想直接解决一个较大的问题，有时是相当困难的。分治法的设计思想是，讲一个难以解决的大问题，分割成规模较小的相同问题，以便各个击破，分而治之。如果原问题可分割成k个子问题，1＜k≤n，且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分之手段，可以使子问题与原问题的类型一致而其规模却不断缩小，最终使子问题缩小到很容易求出其解。由此自然导出递归算法。并以其为基础，可以产生了许多高效算法。 1.1递归的概念 直接或间接的调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。在计算机算法设计与分析中，递归技术是十分有用的。使用递归技术往往使函数的定义和算法的描述简洁且易于理解。 将正整数n表示成一系列正整数之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。 例如正整数6有如下11种不同的划分： 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。 在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。 (1) q(n,1)=1,n?1; 当最大加数n1不大于1时，任何正整数n只有一种划分形式， 即 (2) q(n,m)=q(n,n),m≥n; 最大加数n1实际上不能大于n。因此，q(1,m)=1。 (3) q(n,n)=1+q(n,n-1); 正整数n的划分由n1=n的划分和n1≤n-1的划分组成。 (4) q(n,m)=q(n,m-1)+q(n-m,m),nm1; 正整数n的最大加数n1不大于m的划分由n1=m的划分和 n1≤n-1 的划分组成。 在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。 据此，设计计算去q（n，m）的递归算法如下。 public static int q(int n ,int m ) { if((n1)||(m1)) return 0; if((n==1)||(m==1)) return 1; if(nm) return q(n,n); If(n==m) return q(n,m- 1)+1; return q(n,m-1)+q(n-m,m) ; } 优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。 缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 1.2分治法的基本思想 分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相同。人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。 分治法所能解决的问题一般具有以下几个特征： 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质 利用该问题分解出的子问题的解可以合并为该问题的解； 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。 分治法的基本步骤 divide-and-conquer(P) { if ( | P | = n0) adhoc(P); //解决小规模的问题 d