计算机算法基础 第2版 习题及答案 第2章 .docx

PAGE19

第2章 分治法

用分治法设计一个算法找出数组A[1..n]中的最大的数，并分析所需的比较次数。

解：以下用分治法的算法是作用在数组A[p,r]上的，p≤r。在调用该算法时，只须置p=1，r=n即可。

Maximum(A[p..r],Max)

ifp=r

thenMax?A[p]

exit

endif

q??(p+r)/2?

Maximum(A[p..q],Max1)

Maximum(A[q+1,r],Max2)

Max?max{Max1,Max2}

End

我们用T(n)表示数组中数字间的比较次数，则有以下递推关系：

T(n)=T(?n/2?)+T(?n/2?)+1

T(1)=0

我们用归纳法证明T(n)=n–1。

归纳基础：

因为T(1)=0，所以T(n)=n–1显然在n=1时正确。

归纳步骤：

由递推关系和归纳假设我们有以下推导：

T(n)=T(?n/2?)+T(?n/2?)+1

=(?n/2?-1)+(?n/2?-1)+1

=?n/2?+?n/2?-1

=n–1。

归纳成功。

用分治法设计一个算法同时找出数组A[1..n]中的最大和第二大的数，n?2，并分析所需的比较次数。

解：以下分治法的算法是作用在数组A[p,r]上的,p≤r。在调用该算法时，只须置p=1，r=n即可。

Largest-and-second-largest(A[p..r],L,S)//L和S分别为最大和第二大的数

ifp=r

thenL?A[p]

S?-? //表示没有第二大数

endif

q??(p+r)/2?

Largest-and-second-largest(A[p..q],L1,S1)

Largest-and-second-largest(A[q+1..r],L2,S2)

ifL1L2

thenL?L1

S?max{L2,S1}

elseL?L2

S?max{L1,S2}

endif

End

我们用T(n)表示数组中数的比较次数，则有以下递推关系：

T(n)=T(?n/2?)+T(én/2ù)+2

T(1)=0

它的解可用主方法得到。

令n=2k，则有

T(n)=2T(n/2)+2

=Q(n)。

如果想知道更为准确的常数因子，我们可用归纳法证明T(n)=2n–2。

归纳基础：

因为T(1)=0所以T(n)=2n–2显然在n=1时正确。

归纳步骤：

由递推关系和归纳假设有以下推导：

T(n)=T(?n/2?)+T(én/2ù)+2

=(2?n/2?-2)+(2én/2ù-2)+2

=(2n-4)+2

=2n–2。

归纳成功。

假设GOOGLE公司在过去n天中的股票价格记录在数组A[1..n]中。我们希望从中找出两天的价格，其价格的增幅最大。也就是说，我们希望找到A[i]和A[j]，ij，使得M=A[j]–A[i]的值最大，即M=max{A[j]–A[i]|1?ij?n}。试设计一个复杂度为O(nlgn)或更好的分治算法。

解：以下算法找出数组A[p..r]中序号i和j使得M=A[j]–A[i]的值最大，p?ij?r。

Divide-Conquer-Max-profit(p,r,m,i,j)//假设r3p

ifp=r

thenm?-￥

exit //m=-￥表示只有一天的价格

endif

q=?(p+r)/2?

Divide-Conquer-Max-profit(p,q,ml,il,jl)

Divide-Conquer-Max-profit(q+1,r,mr,ir,jr)

FindxsuchthatA[x]=min(A[p],…,A[q])

FindysuchthatA[y]=max(A[q+1],…,A[r])

mc?A[y]–A[x]

ifmc3max{ml,mr}

thenm?mc

i?x

j?y

elseifml3mr

thenm?ml

i?il

j?jl

elsem?mr

i?ir

j?jr

endif

endi