Schoolof Computer Science and 7ccheologg 1958 算法基础习题课2 助教:刘倩玉 NCAA Network Computing and Advanced Algorithm Laboratory
算法基础习题课2 助教：刘倩玉 1
Schoolof Co buten Seicuac aud technology Page210151-1 。证明 T(n)=1+∑=0T0)T(0)=1 T(n)=2n 数学归纳法 a)T(0)成立 b)假设T(k)成立,推导T(k+1)成立 20221
Page210 15.1-1 2021/2/11 3 。证明 • 𝑻 𝒏 = 𝟏 + 𝒋=𝟎 𝒏−𝟏 𝑻(𝒋) 𝑻 𝟎 = 𝟏 • 𝑻 𝒏 = 𝟐 𝒏 ➢ 数学归纳法 a) T(0)成立 b) 假设T(k)成立，推导T(k+1)成立
Schoolof Co buten Seicuac aud technology Page22615.4-1 。求<1,0,0,1,0,1,0,1>和<0,1,0,1,1,0,1,1,0>的一个LCS >LCS:<1.0.0.1.1.0> <0.1.0.1.0.1> 20221
Page226 15.4-1 2021/2/11 4 。求<1, 0, 0, 1, 0, 1, 0, 1>和<0, 1, 0, 1, 1, 0, 1, 1, 0>的一个LCS ➢ LCS：<1, 0, 0, 1, 1, 0> <0, 1, 0, 1, 0, 1>
Schoolof Co buten Seicuac aud technology Page22615.4-2 设计伪代码,利用完整的表c及原始序列X=<x1,x2,…,xm>和 Y=<yl2y2,,yn>重构LCS,要求运行时间为O(m+n)不能使用表b。 解: 1. PRINT-LCS(C,X, Y,i,J) 2345 return if xli== Y[jl PRINT-LCS(C,X,Y,i-1,j-1) print xIi 789 else if cli-1,j]>=c[i,j-11 PRINT-LCS(C,X,Y,i-1,j) else PRINT-LCS(C, X,Y,i,j-1) 20221
Page226 15.4-2 2021/2/11 5 。设计伪代码，利用完整的表c及原始序列X = <x1, x2, …, xm>和 Y=<y1,y2,…,yn>重构LCS，要求运行时间为O(m+n),不能使用表b。 解： 1. PRINT-LCS(c,X,Y,i,j) 2. if i == 0 or j == 0 3. return 4. if X[i] == Y[j] 5. PRINT-LCS(c,X,Y,i-1,j-1) 6. print X[i] 7. else if c[i-1,j] >= c[i,j-1] 8. PRINT-LCS(c,X,Y,i-1,j) 9. else 10. PRINT-LCS(c,X,Y,i,j-1)
Schoolof Co buten Seicuac aud technology Page22615.4-2 设计伪代码,利用完整的表c及原始序列X=<x1,x2,…,xm>和 Y=<yl2y2,,yn>重构LCS,要求运行时间为O(m+n)不能使用表b。 解: PRINT-LCS(c, X,i,j) if i==0 or return 举例:X=010110110 4 fc[i-1,j-1]==c[i,j]-1 Y=1001 PRINT-LCS(c, X,i-1,J-1) c8,3]=3即100 6 print xli] c9,4]=4即1001 else if cli-1,J== cli,j c[9,4]-1=c[9-1,41]=c[8,3=3 8 PRINT-LCS(C,,i-1,J) 但Xg]的‘0’并不是LCS的构成元素 else 19 PRINT-LCS(,X,i,j-1) 20221
Page226 15.4-2 2021/2/11 6 。设计伪代码，利用完整的表c及原始序列X = <x1, x2, …, xm>和 Y=<y1,y2,…,yn>重构LCS，要求运行时间为O(m+n),不能使用表b。 解： 1. PRINT-LCS(c,X,i,j) 2. if i == 0 or j == 0 3. return 4. if c[i-1,j-1] == c[i,j] - 1 5. PRINT-LCS(c,X,i-1,j-1) 6. print X[i] 7. else if c[i-1,j] == c[i,j] 8. PRINT-LCS(c,X,i-1,j) 9. else 10. PRINT-LCS(c,X,i,j-1) 举例：X = 0 1 0 1 1 0 1 1 0 Y = 1 0 0 1 c[8, 3] = 3 即 1 0 0 c[9, 4] = 4 即 1 0 0 1 c[9, 4] – 1 = c[9-1, 4-1] = c[8, 3] = 3 但X[9]的‘0’并不是LCS的构成元素