《数据结构与算法分析:C语言描述(原书第2版)》的习题解答

解答所对应的图书的具体信息如下: 中文名:数据结构与算法分析:C语言描述(原书第2版) 英文名:Data Structures and Algorithm Analysis in C: Second Edition 作者:(美)维斯 著,冯舜玺 译 出版社:机械工业出版社

Chapter1:Introduction

1.3Becauseofround-offerrors,itiscustomarytospecifythenumberofdecimalplacesthatshouldbeincludedintheoutputandroundupaccordingly.Otherwise,numberscomeoutlookingstrange.Weassumeerrorcheckshavealreadybeenperformed;theroutineSeparate islefttothereader.CodeisshowninFig. 1.1.

Thegeneralwaytodothisistowriteaprocedurewithheading

voidProcessFile(constchar*FileName);

whichopensFileName, doeswhateverprocessingisneeded,andthenclosesit.Ifalineoftheform

#includeSomeFile

isdetected,thenthecall

ProcessFile(SomeFile);

ismaderecursively.Self-referentialincludescanbedetectedbykeepingalistof lesforwhichacalltoProcessFile hasnotyetterminated,andcheckingthislistbeforemakinganewcalltoProcessFile.

1.5(a)Theproofisbyinduction.Thetheoremisclearlytruefor0 < X ≤ 1,sinceitistrueforX = 1,andforX < 1,log X isnegative.Itisalsoeasytoseethatthetheoremholdsfor1 < X ≤ 2,sinceitistrueforX = 2,andforX < 2,log X isatmost1.Supposethetheoremistrueforp < X ≤ 2p (wherep isapositiveinteger),andconsiderany2p < Y ≤ 4p (p ≥ 1).Thenlog Y = 1 + log (Y / 2) < 1 + Y / 2 < Y / 2 + Y / 2 ≤ Y ,wherethe rstine-qualityfollowsbytheinductivehypothesis.

(b)Let2X = A .ThenA B = (2X )B = 2XB .Thuslog A B = XB .SinceX = log A ,thetheoremisproved.

1.6(a)Thesumis4/3andfollowsdirectlyfromtheformula.

123 . . . 23 . . . _______ + ___(b)S = __ + _ + + .4S = 1+ + .Subtractingthe rstequationfrom44424342

21___thesecondgives3S = 1 + __ + 2 + . . . .Bypart(a),3S = 4/ 3soS = 4/ 9.44

4949161______________(c)S = __ + 2 + 3 + . . . .4S = 1 + + 2 + 3 + . . . .Subtractingthe rstequa-444444573________tionfromthesecondgives3S = 1+ + 2 + 3 + . . . .Rewriting,weget444∞i∞1______3S = 2Σi + Σi .Thus3S = 2(4/ 9) + 4/ 3 = 20/ 9.ThusS = 20/ 27.

i =04i =04

∞i N (d)LetSN = Σ___.Followthesamemethodasinparts(a)-(c)toobtainaformulaforSN i 4i =0intermsofSN 1,SN 2,...,S 0andsolvetherecurrence.Solvingtherecurrenceisverydif cult.1.4

你可能喜欢

  • 数据结构与算法答案
  • 数据结构c语言版复习
  • 数据结构严蔚敏习题答案
  • 计算机网络基础教程
  • C语言经典算法
  • 组织行为学答案
  • 经济法试题及答案
  • 数据结构c语言版期末试题

《数据结构与算法分析:C语言描述(原书第2版)》的习题解答相关文档

最新文档

返回顶部