资源描述:
《算法导论-课后题答案》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、PartialSolutionsforIntroductiontoalgorithmssecondeditionProfessor:SongYouTA:ShaoWenACKNOWLEDGEMENTCLASSONE:JINZICLASSTWO:LIUHAO,SONGDINMIN,SUNBOSHAN,SUNYANGCLASSFOUR:DONGYANHAO,FANSHENGBO,LULU,XIAODONG,CLASSFIVE:GAOCHEN,WANGXIAOCHUAN,LIUZHENHUA,WANGJIA
2、N,YINGYINGCLASSSIX:ZHANGZHAOYU,XUXIAOPENG,PENGYUN,HOULANCLASS:LIKANG,JIANGZHOU,ANONYMITYThecollatorofthisAnswerSet,SHAOWen,takesabsolutelynoresponsibilityforthecontents.ThisismerelyavaguesuggestiontoasolutiontosomeoftheexercisesposedinthebookIntroducti
3、ontoalgorithmsbyCormen,LeisersonandRivest.Itisverylikelythattherearemanyerrorsandthatthesolutionsarewrong.Ifyouhavefoundanerror,haveabettersolutionorwishtocontributeinsomeconstructivewaypleasesendanEmailtoshao_wen_buaa@163.comItisimportantthatyoutryhar
4、dtosolvetheexercisesonyourown.Usethisdocumentonlyasalastresortortocheckifyourinstructorgotitallwrong.Havefunwithyouralgorithmsandgetasatisfactoryresultinthiscourse.Bestregards,SHAOWenChapteroneExercises1.1-2Otherthanspeed,whatothermeasuresofefficiencym
5、ightoneuseinareal-worldsetting?空间,硬件资源等Exercises1.1-4(classtwo刘浩)Howaretheshortest-pathandtraveling-salesmanproblemsgivenabovesimilar?Howaretheydifferent?相似点:找出最短路径不同点:shortest-path不一定经过所有点,而traveling-salesman得经过所有点Exercises1.2-2Supposewearecomparingim
6、plementationsofinsertionsortandmergesortonthesamemachine.Forinputsofsizen,insertionsortrunsin8n2steps,whilemergesortrunsin64nlgnsteps.Forwhichvaluesofndoesinsertionsortbeatmergesort?插入排序的性能优于合并排序也就是:插入排序所用的步数少:所以有:8n2≤64nlgn⇒n<8??n需要解一下这个超越方程,编个程序很容易得到
7、:2≤n≤43Exercises1.2-3Whatisthesmallestvalueofnsuchthatanalgorithmwhoserunningtimeis100n2runsfasterthananalgorithmwhoserunningtimeis2nonthesamemachine?原理同上题,可列出如下不等式:100n2≤2n解这个不等式(代数法),可求出最小的整数n=15Problems1-1:ComparisonofrunningtimesForeachfunctionf(n)
8、andtimetinthefollowingtable,determinethelargestsizenofaproblemthatcanbesolvedintimet,assumingthatthealgorithmtosolvetheproblemtakesf(n)microseconds.1111111secondminutehourdaymonthyearcenturylgn210626·107236·108∞∞∞∞12361416n10·101296·10∞