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

PAGE5

第5章 中位数和任一顺序数的选择

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

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

Max-Min(A[p..r],Max,Min)

ifp=r

then Max?A[p]

Min?A[p]

else q??(p+r)/2?

Max-Min(A[p..q],Max1,Min1)

Max-Min(A[q+1,r],Max2,Min2)

Max=max{Max1,Max2}

Min=min{Min1,Min2}

endif

End

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

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

T(1)=0

对任意的n，我们可用归纳法证明T(n)=2n–2。

归纳基础：

因为T(1)=0和T(2)=2，所以T(n)=2n–2在n=1或n=2时正确。

归纳步骤：

假设当n=1，2，…，k-1(k?3)时，有T(n)=2n–2。当n=k时，由递推关系和归纳假设有以下推导：

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

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

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

=2n–2。

归纳成功。

证明任一基于比较的排序算法在最好情况下至少需要(n-1)次比较才能把一个n个数字的序列排好。我们假定这n个数字中可以有相等的数字，但必须通过比较才能确定两数是否相等。

证明1: 如果n个数字的序列被排好序的话，那么序列中任一顺序数便被确定。所以，如果有一个基于比较的排序算法能在最好情况下用少于(n-1)次比较把一个n个数字的序列排好的话，我们就可以在最好情况下用少于(n-1)次比较把最大数找到。这与定理5.2矛盾。

证明2: 我们用反证法证。假设有这么个算法，它用少于(n-1)次比较把某个n个数字的序列排好。我们用一个图来描述这个排序过程。这个图有n个顶点，分别代表这n个数。如果算法在两个数之间作一比较，我们则在代表这两个数的顶点之间画一条边。显然，这个图的边数少于(n-1)，因此是个不连通的图。它含有几个连通分支。那么，这个排序算法不可能正确。这是因为，如果我们把不含最大数的一个连通分支中数字都加上一个很大数，然后让算法去排序的话，那么算法不会察觉到这个变动。因此，每次进行的比较结果与对原序列进行的比较结果完全一样。这样，算法对修改后的序列不可能正确排序。所以，任一基于比较的排序算法在最好情况下至少需要(n-1)次比较才能把一个n个数字的序列排好。

根据5.4.3节的讨论，在n个数字中同时找出最大和第2大的数字需要的比较次数不超过n+?lgn?-2。请给出一个简单例子说明。

解：下面的锦标赛图标明了在找最大数时各结点上比较的胜者。显然，第一轮总共进行了4次比较后找到最大数9。当最大数9被找到后，第2轮找第2大数可从9到根的路径上找到。它一定是存在于在这路径上第一轮比较的败者中，即数字7，2，6中找到。所以这一轮需要2次比较。注意，在第二轮中，9变成了-?，所以在结点X处，7不需比较而取胜。所以总共需要n+?lgn?-2=5+?lg5?-2=6次比较。

6

6

2

9

7

5

9

9

9

6

X

假设我们要从有n个不同的数字的集合A[1..n]中找出1000个与A[1..n]的中位数距离最近的数。我们假定这1000个数中包括中位数本身，并假设n1000。两个数x和y之间的距离定义为它们差的绝对值|x–y|。请设计一个快速而方便的O(n)算法。

解：算法的伪码如下，其正确性从注解可知。

Numbers-closest-to-median(A[1..n],1000)

x?Select(A[1..n],n,?n/2?) //先找出中位数x

fori?1ton

B[i]?|A[i]–x|

endfor

Build-Max-Heap(B[1..1000],1) //用B[i]中头1000个数建堆。

fori?1001ton

ifB[i]B[1]

then B[1]?B[i]

Max-Heapify(B[1..1000],1)

endif

endfor

forj?1to1000