loadingind[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背包问题，设计一个有效算法找出最优解，并说明算法的正确性。 分析与解答：