算法导论15-16 答案

算法导论15-16 答案

ID:34567734

大小:54.61 KB

页数:8页

时间:2019-03-08

算法导论15-16 答案_第1页
算法导论15-16 答案_第2页
算法导论15-16 答案_第3页
算法导论15-16 答案_第4页
算法导论15-16 答案_第5页
资源描述:

《算法导论15-16 答案》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、西安电子科技大学计算机学院霍红卫SolutionstoChapters15&1615.1-1(5-1)ShowhowtomodifythePRINT-STATIONSproceduregivenbelowtoprintoutthesituationsinincreasingorderofstationnumber.PRINT-STATIONS(l,n)1i←l*2print“line”i“,station”n3forj←ndownto24doi←li[j]5print“line”i“,station”j–1Solution:RECURSIVE-PRINT-STATIONS(l,i,

2、j)1ifj=0thenreturn2RECURSIVE-PRINT-STATIONS(l,li[j],j–1)3print“line”i“,station”jToprintoutallthestations,callPRINT-STATIONS(l,l*,n)15.2-1(5-5)Findanoptimalparenthesizationofamatrix-chainproductwhosesequenceofdimensionsis<5,10,3,12,5,50,6>.Solution:Solvethematrixchainorderforaspecificproblem.Th

3、iscanbedonebycomputingMATRIX-CHAIN-ORDER(p)wherep=<5,10,3,12,5,50,6>orsimplyusingtheequation:0ifi=j,m[i,j]=min{min[i,k]+m[k+1,j]+ppp}ifi

4、Them-table:m[1,2]=150,m[2,3]=360,m[3,4]=180,m[4,5]=3000,m[5,6]=1500m[1,3]=330,m[2,4]=330,m[3,5]=930,m[4,6]=1860m[1,4]=405,m[2,5]=2430,m[3,6]=1770m[1,5]=1655,m[2,6]=1950m[1,6]=2010Thes-table:s[1,2]=1,s[2,3]=2,s[3,4]=3,s[4,5]=4,s[5,6]=5s[1,3]=2,s[2,4]=2,s[3,5]=4,s[4,6]=4s[1,4]=2,s[2,5]=2,s[3,6=4

5、s[1,5]=4,s[2,6]=2s[1,6]=2Finally,wehave(A1A2)((A3A4)(A5A6)).15.4-1(5-9)DetermineanLCSof<1,0,0,1,0,1,0,1>and<0,1,0,1,1,0,1,1,0>.Solution:yj010110110xi000000000010↑01↖←1↖↖11←1↖↖11←1001↖↑1↖2←2←2↖2←2←2↖2001↖↑1↖2↑2↑2↖3←3←3↖310↑12↖↑2↖3↖3↑3↖↖44←4001↖↑2↖3↑3↑3↖4↑4↑4↖510↑12↖↑3↖↖44↑4↖↖55↑5001↖↑2↖3↑4↑4↖5↑

6、5↑5↖610↑12↖↑3↖↖45↑6↖↖66↑6Alongestcommonsequencecouldbe<1,0,0,1,1,0>asillustratedbelow(therecouldbesomeotherLCS’,ifwechoose←insteadof↑whenc[i–1,j]=c[i,j–1]):X:<–,1,0,–,–,0,1,0,1,0,1>Y:<0,1,0,1,1,0,1,–,1,0,–>SotheLCSis100110.15.5-3(5-15)Supposethatinsteadofmaintainingthetablew[i,j]wecomputedthev

7、alueofw[i,j]directlyfromequation(5-5)inline8ofOPTIMAL-BSTandusethiscomputedvalueinline10.HowwouldthischangeaffecttheasymptoticrunningtimeofOPTIMAL-BST?jjw(i,j)=∑pl+∑ql(5-5)l=il=i−1OPTIMAL-BST(p,q,n)1fori←1ton+12doe[i,i-1]←qi-13w[i,i-1]←

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。