当前位置：文档之家 › 第二章递归与分治策略

第二章递归与分治策略

  • 格式：ppt
  • 大小：391.50 KB
  • 文档页数：61

下载文档原格式

  / 61

合集下载

分治策略

分治策略
分治策略
分治法的设计思想是： 将一个难以直接解决的大问
题，分割成一些规模较小的
相同问题，以便各个击破，
分而治之。
1、分治策略的定义；
2、分治法解题的步骤；
3、典型例题与练习；
1、分治策略的定义
对于一个规模为n的问题，若该问题 可以容易地解决（比如说规模n较小）则 直接解决，否则将其分解为k个规模较小 的子问题，这些子问题互相独立且与原问
• • • • • • • • • • • • • • • • • • • • • • • • • • • •
var i,j,k,kk:integer; begin if ed-st>0 then begin merge(st,(st+ed) div 2); merge((st+ed) div 2+1,ed); aaa[st,ed]:=aaa[st,(st+ed) div 2]+aaa[(st+ed) div 2+1,ed]; i:=st; j:=(st+ed) div 2+1; while (i<=(st+ed) div 2+1) and (j<=ed) do if a[i]>a[j] then begin aaa[st,ed]:=aaa[st,ed]+ed-j+1; i:=i+1; end else j:=j+1; i:=st; j:=(st+ed) div 2+1; k:=st; while (i<=(st+ed) div 2) and (j<=ed) do if a[i]>a[j] then begin aa[k]:=a[i];k:=k+1;i:=i+1;end else begin aa[k]:=a[j];k:=k+1;j:=j+1;end; if i<=(st+ed) div 2 then for kk:=i to (st+ed) div 2 do begin aa[k]:=a[kk];k:=k+1;end; if j<=ed then for kk:=j to ed do begin aa[k]:=a[kk];k:=k+1;end; for k:=st to ed do a[k]:=aa[k]; end; end;

第2章 递归与分治_作业答案讲解

第2章 递归与分治_作业答案讲解

具体执行过程：求最大值
0 1 2 3 4 5 6 7 8 9 10 11 12 13 24 -13 29 113 87 65 -9 36 14 76 44 83 67 5 0 1 2 3 4 5 6 24 -13 29 113 87 65 -9 0 1 2 3 24 -13 29 113 0 1 24 -13 2 3 29 113 4 5 6 87 65 -9 7 8 9 10 11 12 13 36 14 76 44 83 67 5 7 8 9 10 36 14 76 44 7 8 36 14 7 36 9 10 76 44 11 12 13 83 67 5 11 12 83 67 11 83 12 67 13 5
课后练习
• 练习2：分析如下时间函数的复杂度，并说明 原因。 1. 利用递归树说明以下时间函数的复杂度：
O(1) T ( n) 3T ( n ) O( n) 4 n1 n1
2. 利用主定理说明以下时间函数的复杂度：
T(n) = 16T(n/4) + n
T(n) = T(3n/7) + 1
课后练习
• 练习1：给定数组a[0:n-1]， 1. 试设计一个分治法算法，找出a[0:n-1]中元素最 大值和最小值； 2. 写出该算法时间函数T(n)的递推关系式； 3. 分析该算法的时间复杂度和空间复杂度。
0 1 2 3 4 5 6 7 8 9 10 11 12 13 24 -13 29 113 87 65 -9 36 14 76 44 83 67 5
• 递归公式：
– 设n个元素的集合可以划分为F(n,m)个不同的由 m个非空子集组成的集合。 F(n,m) = 1, when n=0, n=m, n=1, or m=1 F(n,m) = 0, when n<m 否则 F(n,m)=F(n-1,m-1)+m*F(n-1,m)

递归与分治算法心得

递归与分治算法心得

递归与分治算法心得
递归与分治算法都是常用的算法思想，可以很好地解决复杂问题。

递归算法是通过将问题分解为相同或相似的子问题来解决整个问题，然后再逐步合并回原问题的过程。

递归算法通常需要明确边界条件，以确保递归能够正确地停止。

分治算法是将问题分解成若干个相同或相似的子问题，递归地解决这些子问题，然后合并这些子问题的解来解决原始问题。

通常，分治算法可以高效地解决问题，但需要注意分解问题的方式和合并子问题的解的过程。

在实际应用中，递归和分治算法可以相互结合，以解决更加复杂的问题。

例如，可以使用分治算法来将问题分解成多个子问题，然后使用递归算法来解决这些子问题。

此外，还可以在递归算法中使用分治算法来对子问题进行分解和合并。

总而言之，递归与分治算法都是非常有用的算法思想，可以在许多领域中得到应用。

但是，在实际使用时，需要仔细考虑问题的性质和算法的复杂度，以确保算法的正确性和效率。

- 1 -。

五大常用算法

五大常用算法
Your company slogan
回溯法
基本概念 回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发 现原先选择并不是最优或达不到目标，就退回一步重新选择，这种走不通就退回再走的方 法称为回溯法。 基本思想 在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解 空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结 点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回 溯法就是对隐式图的深度优先搜索算法）。 若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍 才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束 。
Your company slogan
贪心算法
例 在漆黑的夜里，四位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的 话，大家是无论如何也不敢过桥去的。不幸的是，四个人一共只带了一只手电筒，而桥窄得 只够让两个人同时过。如果各自单独过桥的话，四人所需要的时间分别是1、2、5、8分钟； 而如果两人同时过桥，所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题 是，如何设计一个方案，让这四人尽快过桥 。
2012年林清华等人提出一种新型快速中值滤波算法，主要应用于医学图像.文中方法利 用中值滤波算法对滤波窗口内其他像素点的排列顺序不作要求的特点，将基于排序寻找中 值的过程转换为基于分治查找中值的过程。在分治查找过程中，利用医学图像未受干扰时 图像中像素值的变化是渐变的特性，优先选用中心点附近的像素值进行分治查找，以达到
图1 动态规划决策过程示意图 实际应用中可以按以下几个简化的步骤进行设计： （1）分析最优解的性质，并刻画其结构特征。 （2）递归的定义最优解。 （3）以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值。 （4）根据计算最优值时得到的信息B→ 2 A←1 AC → 5 A←1 AD → 8 一共就是2+1+5+1+8=17分钟。

递归和分治法

递归和分治法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

递归与分治ppt课件

递归与分治ppt课件
C三个柱子间移动。}
2023/10/8
计算机算法设计与分析
3
Hanoi塔问题的时间复杂性
n Hanoi塔问题的时间复杂性为O(2n)。 n 证明：对n归纳证明move(n) = 2n – 1。 n 归纳基础：当n = 1, move(1) = 1 = 21 – 1。 n 归纳假设：当n k, move(n) = 2n – 1。 n 归纳步骤：当n= k + 1，移动次数为
2、除法，即n / b，的形式
2023/11/4
计算机算法设计与分析
21
递归算法的时间复杂性
n 若~为减法，即n – b，则有：
T(n) = aT(n – b) + D(n)
= a(aT(n – 2b) + D(n – b)) + D(n) =
k–1
k–1
= akT(1) + ai D(n – ib) = ak + ai D(n – ib)
n q最(n简, m单)情{ 形1：(1) q(n, 1)=1, q(1, mn)==1 n或, mm≥1=;1 n 递q(iin归ff,((mnn关)<=系==1)：1q1)||(|((+|nm2(,)qmm<(qn=–(1,n1=)n,)–+1n1)q))(=rrnee–1ttmuu+rr,nqnm(01n);;, nnn＞–≤1m)m，＞n1＞1; n 产i生f (n的=新= 情1) 况|| (：n < m) return 1 + q(n, n–1); n (3r)eqtu(nr,nmq)(n=,qm(n–,1m) +–1q)(n+–qm(,nm–m);, m} ), n＞m＞1 n (整4)数q(nn的, m划)分= q数(nρ,(n),=nq＜(nm, n。)。

士兵站队问题

士兵站队问题

如何确定X轴方向上的最佳的“最终位置”？
n个士兵他们相应的X轴坐标为：X0，X1，X2…Xn-1 设“最终位置”的X轴坐标值为：k，k+1，k+2…k+（n-1） 则最优步数：S=|X0-k|+|X1-(k+1)|+|X2-(k+2)|+…+|Xn-1-(k+(n-1))| 经过变形：S=|X0-k|+|(X1-1)-k|+|(X2-2)-k|+…+|(Xn-1-(n-1))-k|
第二章：递归与分治策略 ---士兵站队问题
问题描述：
• 在一个划分成网格的操场上，n个士兵散乱地 站在网格点上。网格点由整数坐标(x,y)表示。士 兵们可以沿网格边上、下、左、右移动一步，但 在同一时刻任一网格点上只能有一名士兵。按照 军官的命令，士兵们要整齐地列成一个水平队列， 即排列成(x,y),(x+1,y),…,(x+n-1,y)。如何选 择x和y的值才能使士兵们以最少的总移动步数排 成一列。
• • • • • • • • • • • • • • • • • • • • • • • •
#include <iostream> #include <math.h> #include <stdlib.h> using namespace std; void Swap(int &a,int &b)//交换函数 { int temp;//定义一个交换的临时变量 temp=a; a=b; b=temp; } int partition(int *a,int low,int high)//确定一个基准元素以对数组元素进行划分 { int key = a[low];//key初始化为a的首元素 while(low<high) { while(low<high && a[high]>=key) high--; a[low] = a[high]; while(low<high && a[low]<=key) low++; a[high]=a[low]; } a[low]=key; return low; }

计算机专业课《算法》_第二章 递归与分治策略

计算机专业课《算法》_第二章 递归与分治策略

“Hanoi 塔”问题演示 a 初始 a 步骤1 a
c
b
c
“Hanoi 塔”问题程序
void hanoi(int n,a,b,c)
{ if n == 1 move( 1, a, b );
else { hanoi( n-1, a, c, b );
move(n, a, b ); hanoi( n-1, c,b, a) ;
• 递归优点：结构清晰，可读性强
• 递归缺点：递归算法的运行效率较低，无论是耗 费的计算时间还是占用的存储空间都比非递归算 法要多。
整数划分问题的递归关系q(n,m)
如设p(n)为正整数n的划分数，则难以找到递归关系 • q(n,m):正整数n的不同的划分中，最大加数不 大于m的划分个数个数 q(n,m)=
1 q(n,n) 1+q(n,n-1) q(n,m-1)+q(n-m,m) n=1, m=1 n<m n=m n>m>1
递归函数举例(5)
学习要点
理解递归的概念。 掌握设计有效算法的分治策略。
通过典型范例，学习分治策略设计技巧。
2.1 递归的概念
• 递归算法：一个直接或间接地调用自身的算法 • 递归方程：对于递归算法，一般可把时间代 价表示为一个递归方程 • 递归函数：使用函数自身给出定义的函数 • 解递归方程最常用的方法是进行递归扩展
递归函数举例(1)
• 阶乘函数 n ！=
1 n(n-1)！ n=1 n>1
• Fibonacci数列
1 n=0
F(n)=
1 F(n-1)+F(n-2)
n=1 n>1
初始条件与递归方程是递归函数的二个要素

算法之2章递归与分治

算法之2章递归与分治

算法分析(第二章)：递归与分治法一、递归的概念知识再现：等比数列求和公式：1、定义：直接或间接地调用自身的算法称为递归算法。

用函数自身给出定义的函数称为递归函数。

2、与分治法的关系：由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。

在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。

这自然导致递归过程的产生。

分治与递归经常同时应用在算法设计之中，并由此产生许多高效算法。

3、递推方程：(1)定义：设序列01,....na a a简记为{na}，把n a与某些个()ia i n<联系起来的等式叫做关于该序列的递推方程。

(2)求解：给定关于序列{n a}的递推方程和若干初值，计算n a。

4、应用：阶乘函数、Fibonacci数列、Hanoi塔问题、插入排序5、优缺点：优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。

缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。

二、递归算法改进：1、迭代法：(1)不断用递推方程的右部替代左部(2)每一次替换，随着n的降低在和式中多出一项(3)直到出现初值以后停止迭代(4)将初值代入并对和式求和(5)可用数学归纳法验证解的正确性2、举例：-----------Hanoi塔算法----------- ---------------插入排序算法----------- ()2(1)1(1)1T n T nT=−+=()(1)1W n W n nW=−+−（1）=021n-23()2(1)12[2(2)1]12(2)21...2++2 (121)n n n T n T n T n T n T −−=−+=−++=−++==++=−（1）2 ()(1)1((n-2)+11)1(2)(2)(1)...(1)12...(2)(1)(1)/2W n W n n W n n W n n n W n n n n =−+−=−−+−=−+−+−==++++−+−=−3、换元迭代：(1)将对n 的递推式换成对其他变元k 的递推式 (2)对k 进行迭代(3)将解（关于k 的函数）转换成关于n 的函数4、举例：---------------二分归并排序---------------()2(/2)1W n W n n W =+−（1）=0（1）换元：假设2kn =，递推方程如下()2(/2)1W n W n n W =+−（1）=0 → 1(2)2(2)21k k k W W W−=+−（0）=0（2）迭代求解：12122222321332133212()2(2)212(2(2)21)212(2)22212(2)2*2212(2(2)21)2212(2)222212(2)3*2221...2(0)*2(22...21)22k k k k k k k k k k k k k k k k k k k k k k k k W n W W W W W W W W k k −−−−−−−+−+−−−=+−=+−+−=+−+−=+−−=+−+−−=+−+−−=+−−−==+−++++=−1log 1n n n +=−+（3）解的正确性—归纳验证： 证明递推方程的解是()(1)/2W n n n =−()(1)1W n W n n W =−+−（1）=0,(n 1)=n +n=n(n-1)/2+n =n[(n-1)/2+1]=n(n+1)/2n W W +方法：数学归纳法证 n=1,W(1)=1*(1-1)/2=0假设对于解满足方程，则（）---------------快速排序--------------------->>>平均工作量：假设首元素排好序在每个位置是等概率的112()()()(1)0n i T n T i O n n T −==+=∑ >>>对于高阶方程应该先化简，然后迭代(1)差消化简：利用两个方程相减，将右边的项尽可能消去，以达到降阶的目的。

算法设计与分析(霍红卫)-第2章-分治法

算法设计与分析(霍红卫)-第2章-分治法

第2章 分 治 法
我们可以很容易解决这个问题。利用这样一个事实：渐近 表示法只要求对n≥n0，T(n)≤cn lb n成立，其中n0是一个可以选择 的常数。由于对于n>3，递归方程并不直接依赖T(1)，因此可设 n0=2，选择T(2)和T(3)作为归纳证明中的边界条件。由递归方程 可得T(2)=4和T(3)=5。此时只要选择c≥2，就会使得T(2)≤c·2·lb 2 和 T(3)≤c·3·lb 3 成 立 。 因 此 ， 只 要 选 择 n0=2 和 c≥2 ， 则 有 T(n)≤cn lb n成立。
3ic(n/4i)2=(3/16) icn2 i=0，1，…，log4n-1
深度为log4n的最后一层有3log4 n nlog4 3 个结点，每个结点的
开销为T(1)，该层总开销为 nlog4 3T (1) ，即 Θ(nlog4 3)。
第2章 分 治 法
将所有层的开销相加得到整棵树的开销：
T (n) cn2
T(n)=2T(n/2)+n ≤2(c［n/2］lb［n/2］)+n =cn lb n/2+n =cn lb n-cn lb 2+n =cn lb n-cn+n =cn lb n-(c-1)n
最后一步在c≥1时成立。≤cn lb n
第2章 分 治 法
下面证明猜测对于边界条件成立， 即证明对于选择的常 数c，T(n)≤cn lb n对于边界条件成立。 这个要求有时会产生 一些问题。 假设T(1)=1是递归方程的惟一边界条件，那么对 于n=1，T(1)≤c·1·lb 1=0与T(1)=1发生矛盾。因此，归纳法中 的归纳基础不成立。
3
cn2
3
2
cn2
3

算法设计与分析习题第二章分治与递归

算法设计与分析习题第二章分治与递归

2010-12-28
12
2.11 编写针对链表的快速排序程序。
需要保存指针信息。下面给出双向链表的快速排序算法 void fast_sort( Sdata *a, Sdata *f, Sdata *t ) { Sdata *i,*j,k,p; i = f; j = t; if ( t->lnext != f ) { k = a->data; //用于比较的基准数值 i = f; j = t; p = -1; while ( j != i )
7
2.7 按2.2.4节的描述，编写从二叉树中删除一个结点 的C语言程序 二叉树节点删除有三种情况： (1)*p是叶子(即它的孩子数为0)：无须连接*p的子树， 只需将*p的双亲*parent中指向*p的指针域置空即可。 (2)*p只有一个孩子*child：只需将*child和*p的双亲直接 连接后，即可删去*p。注意：*p既可能是*parent的左孩 子也可能是其右孩子，而*child可能是*p的左孩子或右孩 子，故共有4种状态。 (3)*p有两个孩子：先令q=p，将被删结点的地址保存在q 中；然后找*q的中序后继*p，并在查找过程中仍用parent 记住*p的双亲位置。*q的中序后继*p一定是 *q的右子树 中最左下的结点，它无左子树。因此，可以将删去*q的 操作转换为删去的*p的操作，即在释放结点*p之前将其 数据复制到*q中，就相当于删去了*q.
算法设计与分析习题
第二章 分治与递归
2010-12-28
1
2.1 对于顺序查找算法，分析目标值存在于数组中的 概率p趋于0的含义，这种情况下平均查找次数有什么 样的变化？当p趋于1时呢？ 见教材P12。平均比较次数为 n - p(n-1)/2。 p趋于0，平均次数趋于n；p趋于1时，平均次数趋于 （n+1）/2。（求极限）

递归、分治、动态规划、回溯

递归、分治、动态规划、回溯
正整数n的划分数p(n)=q(n,n).
n = 1, m = 1 n<m n=m n > m >1
递归举例
Hanoi塔问题 例6 Hanoi塔问题 设a,b,c是3个塔座.开始时,在塔座a上有一叠共n个圆 盘,这些圆盘自下而上,由大到小地叠在一起.各圆 盘从小到大编号为1,2,…,n,现要求将塔座a上的这一 叠圆盘移到塔座b上,并仍按同样顺序叠置.在移动圆 盘时应遵守以下移动规则: 规则1:每次只能移动1个圆盘; 规则2:任何时刻都不允许将较大的圆盘压在较小的圆盘 之上; 规则3:在满足移动规则1和2的前提下,可将圆盘移至 a,b,c中任一塔座上.
边界条件
递归方程
A(1,0) = 2 A(0, m) = 1 m≥0 n≥2 A(n,0) = n + 2 A(n, m) = A( A(n 1, m), m 1) n, m ≥ 1
递归举例
例3 Ackerman函数 函数 当一个函数及它的一个变量是由函数自身定义时,称这 个函数是双递归函数 双递归函数. 双递归函数 Ackerman函数A(n,m) A(n, Ackerman A(n m)定义如下:
递归举例
例1 阶乘函数 阶乘函数可递归地定义为:
边界条件
n=0 1 n!= n(n 1)! n > 0
递归方程 边界条件与递归方程是递归函数的二个要素,递归函 数只有具备了这两个要素,才能在有限次计算后得出 结果.
递归举例
Fibonacci数列 例2 Fibonacci数列 无穷数列1,1,2,3,5,8,13,21,34,55,…,被 称为Fibonacci数列.它可以递归地定义为:
A(n,m)的自变量m的每一个值都定义了一个单变量函数: M=0时,A(n,0)=n+2 M=1时,A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2,和A(1,1)=2故 A(n,1)=2*n M=2时,A(n,2)=A(A(n-1,2),1)=2A(n-1,2),和 A(1,2)=A(A(0,2),1)=A(1,1)=2,故A(n,2)= 2^n .

递推-递归-分治-回溯

递推-递归-分治-回溯

递推算法在程序编辑过程中，我们可能会遇到这样一类问题，出题者告诉你数列的前几个数，或通过计算机获取了数列的前几个数，要求编程者求出第N项数或所有的数列元素（如果可以枚举的话），或求前N项元素之和。

这种从已知数据入手，寻找规则，推导出后面的数的算法，称这递推算法。

典型的递推算法的例子有整数的阶乘，1，2，6，24，120…，a[n]=a[n-1]*n(a[1]=1)；前面学过的2n，a[n]=a[n-1]*2(a[1]=1)，菲波拉契数列：1，2，3，5，8，13…，a[n]=a[n-1]+a[n-2](a[1]=1,a[2]=2)等等。

在处理递推问题时，我们有时遇到的递推关系是十分明显的，简单地写出递推关系式，就可以逐项递推，即由第i项推出第i+1项，我们称其为显示递推关系。

但有的递推关系，要经过仔细观察，甚至要借助一些技巧，才能看出它们之间的关系，我们称其为隐式的递推关系。

下面我们来分析一些例题，掌握一些简单的递推关系。

例如阶梯问题：题目的意思是：有N级阶梯，人可以一步走上一级，也可以一步走两级，求人从阶梯底走到顶端可以有多少种不同的走法。

这是一个隐式的递推关系，如果编程者不能找出这个递推关系，可能就无法做出这题来。

我们来分析一下：走上第一级的方法只有一种，走上第二级的方法却有两种（两次走一级或一次走两级），走上第三级的走法，应该是走上第一级的方法和走上第二级的走法之和（因从第一级和第二级，都可以经一步走至第三级），推广到走上第i级，是走上第i-1级的走法与走上第i-2级的走法之和。

很明显，这是一个菲波拉契数列。

到这里，读者应能很熟练地写出这个程序。

在以后的程序习题中，我们可能还会遇到菲波拉契数列变形以后的结果：如f(i)=f(i-1)+2f(i-2)，或f(i)=f(i-1)+f(i-2)+f(i-3)等。

我们再来分析一下尼科梅彻斯定理。

定理内容是：任何一个整数的立方都可以写成一串连续的奇数和，如：43=13+15+17+19=64。

递归，分治算法，动态规划和贪心选择的区别

递归，分治算法，动态规划和贪心选择的区别

递归，分治算法，动态规划和贪⼼选择的区别⼀般实际⽣活中我们遇到的算法分为四类：⼀>判定性问题⼆>最优化问题三>构造性问题四>计算性问题⽽今天所要总结的算法就是着重解决最优化问题《算法之道》对三种算法进⾏了归纳总结，如下表所⽰：标准分治动态规划贪⼼算法适⽤类型通⽤问题优化问题优化问题⼦问题结构每个⼦问题不同很多⼦问题重复（不独⽴）只有⼀个⼦问题最优⼦结构不需要必须满⾜必须满⾜⼦问题数全部⼦问题都要解决全部⼦问题都要解决只要解决⼀个⼦问题⼦问题在最优解⾥全部部分部分选择与求解次序先选择后解决⼦问题先解决⼦问题后选择先选择后解决⼦问题分治算法特征：1）规模如果很⼩，则很容易解决。

//⼀般问题都能满⾜2）⼤问题可以分为若⼲规模⼩的相同问题。

//前提3）利⽤⼦问题的解，可以合并成该问题的解。

//关键4）分解出的各个⼦问题相互独⽴，⼦问题不再包含公共⼦问题。

//效率⾼低【⼀】动态规划：依赖：依赖于有待做出的最优选择实质：就是分治思想和解决冗余。

⾃底向上（每⼀步，根据策略得到⼀个更⼩规模的问题。

最后解决最⼩规模的问题。

得到整个问题最优解）特征：动态规划任何⼀个i+1阶段都仅仅依赖 i 阶段做出的选择。

⽽与i之前的选择⽆关。

但是动态规划不仅求出了当前状态最优值，⽽且同时求出了到中间状态的最优值。

缺点：空间需求⼤。

【⼆】贪⼼算法：依赖：依赖于当前已经做出的所有选择。

⾃顶向下（就是每⼀步，根据策略得到⼀个当前最优解。

传递到下⼀步，从⽽保证每⼀步都是选择当前最优的。

最后得到结果）【三】分治算法：实质：递归求解缺点：如果⼦问题不独⽴，需要重复求公共⼦问题---------------------------------------------------------------------------------------------------------------------------贪⼼算法：贪⼼算法采⽤的是逐步构造最优解的⽅法。

递归和分治法

递归和分治法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

递归与分治算法

递归与分治算法

递归与分治算法
递归和分治算法是计算机科学中两种常见的算法设计技术。

递归是一种直接或间接调用自身函数或者方法的算法。

在递归算法中，函数在其定义中使用了函数自身的调用。

递归算法通常用于解决需要重复执行相同任务的问题，例如遍历树结构、递归搜索等。

递归算法的优点是代码简洁、易于理解，但需要注意递归深度的限制以及可能引发栈溢出的问题。

分治算法是一种将问题分解为多个子问题，并分别解决子问题的算法。

分治算法通过将大问题分解为小问题，并将小问题的解合并成大问题的解来解决问题。

分治算法通常用于排序、查找、矩阵乘法等问题。

分治算法的优点是可以将复杂问题分解为简单问题，降低问题的复杂度，但需要注意分解的子问题必须是相互独立的。

在实际应用中，递归和分治算法通常结合使用。

例如，快速排序算法就是一种典型的分治算法，它通过选择一个基准元素，将数组分为两个子数组，并对每个子数组递归地进行排序，最终合并两个有序子数组得到排序后的数组。

总之，递归和分治算法是计算机科学中重要的算法设计技术，它们可以有效地解决许多复杂的问题。

在实际应用中，需要根据问题的特点选择合适的算法，并注意算法的时间复杂度和空间复杂度。

(算法分析设计)第2章递归与分治策略

(算法分析设计)第2章递归与分治策略
后两种方法在时空复杂度上均有较大改善， 但其适用范围有限。
分治法的基本思想
分治法的基本思想
将一个规模为n的问题分解为a个规模较小的子 问题，这些子问题互相独立并且与原问题相同。 通过递归地求解这些子问题，然后再将各个子问 题的解合并，就可以实现对原问题的求解。
分治法的求解过程
分治法的求解过程
表示以塔座b为辅助塔座，将塔座ａ 上自下而上，由大到小叠在一起的 ｎ-1个圆盘按规则移至塔座ｃ上并 按同样顺序叠放。
将塔座a上的圆盘移动 到塔座b上去
Hanoi塔问题的复杂性分析
ｎ=1
移动次数Ｔ（１）＝１
ｎ＝２
移动次数Ｔ（２）＝３
ｎ＝３
移动次数Ｔ（３）＝７
ｎ＝４
移动次数Ｔ（４）＝１５
divide-and-conquer(P) {
if(|P|<=n0) adhoc(P);
n0：阀值
如果问题P的规模不超过n0，说明 问题已经容易求解，不要再继续 分解。利用adhoc(P)直接求解。
divide P into smaller subinstances P1,P2,…,Pa;
for(i=1,i<=a,i++)
T ( n ) ( n lo g b a ) O ( n lo g b a ) ( n lo g b a )
T ( n ) ( n l o g b a ) ( n l o g b a l g n ) ( n l o g b a l g n )
T ( n )( n lo g b a )(f( n ) )(f( n ) )
二分搜索技术 大整数的乘法 Strassen矩阵乘法 合并排序 快速排序 线性时间选择
二分搜索技术

递归分析和分治算法

递归分析和分治算法

递归分析和分治算法递归分析一般利用的方法是主定理，辅助的方法有替换法，递归树方法~主定理：递归树：主定理的证明可以通过递归树的方法进行；主定理适用的范围比较局限，有些情况不能被包括，这些情况就需要利用递归树的方法了，主定理的case1是f(n)小于n log b a多项式时间，原定理描述为f(n)=O（n log b a-ε）且ε>0，它与case2中f(n)=Θ(n log b a)中间差一些情况，就是f(n)小于n log b a，但是多余的不是多项式时间；另外就是case2和case3之间相差的部分，就是f(n)大于n log b a，但是如果不大于多项式时间，就不能满足主定理了；另外一种是case3中的f(n)不满足后面的情况；举个例子，如果最近点对中间利用快速排序进行排序，则合并时间nlgn，递归公式T（n）=2T（n/2）+nlgn，这种情况介于case2和case3，所以利用递归树：T（n）=nlgn+n(lgn-lg2)+n(lgn-lg4)+...=nlgnlgn-n(lg2+2lg2+3lg2+...+lgnlg2)=nlgnlgn-nlg2((1+lgn)lgn)/2=nlgnlgn=nlg2n;不过这里我查到mit给的主定理和算法导论有所不同，涵盖了上面的情况，如下：可能这算是一种情况来了；那么这里我在取一个不满足主定理的例子~所以主定理不满足时就利用决策树进行带入吧！如果数学计算能力比较强大还是可以计算出来的，毕竟主定理都是决策树证明的，数学能力不强表示证明有点困难...不过这里有个偷懒的证明方法，直接假设f（n）是一个n k形式的；T（n）=aT（n/b）+n kT（n/b）=aT（n/b2）+（n/b）k...所以T(n)=a（aT（n/b2）+（n/b）k）+n k=n k （1+a/b k+...+(a/b k)h)=(n k-n logba)/(1-a/b k),接下来讨论a和b k的关系决定了为n k还是n logba，上面如果为1则为n k log b n了。

算法设计与分析习题解答(第2版)

算法设计与分析习题解答(第2版)

第1章算法引论11.1 算法与程序11.2 表达算法的抽象机制11.3 描述算法31.4 算法复杂性分析13小结16习题17第2章递归与分治策略192.1 递归的概念192.2 分治法的基本思想262.3 二分搜索技术272.4 大整数的乘法282.5 Strassen矩阵乘法302.6 棋盘覆盖322.7 合并排序342.8 快速排序372.9 线性时间选择392.10 最接近点对问题432.11 循环赛日程表53小结54习题54第3章动态规划613.1 矩阵连乘问题62目录算法设计与分析(第2版)3.2 动态规划算法的基本要素67 3.3 最长公共子序列713.4 凸多边形最优三角剖分753.5 多边形游戏793.6 图像压缩823.7 电路布线853.8 流水作业调度883.9 0-1背包问题923.10 最优二叉搜索树98小结101习题102第4章贪心算法1074.1 活动安排问题1074.2 贪心算法的基本要素1104.2.1 贪心选择性质1114.2.2 最优子结构性质1114.2.3 贪心算法与动态规划算法的差异1114.3 最优装载1144.4 哈夫曼编码1164.4.1 前缀码1174.4.2 构造哈夫曼编码1174.4.3 哈夫曼算法的正确性1194.5 单源最短路径1214.5.1 算法基本思想1214.5.2 算法的正确性和计算复杂性123 4.6 最小生成树1254.6.1 最小生成树性质1254.6.2 Prim算法1264.6.3 Kruskal算法1284.7 多机调度问题1304.8 贪心算法的理论基础1334.8.1 拟阵1334.8.2 带权拟阵的贪心算法1344.8.3 任务时间表问题137小结141习题141第5章回溯法1465.1 回溯法的算法框架1465.1.1 问题的解空间1465.1.2 回溯法的基本思想1475.1.3 递归回溯1495.1.4 迭代回溯1505.1.5 子集树与排列树1515.2 装载问题1525.3 批处理作业调度1605.4 符号三角形问题1625.5 n后问题1655.6 0\|1背包问题1685.7 最大团问题1715.8 图的m着色问题1745.9 旅行售货员问题1775.10 圆排列问题1795.11 电路板排列问题1815.12 连续邮资问题1855.13 回溯法的效率分析187小结190习题191第6章分支限界法1956.1 分支限界法的基本思想1956.2 单源最短路径问题1986.3 装载问题2026.4 布线问题2116.5 0\|1背包问题2166.6 最大团问题2226.7 旅行售货员问题2256.8 电路板排列问题2296.9 批处理作业调度232小结237习题238第7章概率算法2407.1 随机数2417.2 数值概率算法2447.2.1 用随机投点法计算π值2447.2.2 计算定积分2457.2.3 解非线性方程组2477.3 舍伍德算法2507.3.1 线性时间选择算法2507.3.2 跳跃表2527.4 拉斯维加斯算法2597.4.1 n 后问题2607.4.2 整数因子分解2647.5 蒙特卡罗算法2667.5.1 蒙特卡罗算法的基本思想2667.5.2 主元素问题2687.5.3 素数测试270小结273习题273第8章 NP完全性理论2788.1 计算模型2798.1.1 随机存取机RAM2798.1.2 随机存取存储程序机RASP2878.1.3 RAM模型的变形与简化2918.1.4 图灵机2958.1.5 图灵机模型与RAM模型的关系297 8.1.6 问题变换与计算复杂性归约299 8.2 P类与NP类问题3018.2.1 非确定性图灵机3018.2.2 P类与NP类语言3028.2.3 多项式时间验证3048.3 NP完全问题3058.3.1 多项式时间变换3058.3.2 Cook定理3078.4 一些典型的NP完全问题3108.4.1 合取范式的可满足性问题3118.4.2 3元合取范式的可满足性问题312 8.4.3 团问题3138.4.4 顶点覆盖问题3148.4.5 子集和问题3158.4.6 哈密顿回路问题3178.4.7 旅行售货员问题322小结323习题323第9章近似算法3269.1 近似算法的性能3279.2 顶点覆盖问题的近似算法3289.3 旅行售货员问题近似算法3299.3.1 具有三角不等式性质的旅行售货员问题330 9.3.2 一般的旅行售货员问题3319.4 集合覆盖问题的近似算法3339.5 子集和问题的近似算法3369.5.1 子集和问题的指数时间算法3369.5.2 子集和问题的完全多项式时间近似格式337 小结340习题340第10章算法优化策略34510.1 算法设计策略的比较与选择34510.1.1 最大子段和问题的简单算法34510.1.2 最大子段和问题的分治算法34610.1.3 最大子段和问题的动态规划算法34810.1.4 最大子段和问题与动态规划算法的推广349 10.2 动态规划加速原理35210.2.1 货物储运问题35210.2.2 算法及其优化35310.3 问题的算法特征35710.3.1 贪心策略35710.3.2 对贪心策略的改进35710.3.3 算法三部曲35910.3.4 算法实现36010.3.5 算法复杂性36610.4 优化数据结构36610.4.1 带权区间最短路问题36610.4.2 算法设计思想36710.4.3 算法实现方案36910.4.4 并查集37310.4.5 可并优先队列37610.5 优化搜索策略380小结388习题388第11章在线算法设计39111.1 在线算法设计的基本概念39111.2 页调度问题39311.3 势函数分析39511.4 k 服务问题39711.4.1 竞争比的下界39711.4.2 平衡算法39911.4.3 对称移动算法39911.5 Steiner树问题40311.6 在线任务调度40511.7 负载平衡406小结407习题407词汇索引409参考文献415习题1-1 实参交换1习题1-2 方法头签名1习题1-3 数组排序判定1习题1-4 函数的渐近表达式2习题1-5 O(1) 和 O(2) 的区别2习题1-7 按渐近阶排列表达式2习题1-8 算法效率2习题1-9 硬件效率3习题1-10 函数渐近阶3习题1-11 n !的阶4习题1-12 平均情况下的计算时间复杂性4算法实现题1-1 统计数字问题4算法实现题1-2 字典序问题5算法实现题1-3 最多约数问题6算法实现题1-4 金币阵列问题8算法实现题1-5 最大间隙问题11第2章递归与分治策略14 习题2-1 Hanoi 塔问题的非递归算法14习题2-2 7个二分搜索算法15习题2-3 改写二分搜索算法18习题2-4 大整数乘法的 O(nm log(3/2))算法19习题2-5 5次 n /3位整数的乘法19习题2-6 矩阵乘法21习题2-7 多项式乘积21习题2-8 不动点问题的 O( log n) 时间算法22习题2-9 主元素问题的线性时间算法22习题2-10 无序集主元素问题的线性时间算法22习题2-11 O (1)空间子数组换位算法23习题2-12 O (1)空间合并算法25习题2-13 n 段合并排序算法32习题2-14 自然合并排序算法32习题2-15 最大值和最小值问题的最优算法35习题2-16 最大值和次大值问题的最优算法35习题2-17 整数集合排序35习题2-18 第 k 小元素问题的计算时间下界36习题2-19 非增序快速排序算法37习题2-20 随机化算法37习题2-21 随机化快速排序算法38习题2-22 随机排列算法38习题2-23 算法qSort中的尾递归38习题2-24 用栈模拟递归38习题2-25 算法select中的元素划分39习题2-26 O(n log n) 时间快速排序算法40习题2-27 最接近中位数的 k 个数40习题2-28 X和Y 的中位数40习题2-29 网络开关设计41习题2-32 带权中位数问题42习题2-34 构造Gray码的分治算法43习题2-35 网球循环赛日程表44目录算法设计与分析习题解答（第2版）算法实现题2-1 输油管道问题（习题2-30) 49算法实现题2-2 众数问题（习题2-31) 50算法实现题2-3 邮局选址问题（习题2-32) 51算法实现题2-4 马的Hamilton周游路线问题（习题2-33) 51算法实现题2-5 半数集问题60算法实现题2-6 半数单集问题62算法实现题2-7 士兵站队问题63算法实现题2-8 有重复元素的排列问题63算法实现题2-9 排列的字典序问题65算法实现题2-10 集合划分问题（一）67算法实现题2-11 集合划分问题（二）68算法实现题2-12 双色Hanoi塔问题69算法实现题2-13 标准二维表问题71算法实现题2-14 整数因子分解问题72算法实现题2-15 有向直线2中值问题72第3章动态规划76习题3-1 最长单调递增子序列76习题3-2 最长单调递增子序列的 O(n log n) 算法77习题3-7 漂亮打印78习题3-11 整数线性规划问题79习题3-12 二维背包问题80习题3-14 Ackermann函数81习题3-17 最短行驶路线83习题3-19 最优旅行路线83算法实现题3-1 独立任务最优调度问题（习题3-3) 83算法实现题3-2 最少硬币问题（习题3-4) 85算法实现题3-3 序关系计数问题（习题3-5) 86算法实现题3-4 多重幂计数问题（习题3-6) 87算法实现题3-5 编辑距离问题（习题3-8) 87算法实现题3-6 石子合并问题（习题3-9) 89算法实现题3-7 数字三角形问题（习题3-10) 91算法实现题3-8 乘法表问题（习题3-13) 92算法实现题3-9 租用游艇问题（习题3-15) 93算法实现题3-10 汽车加油行驶问题（习题3-16) 95算法实现题3-11 圈乘运算问题（习题3-18) 96算法实现题3-12 最少费用购物（习题3-20) 102算法实现题3-13 最大长方体问题（习题3-21) 104算法实现题3-14 正则表达式匹配问题（习题3-22) 105算法实现题3-15 双调旅行售货员问题（习题3-23) 110算法实现题3-16 最大 k 乘积问题（习题5-24) 111算法实现题3-17 最小 m 段和问题113算法实现题3-18 红黑树的红色内结点问题115第4章贪心算法123 习题4-2 活动安排问题的贪心选择123习题4-3 背包问题的贪心选择性质123习题4-4 特殊的0-1背包问题124习题4-10 程序最优存储问题124习题4-13 最优装载问题的贪心算法125习题4-18 Fibonacci序列的Huffman编码125习题4-19 最优前缀码的编码序列125习题4-21 任务集独立性问题126习题4-22 矩阵拟阵126习题4-23 最小权最大独立子集拟阵126习题4-27 整数边权Prim算法126习题4-28 最大权最小生成树127习题4-29 最短路径的负边权127习题4-30 整数边权Dijkstra算法127算法实现题4-1 会场安排问题（习题4-1) 128算法实现题4-2 最优合并问题（习题4-5) 129算法实现题4-3 磁带最优存储问题（习题4-6) 130算法实现题4-4 磁盘文件最优存储问题（习题4-7) 131算法实现题4-5 程序存储问题（习题4-8) 132算法实现题4-6 最优服务次序问题（习题4-11) 133算法实现题4-7 多处最优服务次序问题（习题4-12) 134算法实现题4-8 d 森林问题（习题4-14) 135算法实现题4-9 汽车加油问题（习题4-16) 137算法实现题4-10 区间覆盖问题（习题4-17) 138算法实现题4-11 硬币找钱问题（习题4-24) 138算法实现题4-12 删数问题（习题4-25) 139算法实现题4-13 数列极差问题（习题4-26) 140算法实现题4-14 嵌套箱问题（习题4-31) 140算法实现题4-15 套汇问题（习题4-32) 142算法实现题4-16 信号增强装置问题（习题5-17) 143算法实现题4-17 磁带最大利用率问题（习题4-9) 144算法实现题4-18 非单位时间任务安排问题（习题4-15) 145算法实现题4-19 多元Huffman编码问题（习题4-20) 147算法实现题4-20 多元Huffman编码变形149算法实现题4-21 区间相交问题151算法实现题4-22 任务时间表问题151第5章回溯法153习题5\|1 装载问题改进回溯法（一）153习题5\|2 装载问题改进回溯法（二）154习题5\|4 0-1背包问题的最优解155习题5\|5 最大团问题的迭代回溯法156习题5\|7 旅行售货员问题的费用上界157习题5\|8 旅行售货员问题的上界函数158算法实现题5-1 子集和问题（习题5-3) 159算法实现题5-2 最小长度电路板排列问题（习题5-9) 160算法实现题5-3 最小重量机器设计问题（习题5-10) 163算法实现题5-4 运动员最佳匹配问题（习题5-11) 164算法实现题5-5 无分隔符字典问题（习题5-12) 165算法实现题5-6 无和集问题（习题5-13) 167算法实现题5-7 n 色方柱问题（习题5-14) 168算法实现题5-8 整数变换问题（习题5-15) 173算法实现题5-9 拉丁矩阵问题（习题5-16) 175算法实现题5-10 排列宝石问题（习题5-16) 176算法实现题5-11 重复拉丁矩阵问题（习题5-16) 179算法实现题5-12 罗密欧与朱丽叶的迷宫问题181算法实现题5-13 工作分配问题（习题5-18) 183算法实现题5-14 独立钻石跳棋问题（习题5-19) 184算法实现题5-15 智力拼图问题（习题5-20) 191算法实现题5-16 布线问题（习题5-21) 198算法实现题5-17 最佳调度问题（习题5-22) 200算法实现题5-18 无优先级运算问题（习题5-23) 201算法实现题5-19 世界名画陈列馆问题（习题5-25) 203算法实现题5-20 世界名画陈列馆问题（不重复监视）（习题5-26) 207 算法实现题5-21 部落卫队问题（习题5-6) 209算法实现题5-22 虫蚀算式问题211算法实现题5-23 完备环序列问题214算法实现题5-24 离散01串问题217算法实现题5-25 喷漆机器人问题218算法实现题5-26 n 2-1谜问题221第6章分支限界法229习题6-1 0-1背包问题的栈式分支限界法229习题6-2 用最大堆存储活结点的优先队列式分支限界法231习题6-3 团顶点数的上界234习题6-4 团顶点数改进的上界235习题6-5 修改解旅行售货员问题的分支限界法235习题6-6 解旅行售货员问题的分支限界法中保存已产生的排列树237 习题6-7 电路板排列问题的队列式分支限界法239算法实现题6-1 最小长度电路板排列问题一（习题6-8) 241算法实现题6-2 最小长度电路板排列问题二（习题6-9) 244算法实现题6-3 最小权顶点覆盖问题（习题6-10) 247算法实现题6-4 无向图的最大割问题（习题6-11) 250算法实现题6-5 最小重量机器设计问题（习题6-12) 253算法实现题6-6 运动员最佳匹配问题（习题6-13) 256算法实现题6-7 n 后问题（习题6-15) 259算法实现题6-8 圆排列问题（习题6-16) 260算法实现题6-9 布线问题（习题6-17) 263算法实现题6-10 最佳调度问题（习题6-18) 265算法实现题6-11 无优先级运算问题（习题6-19) 268算法实现题6-12 世界名画陈列馆问题（习题6-21) 271算法实现题6-13 骑士征途问题274算法实现题6-14 推箱子问题275算法实现题6-15 图形变换问题281算法实现题6-16 行列变换问题284算法实现题6-17 重排 n 2宫问题285算法实现题6-18 最长距离问题290第7章概率算法296习题7-1 模拟正态分布随机变量296习题7-2 随机抽样算法297习题7-3 随机产生 m 个整数297习题7-4 集合大小的概率算法298习题7-5 生日问题299习题7-6 易验证问题的拉斯维加斯算法300习题7-7 用数组模拟有序链表300习题7-8 O(n 3/2)舍伍德型排序算法300习题7-9 n 后问题解的存在性301习题7-11 整数因子分解算法302习题7-12 非蒙特卡罗算法的例子302习题7-13 重复3次的蒙特卡罗算法303习题7-14 集合随机元素算法304习题7-15 由蒙特卡罗算法构造拉斯维加斯算法305习题7-16 产生素数算法306习题7-18 矩阵方程问题306算法实现题7-1 模平方根问题（习题7-10) 307算法实现题7-2 集合相等问题（习题7-17) 309算法实现题7-3 逆矩阵问题（习题7-19) 309算法实现题7-4 多项式乘积问题（习题7-20) 310算法实现题7-5 皇后控制问题311算法实现题7-6 3-SAT问题314算法实现题7-7 战车问题315算法实现题7-8 圆排列问题317算法实现题7-9 骑士控制问题319算法实现题7-10 骑士对攻问题320第8章NP完全性理论322 习题8-1 RAM和RASP程序322习题8-2 RAM和RASP程序的复杂性322习题8-3 计算 n n 的RAM程序322习题8-4 没有MULT和DIV指令的RAM程序324习题8-5 MULT和DIV指令的计算能力324习题8-6 RAM和RASP的空间复杂性325习题8-7 行列式的直线式程序325习题8-8 求和的3带图灵机325习题8-9 模拟RAM指令325习题8-10 计算2 2 n 的RAM程序325习题8-11 计算 g(m,n)的程序 326习题8-12 图灵机模拟RAM的时间上界326习题8-13 图的同构问题326习题8-14 哈密顿回路327习题8-15 P类语言的封闭性327习题8-16 NP类语言的封闭性328习题8-17 语言的2 O (n k) 时间判定算法328习题8-18 P CO -NP329习题8-19 NP≠CO -NP329习题8-20 重言布尔表达式329习题8-21 关系∝ p的传递性329习题8-22 L ∝ p 330习题8-23 语言的完全性330习题8-24 的CO-NP完全性330习题8-25 判定重言式的CO-NP完全性331习题8-26 析取范式的可满足性331习题8-27 2-SAT问题的线性时间算法331习题8-28 整数规划问题332习题8-29 划分问题333习题8-30 最长简单回路问题334第9章近似算法336习题9-1 平面图着色问题的绝对近似算法336习题9-2 最优程序存储问题336习题9-4 树的最优顶点覆盖337习题9-5 顶点覆盖算法的性能比339习题9-6 团的常数性能比近似算法339习题9-9 售货员问题的常数性能比近似算法340习题9-10 瓶颈旅行售货员问题340习题9-11 最优旅行售货员回路不自相交342习题9-14 集合覆盖问题的实例342习题9-16 多机调度问题的近似算法343习题9-17 LPT算法的最坏情况实例345习题9-18 多机调度问题的多项式时间近似算法345算法实现题9-1 旅行售货员问题的近似算法（习题9-9) 346 算法实现题9-2 可满足问题的近似算法（习题9-20) 348算法实现题9-3 最大可满足问题的近似算法（习题9-21) 349 算法实现题9-4 子集和问题的近似算法（习题9-15) 351算法实现题9-5 子集和问题的完全多项式时间近似算法352算法实现题9-6 实现算法greedySetCover（习题9-13) 352算法实现题9-7 装箱问题的近似算法First Fit（习题9-19) 356算法实现题9-8 装箱问题的近似算法Best Fit（习题9-19) 358算法实现题9-9 装箱问题的近似算法First Fit Decreasing（习题9-19) 360算法实现题9-10 装箱问题的近似算法Best Fit Decreasing（习题9-19) 361算法实现题9-11 装箱问题的近似算法Next Fit361第10章算法优化策略365 习题10-1 算法obst的正确性365习题10-2 矩阵连乘问题的 O(n 2) 时间算法365习题10-6 货物储运问题的费用371习题10-7 Garsia算法371算法实现题10-1 货物储运问题（习题10-3) 374算法实现题10-2 石子合并问题（习题10-4) 374算法实现题10-3 最大运输费用货物储运问题（习题10-5) 375算法实现题10-4 五边形问题377算法实现题10-5 区间图最短路问题（习题10-8) 381算法实现题10-6 圆弧区间最短路问题（习题10-9) 381算法实现题10-7 双机调度问题（习题10-10) 382算法实现题10-8 离线最小值问题（习题10-11) 390算法实现题10-9 最近公共祖先问题（习题10-12) 393算法实现题10-10 达尔文芯片问题395算法实现题10-11 多柱Hanoi塔问题397算法实现题10-12 线性时间Huffman算法400算法实现题10-13 单机调度问题402算法实现题10-14 最大费用单机调度问题405算法实现题10-15 飞机加油问题408第11章在线算法设计410习题11-1 在线算法LFU的竞争性410习题11-4 多读写头磁盘问题的在线算法410习题11-6 带权页调度问题410算法实现题11-1 最优页调度问题（习题11-2) 411算法实现题11-2 在线LRU页调度（习题11-3) 414算法实现题11-3 k 服务问题（习题11-5) 416参考文献422。

第2章作业答案2-3_2-15

第2章作业答案2-3_2-15
▪ 如：序列2 3 4 5，x=5时， ▪ left=0,right=3,mid=1,x>a[1]=3,left=1 ▪ left=1,right=3,mid=2,x>a[2]=4,left=2 ▪ left=2,right-1=2,while循环结束 ▪ 5==a[2]不为真 ▪ 故return -1； ▪ 返回-1表示找不到x，这是一个错误的结论！
▪
int middle = (left+right+1)/2;
▪
if (x < a[middle]) right = middle-1;
▪
else left = middle;
▪
}
▪
if (x == a[left]) return left;
▪}
▪ return -1;
▪}
14
2－2 （5）
▪ 正确。用几个特殊实例证明其正确性。 ▪ 如：序列2 3 4 5，x=5时， ▪ left=0,right=3,mid=2,x>a[2]=4,left=2 ▪ left=2,right=3,mid=3,x=a[3]=5,left=3 ▪ left=3,right=3,while循环结束 ▪ 5==a[3],return 3; ▪ 输出正确
2
2－2判断7个二分搜索算法的正确性。
▪ 下面的7个算法与本章中的二分搜索算法 BinarySearch略有不同。请判断这7个算 法的正确性。如果算法不正确，请说明产 生错误的原因。如果算法正确，请给出算 法的正确性证明。
3
二分搜索算法：
▪ template<class Type>
▪ int BinarySearch(Type a[ ], const Type& x, int left, int right)
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

2.1 递归的概念
例5 整数划分问题 将正整数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。
2.1 递归的概念
例5 整数划分问题 前面的几个例子中，问题本身都具有比较明显的递归关系，因 而容易用递归函数直接求解。 在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关 系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个 数记作q(n,m)。可以建立q(n,m)的如下递归关系。
• 将求出的小规模的问题的解合并为一个更大规模的问 题的解，自底向上逐步求出原来问题的解。
T(n)
n/4
=
n/4
n
n/4 n/4
T(n/16) T(n/16) T(n/16) T(n/16) T(n/16) T(n/16) T(n/16) T(n/16)T(n/16) T(n/16) T(n/16) T(n/16) T(n/16) T(n/16) T(n/16) T(n/16
1 q(n, n) q(n, m) 1 q(n, n 1) q(n, m 1) q(n m, m)
正整数n的划分数p(n)=q(n,n)。
n 1, m 1 nm nm n m 1
整数划分问题递归程序
int q(int n,int m) { if ((n<1)||(m<1)) return 0; if ((n= =1)||(m= =1)) return 1; if(n<m) return q(n,n); if (n= =m) return q(n,m-1)+1; return q(n,m-1)+q(n-m,m); }
2.1 递归的概念
例2 Fibonacci数列 无穷数列1，1，2，3，5，8，13，21，34，55，…， 被称为Fibonacci数列。它可以递归地定义为：
1 n0 F ( n) 1 n 1 F (n 1) F (n 2) n 1
第n个Fibonacci数可递归地计算如下： int fibonacci(int n) { if (n <= 1) return 1; return fibonacci(n-1)+fibonacci(n-2); }
分治策略的定义
• 分治策略是：对于一个规模为n的问 题，若该问题可以容易地解决（比如 说规模n较小）则直接解决，否则将其 分解为k个规模较小的子问题，这些子 问题互相独立且与原问题形式相同， 递归地解这些子问题，然后将各子问 题的解合并得到原问题的解。这种算 法设计策略叫做分治法。
• 如果原问题可分割成k个子问题，1<k≤n ，且这些子问题都可解，并 可利用这些子问题的解求出原问题的解，那么这种分治法就是可行 的。 • 由分治法产生的子问题往往是原问题的较小模式，这就为使用递归 技术提供了方便。在这种情况下，反复应用分治手段，
第2章 递归与分治策略
2.1 递归的概念
• 直接或间接地调用自身的算法称为 递归算法。 • 用函数自身给出定义的函数称为 递归函数。
下面来看几个实例。
2.1 递归的概念
例1 阶乘函数 阶乘函数可递归地定义为：
边界条件
n0 1 n! n(n 1)! n 0
递归方程 边界条件与递归方程是递归函数的二个要素，递归函 数只有具备了这两个要素，才能在有限次计算后得出 结果。
• 分治法的设计思想是，将一个难以直接 解决的大问题，分割成一些规模较小的 相同问题，以便各个击破，分而治之。
算法总体思想
• 将要求解的较大规模的问题分割成k个更小规模的子问题。
T(n)
=
n
T(n/4)
T(n/4)
T(n/4)
T(n/4)
算法总体思想
• 对这k个子问题分别求解。如果子问题的规模仍然不够 小，则再划分为k个子问题，如此递归的进行下去，直 到问题规模足够小，很容易求出其解为止。
2.1 递归的概念
例5 整数划分问题 前面的几个例子中，问题本身都具有比较明显的递归关系，因 而容易用递归函数直接求解。 在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关 系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个 数记作q(n,m)。可以建立q(n,m)的如下递归关系。 (1)q(n,1)=1; (1) q(n,1)=1,n1; (2)q(n,m)=q(n,n),m≥n; 当最大加数n1不大于1时，任何正整数n只有一种划分形式， n (3) q(n,n)=1+q(n,n-1); 即 n 111 正整数n的划分由n1=n的划分和n1≤n-1的划分组成。 (2) q(n,m)=q(n,n),mn; (4) q(n,m)=q(n,m-1)+q(n-m,m),n>m>1; 正整数n的最大加数n1不大于m的划分由n1=m的划分和 最大加数n1实际上不能大于n。因此，q(1,m)=1。 n1≤m-1 的划分组成。
递归小结
优点：结构清晰，可读性强，而且容易用数学归 纳法来证明算法的正确性，因此它为设计算法、 调试程序带来很大方便。 缺点：递归算法的运行效率较低，无论是耗费的 计算时间还是占用的存储空间都比非递归算法 要多。
递归小结
解决方法：在递归算法中消除递归调用，使其转 化为非递归算法。 1.采用一个用户定义的栈来模拟系统的递归调用 工作栈。该方法通用性强，但本质上还是递归， 只不过人工做了本来由编译器做的事情，优化 效果不明显。 2.用递推来实现递归函数。 3.通过Cooper变换、反演变换能将一些递归转化 为尾递归，从而迭代求出结果。
但本例中的Ackerman函数却无法找到非递归的定义。
2.1 递归的概念
例3 Ackerman函数 • A(n，m)的自变量m的每一个值都定义了一个单变量函数： • M=0时，A(n,0)=n+2 • M=1时，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和 A(1,1)=2故A(n,1)=2*n • M=2时，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，和 A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)= 22 • M=4时，A(n,4)的增长速度非常快，以至于没有适当的 n 数学式子来表示这一函数。
2
2.1 递归的概念
例3 Ackerman函数 • 定义单变量的Ackerman函数A(n)为，A(n)=A(n，n)。 • 定义其拟逆函数α(n)为：α(n)=min{k｜A(k)≥n}。 即α(n)是使n≤A(k)成立的最小的k值。 • α(n)在复杂度分析中常遇到。对于通常所见到的正 整数n，有α(n)≤4。但在理论上α(n)没有上界，随 着n的增加，它以难以想象的慢速度趋向正无穷大。
T(n)
n/4
=
n/4
n
n/4 n/4
T(n/16) T(n/16) T(n/16) T(n/16) T(n/16) T(n/16) T(n/16) T(n/16)T(n/16) T(n/16) T(n/16) T(n/16) T(n/16) T(n/16) T(n/16) T(n/16
算法总体思想
2.1 递归的概念
例6 Hanoi塔问题 void hanoi(int n, int a, int b, int c) 当n=1时，问题比较简单。此时，只要将编号为1的圆盘从塔座a直 在问题规模较大时，较难找到一般的方法，因此我们尝试 接移至塔座b上即可。 用递归技术来解决这个问题。 { 思考题：如果塔的个数变为a,b,c,d 当n＞1时，需要利用塔座c作为辅助塔座。此时若能设法将n-1个 if (n > 0) 四个，现要将n个圆盘从a全部移动 较小的圆盘依照移动规则从塔座a移至塔座c，然后，将剩下的最 { 到d，移动规则不变，求移动步数最 大圆盘从塔座a移至塔座b，最后，再设法将n-1个较小的圆盘依照 hanoi(n-1, a, c, b); 小的方案。 移动规则从塔座c移至塔座b。 move(a,b); 由此可见，n个圆盘的移动问题可分为2次n-1个圆盘的移动问题， hanoi(n-1, c, b, a); 这又可以递归地用上述方法来做。由此可以设计出解Hanoi塔问题 的递归算法如下。 } }
后两种方法在时空复杂度上均有较大改善， 但其适用范围有限。
• 任何一个可以用计算机求解的问题所需的计算时间都与其规 模有关。 • 问题的规模越小，越容易直接求解，解题所需的计算时间 也越少。 • 例如，对于n个元素的排序问题， • n=1时，不需任何计算。 • n=2时， 只要作一次比较即可排好序。 • n=3时 只要作3次比较即可，…。 • 而当n较大时，问题就不那么容易处理了。要想直接解决一 个规模较大的问题，有时是相当困难的。
2.1 递归的概念
例3 Ackerman函数 前2例中的函数都可以找到相应的非递归方式定义：
n! 1 2 3 (n 1) n
1 5 n1 1 5 n1 1 F (n) 2 5 2
边界条件
递归方程
2.1 递归的概念
例3 Ackerman函数 当一个函数及它的一个变量是由函数自身定义时，称这 个函数是双递归函数。 Ackerman函数A(n，m)定义如下：