算法课件以及实验指导书第2章分治策略

第2章递归与分治策略Divide

andConquer本章主要内容2递归分治法基本思想二分搜索算法BinarySearch合并排序算法MergeSort快速排序算法QuickSort线性时间选择Selection

in

Linear

Time2.1递归（Recursion）直接调用自己或间接通过一些语句调用自己。一个直接或间接地调用自身的算法称为递归算法。一个使用函数自身给出定义的函数称为递归函数。优点：描述某些数学问题非常自然，证明算法很容易缺点：时间、空间消耗多一个递归问题可分为“回推”和“递推”两个阶段3例2-1

阶乘函数1

n

=

0n(n

-1)!

n

>

0n!=

非递归部分，终止条件11actorial(4)

244*Factorial(3)

63*Factorial(2)

22*Factorial(1)1*Factorial(02.1

递归F

intFactorial(intn){4if

(n==0)

return1;return

n*Factorial(n-1);

)}递归满足如下条件：定义中必须包含一个基本部分(base)，其中对于n的一个或多个值，f(n)必须是直接定义的（递归出口）。在递归部分(recursivecomponent)中，右侧所出现的所有f的参数都必须有一个比n小，以便重复运用递归部分来改变右侧出现的f，直至出现f的基本部分。2.1

递归5递归满足如下条件：一个递归定义必须是有确切的含义的;一步比一步简单，最后是有终结的，决不能

无限循环下去，如阶乘函数中n为0时定义为1;“递归出口”本身不再使用递归的定义;每个递归函数都必须有非递归定义的初始值。2.1

递归6Fibonacci数列1F(n)

=n=01

n=1F(n-1)+F(n-2)

n>1F4

=F3+F2

=F2

+F1

+F1

+F0

=

3F1

+

2F0

=

52.1

递归7例2-2

Fibonacci数列递归算法int

Fibonacci(int

n){int

f1,

f2;1

if

(n<=1) return

1;•2f1

=

Fibonacci(n-1);•3f2

=

Fibonacci(n-2);•4return

f1+f2;}2.1

递归89int

Fibonacci(intn){•••int

f1,

f2;if

(n<=1)

return

1;f1

=Fibonacci(n-1);3

f2

=

Fibonacci(n-2);••4

return

f1+f2;}mainx

:mainx

:fibn

:3f1:f2:fLine•:1fibn

:3f1:f2:fLine:2mainx

:fibn

:3f1:f2:fLine:2mainx

:fibn

:2f1:f2:fLine:1fibn

:3f1:f2:fLine:2fibn

:2f1:f2:fLine:2fibn

:1f1:f2:f:

1Line:1fibn

:3f1:f2:fLine:2fibn

:2f1:1f2:fLine:3fibn

:0f1:f2:f

:

0Line:1mainx

:fibn

:3f1:f2:fLine:2fibn

:2f1:1f2:fLine:3mainx

:fibn

:3f1:f2:fLine:2fibn

:2f1:1f2:0fLine:4mainx

:fibn

:3f1:1f2:fLine:3fibn

:1f1:f2:f:1Line:1mainx

:fibn

:3f1:1f2:1fLine:4mainx

:mainx

:2mainx

:2.1

递归非递归方式表达Fibonacci数列1F(n)

=n=01

n=1F(n-1)+F(n-2)

n>12.1

递归)

)102251-

5)

-(1+

5n+1n+1F

(n)

=

1

((非递归方式表达F(n)

=

F(n-1)+F(n-2)F(n)

-

F(n-1)

-

F(n-2)=0x2

-

x

-1

=

02.1

递归211x

=

1–

5F

(n)

=

c

xk

+1

+

c

xk

+11

1

2

2例2-3

排列问题设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。记为perm({r1,r2,…,rn})。比如a，b和c的排列方式有：abc,

acb, bac,

bca,

cab和cba。n个元素的排列方式共有n！种。abc

+acb

=a(bc+cb)

=aperm({b,c})bac

+bca

=b(ac+ca)

=bperm({a,c})cab

+cba

=c(ab+ba)

=cperm({a,b})2.1

递归1213设R={r1,r2,…,rn}是要进行排列的n个元素，Ri=R-{ri}。

(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列以后所得到的排列方式。所以R的全排列可以递归的写为：当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素；当n>1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)构成。Perm(R)=a.perm({b,c})+b.perm({a,c})+c.perm({a,b})。perm({b,c})=b.perm({c})+c.perm({b}),

所以a.perm({b,c})=

ab.perm({c})+ac.perm({b})=

ab.c+

ac.b=(abc,acb)。同理可得b.perm({a,c})=ba.perm({c})+

bc.perm({a})=

ba.c+

bc.a=

(bac,

bca)，c.perm({a,b})=ca.perm({b})+

cb.perm({a})=

ca.b+

cb.a=(cab,

cba)。2.1

递归排列问题的递归算法template<class

T>void

Perm(T

list[

],

int

k,

intm){//生成list

[k：m]的所有排列方式

int

i;if

(k

==

m){//输出一个排列方式for

(i

=

0;

i

<=

m;

i++)cout

<<

list

[i];cout

<<

endl;}else//list[k：m]有多个排列方式//递归地产生这些排列方式for

(i=k;

i

<=

m;i++){Swap

(list[k],

list[i]);Perm

(list,

k+1,

m);Swap

(list

[k],

list

[i]);}}2.1

递归14例2-4 Hanoi塔问题设A、B、C是三个塔座。开始时，在塔座A上有一叠共n各圆盘，这些圆盘自下而上，由大到小地叠在一起，各圆盘从小到大的编号为1，2，···，n，现要求将塔座A上的这一叠圆盘移到塔座B上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：每次只能移动一个圆盘；任何时刻都不允许将较大的圆盘压在较小的圆盘之上；在满足移动规则（1）和（2）的前提下，可将圆盘移至A，B，C中任一塔座上。2.1

递归154nono3no21nono3no21nono4①②③no3no2no12.1

递归原函数为hanoi(n,A,B,C)n＝1时，只要将编号为1的圆盘从A直接移动到B即可

n>1时第一步：先把n－1个盘子设法借助B杆放到C杆，记做hanoi（n－1，A，C，B）第二步：把第n个盘子从A杆移到B杆，move(n,

A,

B);第三步：把C杆上的n－1个盘子借助A杆移到B杆，记做hanoi（n－1，C，B，A）16ABC算法描述Void

Hanoi(int

n,int

A,int

B,int

C){if(n>0){Hanoi(n-1,A,C,B);move(n,A,B);Hanoi(n-1,C,B,A);}}考虑移动的次数2.1

递归17汉诺塔移动次数M(1)=1M(n)=2M(n-1)+1=

2[2M(n-2)+1]+1=

22M(n-2)+2+1=

23M(n-3)+22+2+1=……=2iM(n-i)+2i-1+2i-2+……+2+1=2iM(n-i)+2i

-

1令i=

n-1则M(n)=

2n-1

+2n-12.1

递归18一个算法调用另一个算法时，系统需要在运行被调用算法之前先完成三件事：将所有实参指针，返回地址等信息传递给被调用算法；为被调用算法的局部变量分配存储区；将控制转移到被调用算法的入口。2.1

递归19在被调用算法返回调用算法时，系统也相应地要完成三件事：保存被调用算法的计算结果；释放分配给被调用算法的数据区；依照被调用算法保存的返回地址将控制转移到调用算法。2.1

递归20主算法栈块主算法调用递归算法A的栈块算法A的第一层递归调用工作记录算法A的第二层递归调用工作记录TOP2.1

递归21递归小结优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。2.1

递归222.2

分治法的基本思想23例:[找伪币问题]一个装有1

6个硬币的袋子。1

6个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。任务是找出这个伪造的硬币。为了帮助完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。一种方式两两对比，找到轻者，最差比较8次另外一种将16个硬币分成A、B两半；将A放仪器的一边，B放另一边，如果

A袋轻，则表明伪币在A，解子问题A即可，否则，解子问题B。2.2

分治法基本思想24例2－5

金块问题有一个老板有一袋金块。每个月将有两名雇员会因其优异的表现分别被奖励一个金块。按规矩，排名第一的雇员将得到袋中最重的金块，排名第二的雇员将得到袋中最轻的金块。根据这种方式，除非有新的金块加入袋中，否则第一名雇员所得到的金块总是比第二名雇员所得到的金块重。如果有新的金块周期性的加入袋中，则每个月都必须找出最轻和最重的金块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最轻和最重的金块。2.2

分治法基本思想25假设袋中有n

个金块。通过n-1次比较找到最重的金块。找到最重的金块后，可以从余下的n-1个金块中用类似的方法通过n-2次比较找出最轻的金块。这样，比较的总次数为2n-3。n≤2时，识别出最重和最轻的金块，做一次比较。

n＞2时，第一步，把这袋金块平分成两个小袋A和B。第二步，分别找出在A和B中最重和最轻的金块。HA与LA，HB

和LB。第三步，通过比较HA

和HB，可以找到所有金块中最重的；通过比较LA

和LB，可以找到所有金块中最轻的。2.2

分治法基本思想26复杂度设c(n)为比较次数。假设n是2的幂。当n=2时，c(n)=1；当n>2时，c(n)=2c(n/2)+2。当n是2的幂时，可知c(n)=3n/

2-2。使用分而治之方法比逐个比较的方法少用了2

5％的比较次数。2.2

分治法基本思想27Divide

and

Conquer28The

most

well

known

algorithm

designstrategy:

Divide

instance

of

problem

into

twoormore

smaller

instancesSolve

smaller

instances

recursivelyObtain

solution

to

original

(larger)instance

by

combining

these

solutions2.2

分治法的基本思想分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以：把它分成两个或多个更小的问题；分别解决每个小问题；把各小问题的解答组合起来，即可得到原问题的解答。小问题通常与原问题相似，可以递归地使用分而治之策略来解决。2.2

分治法基本思想29原问题子问题1子问题2子问题k子问题1’子问题2’子问题3’相同类型不可再分，直接求解2.2

分治法基本思想3031分治法流程用P表示问题的输入。Divide-and-Conquer(P){if

(|P|<=n0)

Adhoc(P);divide

P

into

smaller

subinstancesP1,P2,···,Pk;for(i=1;i<=k;i++)}2.2

分治法基本思想判断输入规模p是否足够的小解该规模问题的函数分割函数分治解决yi=Divide-and-Conquer

(Pi);return

Merge(y1,···,yk);合并得到最后结果问题应把原问题分为多少个子问题才较适宜？每个子问题是否规模相同或怎样才为适当？2.2

分治法基本思想32分治法计算效率原问题规模——n分成k个子问题，每个规模——n/m设分解阈值n0＝1，Adhoc解规模为1的问题耗费1个单位时间设分解原问题及用Merge将k个子问题的解合并需要f(n)个单位时间T(n)表示分治法的解规模为|P|=n的问题所需的计算时间2.2

分治法基本思想33计算时间分析由上可得O(1)n=1T(n)=kT(n/m)+f(n)

n>1解上式得到logm

n-1T

(n)

=

nlogm

k

+

k

j

f

(n

/

m

j

)j

=02.2

分治法基本思想342.3

二分搜索技术给定已排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x，找到则将其位置赋于变量j中，否则j置-1。如果只允许进行元素间的比较而不允许对它们进行其它的运算，则所设计的算法称为以比较为基础的算法。问题提出35361

线性搜索x:A[2]x:A[n]不成功不成功不成功线性搜索二元比较树如下：x:A[1]不成功2.2

二分搜索技术任何以比较为基础的搜索算法的执行过程都可以用一棵二元比较树来描述。每次可能的比较用一个内顶点表示，对应于不成功的结果有一个外顶点与之对应。A[n-1]<x<A[n]X>A[n]线性算法复杂度该方法没有很好利用已经排好序这个条件，顺序搜索方法平均需要O(n)次比较。2.3二分搜索技术372

二分搜索方法2.3二分搜索技术基本思想取一个中间元素做比较元素，如果x等于它，则结束，如果小于，去左半部查找，否则去右半部搜索将问题表示为：I=(n,a1,…,an,x)选取一个下标k，可得到三个子问题：I1=(k-1,a1,…,ak-1,x)I2=(1,ak,x)I3=(n-k,ak+1,…,an,x)a[k]38二元比较树含9个元素的情况4650287132.3二分搜索技术39二元比较树x:A[(n-1)/2]x:A[(n-3)/4]x:A[(3n-1)/4]x:A[(n-1)/2-1]x:A[(n-1)/2+1]x:A[0]x:A[n-1]不成功不成功不

成功不

成功不

成功不

成功不

成功不

成功2.3二分搜索技术40例2-6

在[9,12,15,27,39]中分别查找27，12，1401234912152739leftrightmidmid

=

(left+right)/2=(0+4)/2=2mid

=(3+4)/2=3912152739rightmid

left查找27成功返回3，left<right912152739rightleftmid9

12

15

27

39查找12成功返回1,left=right查找14失败返回-1,left>rightleft

mid

right912152739leftright41int

middle=2.3二分搜索技术template<classT>int

BinarySearch(

T

a[],

const

T&

x,

int

n){//在a[0]<=a[1]<=···<=a[n-1]中搜索x//如果找到，则返回所在位置，否则返回–1int

left=

0

;

int

right=

n-1

;while(

left<=right

){42(left+right)/2

;if(x==a[middle])

return

middle;if(x>a[middle])

left=

middle+1

;else

right=

middle

–

1;}return

–1;//未找到x}例:-15,-6,0,7,9,23,54,82,101中查找101，-14，822.3二分搜索技术X=101Low

high

mid084586787888OKX=-14Lowhigh

mid08403100010NOX=82Low

high

mid43084586787OK二分搜索所需的空间和时间所需空间存放数组a的地址，还有n，left，right，middle，及x的地址需要存储，共24字节计算时间成功检索的最好情况和不成功检索的最好情况成功检索的平均情况和不成功检索的平均情况成功检索的最坏情况和不成功检索的最坏情况2.3二分搜索技术4445成功检索最好情况和不成功检索最好情况成功检索共有n种不成功检索共有n+1种a012345678元素25679235482101比较次数3234132343334

4

33344成功比较次数不成功比较次数2.3二分搜索技术465028713由图可见，当x在数组A中时，算法在圆形顶点结束；不在A中时，算法在方形顶点结束。因为23≤9<24，所以比较树的叶顶点都在4或5级上出现。因而元素比较的最多次数为4。一般地有：当n

˛

2k

-1,2k

)时，一次成功的折半搜索至多做k次比较，而一次不成功的折半搜索或者做k-1次比较，或者做k次比较。2.3二分搜索技术46二分搜索的时间复杂度最坏情况下的成功检索计算时间Θ(logn)最坏情况下的