算法设计技巧与分析习题参考答案.docx
《算法设计技巧与分析习题参考答案.docx》由会员分享，可在线阅读，更多相关《算法设计技巧与分析习题参考答案.docx（19页珍藏版）》请在冰点文库上搜索。
算法设计技巧与分析习题参考答案
习题4.13
A1
A2
A3
A4~A3各2次；A2
各1次;
（b）元素最大交换次数：
A9〜A5
最多3次；A1最多4次最多共需16次元素交换
4.13另解：
考虑第i个节点，其子节点为2i，则最多可交换1次;若子节点有子节点22i,则最多可交换2次；若….•有子节点i疋k,则最多可交换k次；
因此有
i泌<19
求出满足上述不等式的最大的k值即可。
i=1时,k=4;
i=2时,k=3;
i=3或4时,k=2;
i=5~9时,k=1;
因此最多交换4+3+22+1）5=16次
6.5用分治法求数组A[1…n]元素和，算法的工作空间是多少?
输入：
数组A[1-n]
输出：
数组的所有元素之和刀A[i]{i=1…n}
SUM（low,high）
1.ifhigh=lowthen
2.returnA[low]
3.else
4.midJ（low+high）/2
5.s1JSUM（low,mid）
6.s2JSUM（mid+1,high）
7.returns1+s2
8.endif
工作空间：
mid~（logn）,s1&s2~
（1）（后序遍历树，不断释放空间，故为常数
（1）），总的工作空间为（logn）.
6.6用分治法求元素x在数组A中出现的频次。
freq（A[low,high],x）
1.ifhigh=lowthen
2.ifA[low]=xthen
3.return1
4.else
5.return0
6.endif
7.else
8.midJ（low+high）/2
9.flJfreq（A[low,mid]）
10.f2Jfreq（A[mid+1,high]）
11.returnf1+f2
12.endif
复杂度:
T（n）=T（n/2）+T（n/2）〜2T（n/2）（设2k《＜2k+1）=-=2kT（n/2k）=2kT
（1）=n
6.16修改后的MERGESORT算法
n1ifnm
最小比较次数C（n）2C（n/2）n/2ifnm
令n/2k=m^2,展开可知：
T（n）=2kT（n/2k）+kn-（2k-1）
=n/m>m（m-1）/2+nlog（n/m）-n/m+1
=n（m-1）/2+nlog（n/m）-n/m+1
若T（n）=（nlogn）,其中表达式有nm,nlogn,nlogm,n/m等.
有n/m则须有mlogn.可令c=1,贝UmWogn.另一方面，
C（n）=2kC（n/2k）+kn/2=n/m（惦-1）+（n/2）log（n/m）=（nlogn）
6.35split（A[low,...high]）
1.xJA[low]//备份为x
2.while（low3.
--high;
++low;
while（low0）
4.A[low]JA[high]
5.while（lowvhigh&&A[low]O）
6.A[high]JA[low]
7.}
8.A[low]Jx//这时,low=high
k
7.3动态规划法计算二项式系数Cn，并分析其时间复杂度。
1.fori—Iton
2.C[i,0]—1;C[i,i]—1
3.endfor
4.fori—2ton
5.forj—1toi-1/min（k,i-1）〃例如计算C[6,2]
6.C[i,j]—C[i-1,j-1]+C[i-1,j]
7.end
8.endfor
9.returnC[n.k]
复杂度分析：
ni-1
c
i2j1
n
ckcck（n1）O（nk）
8.5硬币的面值为1,2,4,8,…，2,要兑换的值n<2k+1，用贪心算法解这个问题，要求算法复杂度为O（logn）
输入：
k+1个不同硬币的面值，其中包括单位币（面值为1）输出：
若要兑换的值n,给出各个面值硬币的数目num[0…k]
1.将k+1个不同的面值按递增顺序排列，记为Value[0...k]
2.num[0…k]T
3.forjJkdownto0
4.num[j]Jn/Value[j]
5.nJn-num[j]>A/alue[j]
6.endfor
7.returnnum[0…k]
8.16修改Dijkstra算法，使它找出最短路径和它的长度。
1.X={1};Y—V1}；入[1]Jpre[1]J0;
2.fory
J2ton
3.
ify相邻于1thenX[y]Jlength[1,y]
4.
5.
elseX[y]Jendif
6.endfor
7.forj
J1t-o1n
8.
令y€Y,使得X[y为最小的
9.
10.
XJXU{y}YJY-{y}
11.
for每条边（y,w）
12.
13.
14.
14.
ifw€YandX[y]+length[y,w]X[w]JX[y]+length[y,w]pre[w]Jyendif
15.endfor
16.endfor
输出最短路径
voidPrintPath（intnode）//输出格式为1^—>node
{if（node==1）print（“1”）;
else{
PrintPath（pre[node]）;//先递归再输出
print（J；node）;
13.2考虑3着色问题，给出一个算法判断一图G=（V,E）的3着色向量c[1…n]是否是合法的。
输入：
图G=（V,E），向量c[1…n]
输出：
flag=true若合法着色；否则flag=false
2.foriJ1ton
3.ifc[i]K0
4.for（i,j）€E
5.ifc[j]◎dc[j]=c[i]
6.returnfalse;
7.endif
8.endfor
9.endif
10.endfor
11.returntrue
13.3考虑3着色问题，给出一个算法判断一图G=（V,E）的3着色向量c[1…k]是否是部分的。
输入：
图G=（V,E），向量c[1…k]
输出：
true若着色是部分的；否则输出false
2.foriJ1to
3.ifc[i]K0
4.for（i,j）€E
5.ifjwkndc[j]半0andc[j]=c[i]
6.returnfalse;
7.endif
8.endfor
9.endif
10.endfor
11.returntrue
13.10设计一个回溯算法来生成数字1,2,…,n的所有排列。
输入：
数字1,2,-,n
输出：
数字1,2，…的所有排列c[1,…向量
1.forkJ1ton
2.c[k]J0
3.endfor
5.kJ1
6.whilek>1
7.whilec[k]-卒n
8.
c[k]Jc[k]+1
9.
ifc为合法的thenoutputc
（andgoto12）
10.
elseifc为部分解thenk
Jk+1
11.
endwhile
12.
c[k]J0
13.
kJk-1
14.endwhile
14.7对二分查找算法进行随机化，即每次迭代时，随机选择剩下的位置代替搜索空间减半，假设在low与high之间每个位
置被选中的概率都是相同的。
比较这种随机化算法与二分查找的表现。
输入：
n个元素的升序数组A[1…n]和元素x
输出：
若x=A[j],1jn,则输出j,否则输出0
1.lowJ1;highJn;jT
2.while（lowhigh）and（j=0）
3.midJ（low+high）/2/midJrandom（low,high）
4.ifx=A[mid]thenjJmid
5.elseifx6.elselowjmid+1
7.endwhile
8.returnj
时间复杂度分析
将每次迭代时随机选择的位置记为k,且在low与high之间每
个位置被选中的概率都是1/n，期望比较次数C（n）满足
1）C（nk）
1n
C（n）—1C（k
nk1
1）C（nk）
1n
—C（k
nk1
1
n-1
c（j）
j1
n-1
-C（j）
nj1
2n-1
-C（j）
nj1
（1）
（2）
nC（n）=n+2{C
（1）+C
（2）+…+C（n-2）+C（n-1）}（n-1）C（n-1）=n-1+2{C
（1）+C
（2）+…+C（n-2）}
（2）-
（1）nC（n）-（n-1）C（n）=1+2C（n-1）
nC（n）=1+（n+1）C（n-1）
nC（n）=
C（n）
1+（n+1）C（n-1）
-山C（n1）nn
n-1
n-1C（n-2）
12c（n2）
nn（n1）n1
（*）
-n1
nn（n1）
-n1
nn（n1）
土唱C（n-3）
n1
（n1）（n2）
^^C（n3）
n2
（*）
C（n）1n
n+1
n（n-1）
fn
n1
2）
n1
J2）
n
n（n-1）
1
1
n（n-1）
1
n
2
n1
2
n1
2
n1
n-1n-1
n1〜C（n
n1
n11
2）
n-1
彳c+C（n-3）
n1n-2n-2
n1（n1）（n1）C（n3）（n1）（n2）（n1）（n2）
*）
2
n1
3
n2
n-12n1、—
+C（n3）
（n-1）（n-2）（n-1）（n-2）n2
122n1〜-
——+——-C（n3）
n-2n-2n-1n2
*）
IL4C（n3）
n2
AnA
C（n）———C（n1）
nn
n1
k（n2）
口C（n3）
n2
n-3
5
（1）
2
nA
--〃{QC
（1）1}
2
n1
2
n1
2
n
何将C（n）=n代入推导过程，以验证其正确性）因此，随机化拟二分查找的时间复杂度为O（n），二分查找的时间复杂度为O（logn）。
随机化方法的效率反而比二分查找低，其原因在于…
14.10设L=xi,X2,…,x是一个元素序列，其中元素x恰好出现k次（Kk<）n我们要找到一个j，使得xj=x。
考虑重复执行下面的过程直到找到x为止。
生成一个1到n之间色随机数i，
并检查是否Xi=X。
在平均情况下，这种方法和线性方法查找哪一种方法快？
请说明。
解：
（1）随机查找的情况
不妨设第ii,i2,…,k个元素等于X，记I二{iI,i2,…,k},|I|=k,贝yP{i€I}=k/n，记p=k/n,q=1-p，则查找长度的数学期望
E（ASL）=px1+qxpx2+…-+qpxi+…=1/p二n/k
（2）线性查找的情况
k
E（ASL）1
n
（1
（1
（1
n
k、
（1
（1
n
k
（1-）（1
i1n
k2（1n1七）...（1n1
=）...（1n1
七）…（1
n1
与（1
n
亠
k2
«）
k2
-）i
ni2n（i1）
丄）丄3...
n1n2
—（nk）
k1
k
（1）1（nk1）
k1
k
其中，分母=n（n-1）（n-2）…（n-i+1）=n!
/（n-i）!
分子=（n-k）（n-k-1）…（nk-i+2）k激=（n-k）!
kW（n-k・i+1）!
则通项可写为
（nk）!
ki
（nki1）!
（nk）!
（ni）!
k（k1）!
n!
/（ni）!
n!
（nki1）!
（k1）!
（nk）!
（ni）!
k!
i血
n!
（nki1）!
（k1）!
C：
于是，
nk1iC：
：
n1
i1C；k1
■■■
Ck1Cn1
Ck1
Cn2
Ck
Cn
1
3...
Ck
Ck1
，另一方面
Ck1
Cn1
Ck1
Cn2
Ck
Cn
1
3...
k1
Ck
Ck1
Ck1
k1
Cn
CkCk
Cn1Cn2
Ck
Cn3
■■■
Ckk1
Ck
Ck，
（*）其中
Ck
Cn1
k1
Cn2
k1
Cn3
■■■
k1
Ck
k1
Ck1
Ck
Cn2
Ck1
Cn3
■■■
k1
Ck
Ck1
Ck1
Ck
Ck1
k1
Ck
Ck1
Ck1
Ckk
Ck1
Ck1
将以上各式（除了*式）相加，即可得到
nk1
k1即有i1iCni
总结：
随机查找e（asl）n，线性查找E（ASL）
因为=nkoT^f）0，故线性查找更快。
14.16修改14.7节的随机抽样算法，使得它不再需要布尔数组
S[1…n]，假设n比m大得多，比如n>m2.
解：
算法设计如下:
1.kT
2.whilek3.rJrandom（1,n）
4.iJk-1
5.whilei>1andr半A[i]
6.iJi-1
7.endwhile
8.ifi=0
9.A[k]Jr
10.kJk+1
11.endif
12.endwhile
复杂度分析如下每次随机生成一个新元素r,要查找r是否已经出现在已经选定的数字中
设生成第i个有效随机数时，平均要产生E（Xi）次，则复杂度
容易证明，
（E-U）J_（Z（E-U）l
（LEEIu
Lu:
u
LLU
（LUJ）
u:
Iu
LLU
LLU
LLU
Liu
LLU
dVJLU
（uru）l
（uru）l
14.16另解：
算法设计思路如下
生成一个[1,n]之间的随机数r，互换X[n]和X[r];
再生成一个[1,n-1]之间的随机数r，互换X[n-1]和X[r];…
再生成一个[1,n-m+1]之间的随机数r，互换X[n・m+1]和X[r];返回X[n-m+1…n],即为随机选择的m个数。
好处：
不需要重复产生随机数；不需要额外空间。
1.forijndownto-m+1
2.rjrandom（1,i）
3.X[r]<-->X[i]
4.endfor
5.returnX[n-m+1…n]
时间复杂度：
（m）.空间复杂度：
（1）.
升级会员 