绠楁硶璁捐�′笌鍒嗘瀽鐜嬫檽涓� - 鐧惧害鏂囧簱

ind[0] = right; ind[1]=left; return false; }

返回的ind[1]是小于x的最大元素位置，ind[0]是大于x的最小元素的位置。

习题3-3 设a[0:n-1] 是有n个元素的数组， 是非负整数。试设计一个算法讲子数组 与 换位。要求算法在最坏情况下耗时为 ，且只用到 的辅助空间。 分析与解答： 算法： 三次求反法

Algorithm exchange(a, k, n); Begin

Inverse(n,0,k-1); inverse(n,k,n-1)； inverse（n,0,n-1） End.

Algorithm inverse(a, i, j); Begin

h=[(j-i+1)/2] ; For k=0 to h-1 do

Begin x=a[i+k]; a[i+k]=a[j-k]; a[j-k]= x end ; end

习题3-4 如果在合并排序算法的分割步中，讲数组a[0;n-1] 划分为 [根号2】个子数组，每个子数组中有 个元素。然后递归地对分割后的子数组进行排序，最后将所得到的 个排好序的子数组合并成所要求的排好序的数组 。设计一个实现上述策略的合并排序算法，并分析算法的计算复杂性。 分析与解答：

实现上述策略的合并排序算法如下：

public static void mergesort(int []a, int left ,int right) {

if (left < right ) {

int j = (int) Math.sqrt(right –left+1); if (j>1) {

for (int i=0; i

mergeall(a,left,right); } }

其中，算法mergeall合并根号n 个排好序的数组段。在最坏情况下，算法mergeall需要O（nlogn) 时间。因此上述算法所需的计算时间 T(n)满足： T(n)=O(1),n<=1

T(n)=根号n*T(根号n),n>1 T(n)=O(nlogn)

此递归式的解为： 。

习题3-5 设S1,S2...Sk 是整数集合，其中每个集合 中整数取值范围是 ，且 ，试设计一个算法，在 时间内将 分别排序。 分析与解答：

用桶排序或基数排序算法思想可以实现整数集合排序。

习题3-6 设X[0:n-1] 和Y[0:n-1] 为两个数组，每个数组中还有n个已排好序的数。试设计一个 时间的算法，找出X和Y的2n个数的中位数。 分析与解答： （1） 算法设计思想

考虑稍一般的问题：设X[i1:j1] 和y[i2;j2] 是X和Y的排序好的子数组，且长度相同，即j1-i1=j2-i2 。找出这两个数组中2(i1-j1+1) 个数的中位数。

首先注意到，若X(i1)<=Y(j2) ，则中位数median满足X(i)<=median<=Y(j2) 。同理若X(i1)>=Y(j2) ，则Y(j2)<=median<=X(i1) 。

设m1=(i1+j1)/2,m2=(i2+j2)/2 ，则m1+m2=i1+i2+(j1-i1)/2+(j2-i2)/2 由于j1-i1=j2-i2 ，故(j1-i1)/2+(j2-i2)/2=j2-i2。 因此m1+m2=i1+j2 。

当X(m1)=Y(m2) 时，median=X(m1)=Y(m2) 。

当X(m1)>Y(m2) 时，设median1 是X(m1:j1) 和Y(j2:m2) 的中位数，则median=median1 。 当X(m1)

（2） 设在最坏情况下，算法所需的计算时间为T(2n) 。由算法中m1 和m2 的选取策略可知，在递归调用时，数组X和Y的大小都减少了一半。因此，T(2n) 满足递归式： T(2n)=(1),n<=1 T(2n)=T(n)+O(1),n>=c

解此递归方程可得：T(2n)=O(logn) 。

习题3-7 Gray码是一个长度为2^n 的序列。序列中无相同元素，每个元素都是长度为n位的（0，1）串，相邻元素恰好只有1位不同。用分治策略设计一个算法，对任意的n构造相应的Gray码。 分析与解答： 考察 的简单情形。 n=1 0 1 n=2 00 01 11 10 n=3

000 001 011 010 110 111 101 100

设n位Gray码序列为G(n) 以相反顺序排列的序列为G^-1(n)。从上面的简单情形可以看出G(n) 的构造规律：G(n+1)=OG(n)1G^-1(n) 。

注意到G(n) 的最后一个n位串与G^-1(n) 的第1个n位串相同，可用数学归纳法证明G(n) 的上述构造规律。由此规律容易设计构造G(n) 的分治法如下。 public static void Gray(int n) {

if ( n == 1) { a[1] = 0; a[2] = 1; return; }

Gray(n-1);

for ( int k = 1<< ( n - 1), i = k; i > 0; i--) a[2*k-i+1]=a[i] + k; }

上述算法中将n位（0，1）串看做是二进制整数，第i个串存储在 中。 完成计算之后，由out输出Gray码序列。 public static void out(int n) {

int m=1<

for (int i=1; i<=m; i++) {

String str=Integer.toBinaryString(a[i]); int s=str.length();

for ( int j=0; j

System.out.println(); }

第四章 动态规划

习题4-1 设计一个 时间的算法，找出由n个数组成的序列的最长单调递增子序列。 分析与解答：

引入一个数组b，使b[i]为已扫描部分的长度为ｉ的升序子序列的最小终值。 按此思想设计的动态规划算法描述如下： j:=0; b[0]:=-maxint; FOR i:=1 TO n DO IF a[i]>b[j] THEN

BEGIN j:=j+1; b[j]:=a[i]; END ELSE

BEGIN k:=1;

while a[i]>b[k] DO k:=k+1; b[k]:=a[i]; END;

习题4-2 考虑下面的整数线性规划问题： 为非负整数，

试设计一个解此问题的动态规划算法，并分析算法的计算复杂性。 分析与解答：

该问题是一般情况下的背包问题，具有最优子结构性质。 设所给背包问题的子问题：max∑CkXk(1..i)∑AkXk<=j

的最优值为m(i,j) ，即 m(i,j)是背包容量为j，可选择物品为1，2，…，i时背包问题的最优值。由背包问题的最优子结构性质，可以建立计算m(i,j） 的递归式如下： m(i,j)=max{m(i-1,j),m(i,j-ai)+ci} j>=ai,

m(i,j)=m(i-1,j),0<=j,ai m(0,j)=m(i,0);m(i,j)=-*,j<0

按此递归式计算出的m(n,b) 为最优值。算法所需的计算时间为O(nb) 。

习题4-3 给定一个由n行数字组成的数字三角形如图3-2所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。 分析与解答：

记f(uij)为至ij元素的最大路径值, aij ：元素(i,j)之值。 递归式:

F(uij)=max{f(ui-1,j)+aij, f(ui-1,j+1)+aij} (i=1,…n， j=1,…i)

经过一次顺推，便可求出从顶至底n个数的n条路径（这n条路径为至底上n个数的n个最大总和的路径），求出这n个总和的最大值，即为正确答案。 数据结构:

a[i,j].val: 三角形上的数字，

a[i,j].f: 由（1，1）至该点的最大总和路径的总和值。 type node=record val, f: integer; end;

var a:array [1.. maxn, 1..maxn] of node; procedure findmax; begin

a [1,1]. f :=a[1,1].val; for i:=2 to n do for j:=1 to i do begin a[i,j]. f:=-1;

if (j<>1) and (a [i-1,j-1].f+a[i,j].val > a [i,j].f) then a[i,j]. f:=a [i-1,j-1]. f+a[i,j].val; if (j<>i) and(a [i-1,j].f+a[i,j].val > a[i,j].f) then a[i,j]. f:=a[i-1,j]. f+a[i,j]. val end; max:=1; for i:=2 to n do

if a[n,i]. f> a[n, max] .f then max:=i; writeln (a [n, max]. f) end;

第五章 贪心算法

习题5-1 特殊的0-1背包问题

若在0-1背包问题中，各物品依重量递增排列时，其价值恰好依递减序排列。对这个特殊的0-1背包问题，设计一个有效算法找出最优解，并说明算法的正确性。 分析与解答：