第四章 递归和分治

第三章-递归1．统计二叉树高度递归转非递归2．层次遍历递归转非递归，时空复杂度3．求树的叶节点数递归转非递归4．最后三位010（习题3.6）5．第一次010（习题3.7）6．Fabonacci递归转非递归7．欧几里得算法8．递归实现二分检索9．Fabonacci非递归（2）10.补充：证明Tn=T(n/9)+ T(63n/72)+C1n11．MAXMIN递归转非递归第四章-分治1. 稳定快排2. 完全三叉树的成功检索效率（P76有二叉树的）3. 求解递归关系式（习题4.2）4. 二分检索（递归）（习题4.3）5. MAXMIN递归转非递归（习题4.8）（第三章11）6. 稳定快排（习题4.13）7. 补充：证明E=I+2n第五章-贪心1.期限作业2.01背包（习题5.3）3.集合覆盖（习题5.4）4.结点覆盖（习题5.5）5.期限作业（习题5.8）6.最优三元归并树（习题5.12）7.在假定图用邻接表来表示的情况下重写Prim，计算复杂度（习题5.14）8.补充：用集合算法，求图是否有回路9.补充：用集合算法，求图是否为连通图第六章-动规1.最优二分检索树2.三级系统，成本与可靠性3.货郎担问题4.流水线调度问题P150例题6.19 第七章-基本检索与周游设计算法，输出遍历的二叉树第八章-回溯N的R排列分派问题，成本最小子集合数的状态空间树NQ的状态空间树第九章-分枝限界LCKNAP（LC的背包问题）第十章-NP集团最优化问题可约化为集团的判定问题集团判定为NP难问题P问题、NP问题、NP完全问题、CNF 可满足性问题之间的关系【3.1】（1）试给出统计二叉树高度的递归算法；（2）对该递归算法用消除递归法改写递归：procedure TreeDeep (T)if T = null then deep <- 0else ldeep <- TreeDeep(T, lchild)rdeep <- TreeDeep(T, rchild)deep <- Max(ldeep, rdeep)+1endifreturn (deep)end TreeDeep非递归：Procedure TreeDeep(T)STACK(1:8n); top <- 0L1: if T = null then deep <- 0 // r2 else top <- top+1; STACK(top) <- T // r3top <- top+1; STACK(top) <- ldeep // r3top <- top+1; STACK(top) <- rdeep // r3top <- top+1; STACK(top) <- 2 // r4T <- T.lchild // r5goto L1L2: ldeep <- STACK(top); top <- top-1 // r7 top <- top+1; STACK(top) <- T // r3top <- top+1; STACK(top) <- ldeep // r3top <- top+1; STACK(top) <- rdeep // r3top <- top+1; STACK(top) <- 3 // r4T <- T.rchild // r5goto L1 // r6L3: rdeep <- STACK(top); top <- top-1 // r7 deep <- Max(ldeep, rdeep)+1endifif top = 0 then return (deep) // r8else addr <- STACK(top); top <- top-1 // r10rdeep <- STACK(top); top <- top-1 // r11ldeep <- STACK(top); top <- top-1 // r11T <- STACK(top); top <- top-1 // r11top <- top+1; STACK(top) <- deep // r12if addr = 2; then goto L2 endif // r13if addr = 3; then goto L3 endif // r13 endifend TreeDeep【3.2】三、试写出栈层次遍历一颗二叉树的算法，并给出时空复杂度procedure LEVELORDER(T)if T ≠ null thenInit(Q) //初始化队列Q为空call ADDQ(T,Q)loopif EMPTY(Q) then return endifcall DELETEQ(u,Q)print (u)if u.lchild ≠ null thencall ADDQ(u.lchild, Q)endifif u.rchild ≠ null thencall ADDR(u.rchild, Q)endifrepeatendifend LEVELORDER时间复杂度Θ(n) 空间复杂度Θ(n)【3.3】设有如下递归程序，改为非递归，求叶节点个数procedure leaf(T)if T = null then res = 0else if T是叶子then res = 1else lL = leaf(T.lchild)lR = leaf(T.rchild)res = lL+lRendifendifreturn(res)end leaf非递归：procedure leaf(T)global integer S(1:n), lL, lR, res, addrInit(S)L1: if T=n:1 then res = 0elseif T是叶子then res =1elsepush(T);push(lR);push(lL);push(2)T <- T.lchildgoto L1L2: lL <- pop(S)push(T);push(lR);push(lL);push(3)T <- T.rchildgoto L1L3: lR <- pop(S)res = lL+lRendifendifif empty(S) then return reselseaddr <- pop(S)lL <- pop(S)lR <- pop(S)T <- pop(S)push(res)if addr = 2 then goto L2 endifif addr = 3 then goto L3 endif endifend leaf【3.11】将递归过程MAXMIN翻译成在计算机上等价的非递归过程解：procedure MAXMIN(i,j,fmax,fmin)integer i,j,k; integer stack(1:4n)global n, A(1:n)top <- 0L1: case:i=j: fmax <- fmin <- A(i):i=j-1:if A(i) < A(j) thenfmax <- A(j)fmin <- A(i)elsefmax <- A(i)fmin <- A(j)endif:else:mid <- ⌊(i+j)/2⌋top <- top+1; stack(top) <- i; k <- j; j <- mid;top <- top+1; stack(top) <- j; j <- k; k <- ii <- mid+1; top <- top+1; stack(top) <- itop <- top+1; stack(top) <- j; i <- ktop <- top+1; stack(top) <- 2goto L1L2: gmax <- stack(top); top <- top-1gmin <- stack(top); top <- top-1hmax <- stack(top); top <- top-1hmin <- stack(top); top <- top-1endcaseif top = 0 thenfmax <- max(gmax, hmax)fmin <- min(gmin, hmin)elseaddr <- stack(top); top <- top-1j <- stack(top); top <- top-1; i <- stack(top); top <- top-1;j <- stack(top); top <- top-1; i <- stack(top); top <- top-1;top <- top+1; stack(top) <- hmintop <- top+1; stack(top) <- hmaxtop <- top+1; stack(top) <- gmintop <- top+1; stack(top) <- gmaxif addr=2 then goto L2 endifendifend MAXMIN【4.1】quicksort算法是一种不稳定的算法，但如果把A(i)中的值做适当变换，可使A(i)值各不相同，在分类之后，在将A(i)恢复成原来的值A(i)，试给出变换和恢复表达式，并证明该式能满足要求。

递归和分治法摘要：1.递归和分治法的定义2.递归和分治法的区别3.递归和分治法的应用实例4.递归和分治法的优缺点正文：递归和分治法是计算机科学中常用的两种算法设计技巧。

它们在解决问题时都采用了将问题分解成更小子问题的思路，但在具体实现上却有所不同。

下面，我们来详细了解一下递归和分治法。

1.递归和分治法的定义递归法是指在算法中调用自身来解决问题的方法。

递归函数在执行过程中，会将原问题分解成规模更小的相似子问题，然后通过调用自身的方式，解决这些子问题，最后将子问题的解合并，得到原问题的解。

分治法是指将一个大问题分解成若干个规模较小的相似子问题，然后分别解决这些子问题，最后将子问题的解合并，得到原问题的解。

分治法在解决问题时，通常需要设计一个主函数（master function）和一个子函数（subfunction）。

主函数负责将问题分解，子函数负责解决子问题。

2.递归和分治法的区别递归法和分治法在解决问题时都采用了将问题分解成更小子问题的思路，但它们在实现上存在以下区别：（1）函数调用方式不同：递归法是通过调用自身来解决问题，而分治法是通过调用不同的子函数来解决问题。

（2）递归法必须有递归出口，即必须有一个基线条件，而分治法不一定需要。

3.递归和分治法的应用实例递归法应用广泛，例如斐波那契数列、汉诺塔问题、八皇后问题等。

分治法也有很多实际应用，例如快速排序、归并排序、大整数乘法等。

4.递归和分治法的优缺点递归法的优点是代码简单易懂，但缺点是容易产生大量的重复计算，导致时间复杂度较高。

分治法的优点是时间复杂度较低，但缺点是代码实现相对复杂，需要设计主函数和子函数。

总之，递归和分治法都是解决问题的有效方法，具体应用需要根据问题的特点来选择。

分治算法知识点总结一、基本概念分治算法是一种递归的算法，其基本思想就是将原问题分解成多个相互独立的子问题，然后分别解决这些子问题，最后将子问题的解合并得到原问题的解。

分治算法的核心思想可以用一句话概括：分而治之，分即是将原问题分解成若干个规模较小的子问题，治即是解决这些子问题，然后将子问题的解合并起来得到原问题的解。

分治算法通常包括三个步骤：（1）分解：将原问题分解成若干个规模较小的子问题；（2）解决：递归地解决这些子问题；（3）合并：将子问题的解合并起来得到原问题的解。

分治算法的典型特征包括递归和合并。

递归指的是将原问题分解成若干个规模较小的子问题，然后递归地解决这些子问题；合并指的是将子问题的解合并得到原问题的解。

通常来说，分治算法的递归实现方式很容易编写，但有时可能会面临大量的重复计算，因此需要合并操作来避免这种情况。

二、原理分治算法的原理可以通过一个简单的例子来说明。

我们以计算数组中的最大值为例，具体的步骤如下：（1）分解：将数组分解成两个规模相等的子数组；（2）解决：递归地在这两个子数组中分别找到最大值；（3）合并：比较这两个子数组的最大值，得到原数组的最大值。

从这个例子可以看出，分治算法将原问题分解成两个子问题：分别在左边子数组和右边子数组中找到最大值，然后将这两个子问题的解合并起来得到原数组的最大值。

这种将问题分解成若干个规模较小的子问题，然后合并子问题的解得到原问题的解的方法正是分治算法的核心原理。

分治算法的优势在于它可以将原问题分解成多个规模较小的子问题，然后并行地解决这些子问题，最后合并子问题的解得到原问题的解。

这种并行的设计思路使得分治算法非常适合于并行计算，能够有效地提高计算效率。

三、应用分治算法在计算机科学领域有着广泛的应用，包括排序、搜索、图论、动态规划等多个方面。

下面我们将以排序算法和搜索算法为例，来介绍分治算法在实际应用中的具体情况。

1. 排序算法排序算法是计算机科学领域中一个重要的问题，分治算法在排序算法中有着广泛的应用。

算法设计与分析：递归与分治法-实验报告(总8页)实验目的：掌握递归与分治法的基本思想和应用，学会设计和实现递归算法和分治算法，能够分析和评价算法的时间复杂度和空间复杂度。

实验内容：1.递归算法的设计与实现3.算法的时间复杂度和空间复杂度分析实验步骤：1）递归定义：一个函数或过程，在其定义或实现中，直接或间接地调用自身的方法，被成为递归。

递归算法是一种控制结构，它包含了解决问题的基础情境，也包含了递归处理的情境。

2）递归特点：递归算法具有以下特点：①依赖于递归问题的部分解被划分为若干较小的部分。

②问题的规模可以通过递推式递减，最终递归终止。

③当问题的规模足够小时，可以直接求解。

3）递归实现步骤：①确定函数的定义②确定递归终止条件③确定递归调用的过程4）经典实例：斐波那契数列递推式：f(n) = f(n-1) + f(n-2)int fib(int n) {if (n <= 0)return 0;else}5）优化递归算法：避免重复计算例如，上述斐波那契数列的递归算法会重复计算一些中间结果，影响效率。

可以使用动态规划技术，将算法改为非递归形式。

int f1 = 0, f2 = 1;for (int i = 2; i <= n; i++) {f1 = f2;使用循环避免递归，重复计算可以大大减少，提高效率。

1）分治算法的定义：将原问题分解成若干个规模较小且类似的子问题，递归求解子问题，然后合并各子问题得到原问题的解。

2）分治算法流程：②将问题分解成若干个规模较小的子问题。

③递归地解决各子问题。

④将各子问题的解合并成原问题的解。

3）分治算法实例：归并排序归并排序是一种基于分治思想的经典排序算法。

排序流程：②分别对各子数组递归进行归并排序。

③将已经排序好的各子数组合并成最终的排序结果。

实现源代码：void mergeSort(int* arr, int left, int right) {if (left >= right)while (i <= mid && j <= right)temp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];temp[k++] = arr[i++];1) 时间复杂度的概念：指完成算法所需的计算次数或操作次数。

递归和分治法摘要：一、递归与分治法的概念1.递归：函数调用自身的思想2.分治法：把一个大问题分解成若干个小问题二、递归与分治法的联系与区别1.递归通常作为分治法的实现方式2.分治法不一定要用递归实现三、递归与分治法的应用实例1.快速排序算法2.归并排序算法3.汉诺塔问题正文：递归和分治法是两种在计算机科学中经常使用的解决问题的方法。

递归是一种函数调用自身的思想，即函数在执行过程中，会调用自身来完成某些操作。

而分治法则是把一个大问题分解成若干个小问题，然后逐个解决这些小问题，最后再把它们的解合并，得到大问题的解。

这两种方法在某些情况下可以相互转化，递归通常作为分治法的实现方式，但分治法不一定要用递归实现。

递归与分治法之间的联系在于，递归通常是分治法的实现方式。

在分治法中，我们会把一个大问题分解成若干个小问题，然后通过递归的方式，逐个解决这些小问题。

最后，再把它们的解合并，得到大问题的解。

在这个过程中，递归函数的调用栈会随着问题规模的减小而减小，最终回到原点，从而完成问题的求解。

然而，分治法并不一定要用递归实现。

在一些情况下，我们可以通过迭代的方式，逐个解决小问题，然后把它们的解合并。

这种方式虽然不是通过递归函数调用自身来实现的，但它仍然符合分治法的思想，即把大问题分解成小问题，逐个解决。

递归和分治法在实际问题中有很多应用。

例如，快速排序算法和归并排序算法都是基于分治法的思想设计的。

在快速排序算法中，我们选择一个基准元素，然后把数组中小于基准的元素放在左边，大于基准的元素放在右边，再对左右两个子数组递归地执行相同的操作，直到数组有序。

而在归并排序算法中，我们同样把数组分成左右两个子数组，然后递归地对它们进行排序，最后再把排序好的子数组合并成一个有序的数组。

另一个例子是汉诺塔问题。

在这个问题中，有三个柱子和一个大小不同的圆盘。

要求把圆盘从第一个柱子移动到第三个柱子，每次只能移动一个圆盘，并且大盘不能放在小盘上。

实验一分治与递归（4学时）一、实验目的与要求1、熟悉C/C++语言的集成开发环境；2、通过本实验加深对递归过程的理解二、实验内容掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递归算法。

三、实验题任意输入一个整数，输出结果能够用递归方法实现整数的划分。

四、程序代码五、实验结果首先按照提示输入数字：按回车键，得到此数划分的个数：此时您可以接着计算另一个数的划分个数：若要退出，请输入一个小于等于零的数：六、结果分析及程序功能经过和其它同学的实验数据对比，初步认定此程序基本正确，然而不足之处是只能得到划分的个数，而不能列出每个划分的详细情况。

一、实验目的与要求1、掌握棋盘覆盖问题的算法；2、初步掌握分治算法二、实验题盘覆盖问题：在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。

在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。

三、程序代码四、实验结果按照提示输入特殊方格的行号和列号（起始行列号为0）：按回车键，得到一个矩阵，数字相同区域为一个L型骨牌覆盖：五、结果分析及程序功能得到的16*16棋盘覆盖结果正确，此程序的不足之处：只能设定特殊方格的行列号，而不能设定棋盘的大小。

实验二动态规划算法(4学时)一、实验目的与要求1、熟悉最长公共子序列问题的算法；2、初步掌握动态规划算法；二、实验题若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。

例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。

给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。