算法设计与分析习题与实验题(12.18)

《算法设计与分析》习题

第一章 引 论

习题1-1 写一个通用方法用于判定给定数组是否已排好序。 解答：

Algorithm compare(a,n) Begin J=1;

While (j

While (j=a[j+1]) do j=j+1;

If j=n then return true else return false end if

End if end

习题1-2 写一个算法交换两个变量的值不使用第三个变量。 解答： x=x+y; y=x-y; x=x-y;

习题1-3 已知m,n为自然数，其上限为k（由键盘输入，1<=k<=109）,找出满足条件 (n2-mn-m2)2=1 且使n2+m2达到最大的m、 n。 解答：

m:=k; flag:=0; repeat

n:=m; repeat

l:=n*n-m*n-m*n;

if (l*l=1) then flag:=1 else n:=n-1; until (flag=1) or (n=0) if n=0 then m:=m-1 until (flag=1) or (m=0);

第二章 基础知识

习题2-1 求下列函数的渐进表达式：

3n2+10n; n2/10+2n; 21+1/n; logn3; 10 log3n 。

解答： 3n2+10n=O（n2）， n2/10+2n=O（2n）， 21+1/n=O（1）， logn3=O（log n），10 log3n=O（n）。

习题2-2 说明O(1)和 O(2)的区别。

习题2-3 照渐进阶从低到高的顺序排列以下表达式：n!，

4n,logn,3,20n,2,n2n2/3。

n

2解答：照渐进阶从低到高的顺序为：n!、 3、 4n、n3、20n、logn、2

习题2-4

2（1） 假设某算法在输入规模为n时的计算时间为T(n)?3?2n。在某台计算机

上实现并完成该算法的时间为t秒。现有另外一台计算机，其运行速度为第一台计算机的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？

（2） 若上述算法的计算时间改进为T(n)?n2，其余条件不变，则在新机器上用

t秒时间能解输入规模多大的问题？

（3） 若上述算法的计算时间进一步改进为T(n)?8,其余条件不变，那么在新机

器上用t秒时间能解输入规模多大的问题？

解答：

（1） 设新机器用同一算法在t秒内能解输入规模为n1的问题。因此有

t?3?2?3?2nn1/64，解得n1?n?6。

（2） n12?64n2??n1?8n。

（3） 由于T(n)?常数，因此算法可解任意规模的问题。

习题2-5 XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC公司同类产品的100倍。对于计算复杂性分别为n，n2，n3和n!的各算法，若用ABC公司的计算机能在1小时内能解输入规模为n的问题，那么用XYZ公司的计算机在1小时内分别能解输入规模为多大的问题？

解答：

n??100n。

n?2?100n2??n??10n。

n?3?100n3??3100n?4.64n。

n?!?100n!??n??n?log100?n?6.64。

习题2-6对于下列各组函数f(n)和g(n)，f(n)??(g(n))或f(n)??(g(n))，并简述理由。

（1）f(n)?logn2;g(n)?logn?5。 （2）f(n)?logn2;g(n)?n。

（3）f(n)?n;g(n)?log2n。 （4）f(n)?nlogn?n;g(n)?logn。 （5）f(n)?10;g(n)?log10。 （6）f(n)?log2n;g(n)?logn。 （7）f(n)?2n;g(n)?100n2。 （8）f(n)?2n;g(n)?3n。

解答：

（1）logn2??(logn?5)。

（2）logn2?O(n)。

（3）n??(log2n)。

（4）nlogn?n??(logn)。 （5）10??(log10)。 （6）log2n??(logn)。

（7）2n??(100n2)。

确定f(n)?O(g(n))或

（8）2n?O(3n)。

习题2-7 证明：如果一个算法在平均情况下的计算时间复杂性为?(f(n))，则该算法在最坏情况下所需的计算时间为?(f(n))。

证明：

Tavg(N)???P(I)T(N,I)I?DN?I?DNP(I)maxT(N,I?)I??DN

?T(N,I)**?P(I)I?DN?T(N,I)?Tmax(N)因此，Tmax(N)??(Tavg(N))??(?(f(n)))??(f(n))。

习题2-7 求解下列递归方程: s0=0

sn=2sn-1+2n -1 解答：

步骤: 1应用零化子化为齐次方程，

2解此齐次方程的特征方程， 3由特征根构造一般解，

4再由初始条件确定待定系数，得到解为：

sn?(n?1)2?1n

习题2-8 求解下列递归方程:

h0?2??h1?8 ??h?4h?4hn?1n?2?n解 hn=2n+1(n+1)

第三章 递归与分治策略

习题3-1 下面的7个算法都是解决二分搜索问题的算法。请判断这7个算法的正确性。如果算法不正确，请说明产生错误的原因。如果算法正确，请给出算

法的正确性证明。

public static int binarySearch1(int []a,int x,int n) { int left=0; int right =n-1; while (left<=right) { int middle = ( left + right )/2; if ( x == a[middle]) return middle; if ( x> a[middle]) left = middle; else right = middle; return -1; }

public static int binarySearch2(int []a, int x, int n) { int left = 0; int right = n-1; while ( left < right-1 ) { int middle = ( left + right )/2; if ( x < a[middle]) right = middle; else left = middle; } if (x == a[left]) return left; else return -1 }

public static int binarySearch3(int []a, int x, int n) { int left = 0; int right = n-1; while ( left +1 != right) { int middle = ( left + right)/2; if ( x>= a[middle]) left = middle; else right = middle; } if ( x == a[left]) return left ; else return -1; }

public static int binarySearch4(int []a, int x, int n) { if (n>0 && x>= a[0]) { int left = 0; int right = n-1; while (left < right ) { int middle = (left + right )/2; if ( x < a[middle]) right = middle -1 ;

else left = middle; } if ( x == a[left]) return left; } return -1; }

public static int binarySearch5(int []a, int x, int n) { if ( n>0 && x >= a[0] ) { int left = 0; int right = n-1; while (left < right ) { int middle = ( left + right +1)/2; if ( x < a[middle]) right = middle -1; else left = middle ; } if ( x == a[left]) return left; } return -1; }

public static int binarySearch6(int []a, int x, int n) { if ( n>0 && x>= a[0]) { int left = 0; int right = n-1; while ( left < right) { int middle = (left + right +1)/2; if (x < a[middle]) right = middle – 1; else left = middle + 1; } if ( x == a[left]) return left ; } return -1; }

public static int binarySearch7(int []a, int x, int n) { if ( n>0 && x>=a[0]) { int left = 0; int right = n-1; while ( left < right) { int middle = ( left + right + 1)/2; if ( x < a[middle]) right = middle; else left = middle; }

if ( x == a[left]) return left; } return -1; }

分析与解答：

算法binarySearch1数组段左右游标left和right的调整不正确，导致陷入死循环。

算法binarySearch2数组段左右游标left和right的调整不正确，导致当x=a[n-1]时返回错误。

算法binarySearch3数组段左右游标left和right的调整不正确，导致当x=a[n-1]时返回错误。

算法binarySearch4数组段左右游标left和right的调整不正确，导致陷入死循环。

算法binarySearch5正确，且当数组中有重复元素时，返回满足条件的最右元素。

算法binarySearch6数组段左右游标left和right的调整不正确，导致当x=a[n-1]时返回错误。

算法binarySearch7数组段左右游标left和right的调整不正确，导致当x=a[n-1]时陷入死循环。

习题3-2 设a[0:n?1]是已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。

分析与解答：

改写二分搜索算法如下：

public static boolean binarySearch(int []a, int x, int left, int right, int []ind) { int middle; while ( left <= right ) { middle = (left + right)/2; if (x == a[middle]) { ind[0]=ind[1]=middle; return true;} if (x > a[middle]) left = middle + 1; else right = middle -1; } ind[0] = right; ind[1]=left; return false; }

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

习题3-3 设a[0:n?1]是有n个元素的数组，k(1?k?n?1)是非负整数。试设

计一个算法讲子数组a[0:k?1]与a[k:n?1]换位。要求算法在最坏情况下耗时为

O(n)，且只用到O(1)的辅助空间。

分析与解答：

算法： 三次求反法

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]划分为?n?个子数组，每个子数组中有O(n)个元素。然后递归地对分割后的子数组进行排序，最后将所得到的

?n?个排好序的子数组合并成所要求的排好序的数组

a[0:n?1]。设计一个实现上述策略的合并排序算法，并分析算法的计算复杂性。

分析与解答：

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

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合并n个排好序的数组段。在最坏情况下，算法mergeall

需要O(nlogn)时间。因此上述算法所需的计算时间T(n)满足：

?O(1)T(n)???nT(n)n?1n?1

此递归式的解为：T(n)?O(nlogn)。

习题3-5 设S1,S2,...Sk是整数集合，其中每个集合Si(1?i?k)中整数取值

k范围是1~n，且?Si?n，试设计一个算法，在O(n)时间内将S1,S2,...Sk分别

i?1排序。

分析与解答：

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

习题6 设X[0:n?1]和Y[0:n?1]为两个数组，每个数组中还有n个已排好序的数。试设计一个O(logn)时间的算法，找出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[i1]?medi?aY[nj2]。同理若X[i1]?Y[j2]，则Y[j2]?median?X[i1]。

设

m1?(i1?j1)/2，

m2?(i2?j2)/2，

则

m1?m2?(i1?j1)/2?(i2?j2)/2?i1?(j1?i1)/2?i2?(j2?i2)?i1?i2?(j1?i1)/2?(j2?i2)/2由于j1?i1?j2?i2，故(j1?i1)/2?(j2?i2)/2?j1?i1?j2?i2。 因此m1?m2?i1?i2?j1?i1?i2?j1?i1?i2?j2?i2?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]?Y[m2]时，设median2是X[i1:m1]和Y[m2:j2]的中位数，类似地有median?median2。

通过以上讨论，可以设计出找出两个子数组X[i1:j1]和Y[i2:j2]的中位数median的算法。

（2） 设在最坏情况下，算法所需的计算时间为T(2n)。由算法中m1和m2的选

取策略可知，在递归调用时，数组X和Y的大小都减少了一半。因此，T(2n)满足递归式：

?O(1)T(2n)???T(n)?O(1)n?cn?c

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

习题3-6 Gray码是一个长度为2n的序列。序列中无相同元素，每个元素都是长度为n位的（0，1）串，相邻元素恰好只有1位不同。用分治策略设计一个算法，对任意的n构造相应的Gray码。

分析与解答：

考察n?1,2,3的简单情形。

n=1 0 n=2 00 11 n=3 000 110 001 111 011 101 010 100 01 10 1 设n位Gray码序列为G(n)以相反顺序排列的序列为G?1(n)。从上面的简单情形可以看出G(n)的构造规律：G(n?1)?0G(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个串存储在a[i]中。 完成计算之后，由out输出Gray码序列。 public static void out(int n) { int m=1<

第四章 动态规划

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

用数组b[0:n?1]记录以a[i],0?i?n为结尾元素的最长递增子序列的长度。序列a的最长递增子序列的长度为max{b[i]}。易知，b[i]满足最优子结构性

0?i?n质，可以递归地定义为：

b[0]?1,b[i]?max{b[k]}?1

0?k?ia[k]?a[i]据此将计算b[i]转化为i个规模更小的子问题。 按此思想设计的动态规划算法描述如下： public static int LISdyna() {

int i, j, k; for ( i=1, b[0]=1; i

static int maxL(int n) { int temp=0; for ( int i= 0; i temp) temp=b[i]; return temp; }

上述算法LISdyna按照递归式计算出b[0:n?1]的值，然后由maxL计算出序列a的最长递增子序列的长度。从算法LISdyna的二重循环容易看出，算法所需的计算时间为O(n2)。

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

nmaxn?ci?1iixi xi为非负整数，1?i?n

?ai?1xi?b试设计一个解此问题的动态规划算法，并分析算法的计算复杂性。

分析与解答：

该问题是一般情况下的背包问题，具有最优子结构性质。 设所给背包问题的子问题：

imaxi?ck?1kkxk

?ak?1xk?j的最优值为m(i,j)，即m(i,j)是背包容量为j，可选择物品为1，2，…，i时背包问题的最优值。由背包问题的最优子结构性质，可以建立计算m(i,j)的递归式如下：

?max{m(i?1,j),m(i,j?ai)?ci}m(i,j)???m(i?1,j)j?ai0?j?ai

m(0,j)?m(i,0);m(i,j)???,j?0。

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

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

分析与解答：

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

设所给的输入为W?0,?i?0,?i?0,1?i?n。不妨设0??1??2?...??n。由题意知?1??2?...??n?0。由此可知

?i?i??i?1?i?1，1?i?n?1

贪心选择性质： 当?1?W时问题无解。

当?1?W时，存在0-1背包问题的一个最优解S?{1,2,...,n}使得1?S。

事实上，设S?{1,2,...,n}使0-1背包问题的一个最优解，且1?S。对任意i?S，取

Si?S?{1}?{i}，则Si满足贪心选择性质的最优解。

习题5-2 Fibonacci序列的Huffman编码

试证明：若n个字符的频率恰好是前n个Fibonacci数，用贪心法得到它们的Huffman编码树一定为一棵“偏斜树”。

分析与解答： 频率恰好是前8个Fibonacci数的哈夫曼编码树如图所示。

2 1 1 4 2 7 12 5 3 33 54 21 20 8 13

本文来源：https://www.bwwdw.com/article/0bua.html