《MarkAllenWeiss数据结构与算法分析课后习题答案1.docx》由会员分享，可在线阅读，更多相关《MarkAllenWeiss数据结构与算法分析课后习题答案1.docx（3页珍藏版）》请在三一文库上搜索。
1、Chapter 1: Introduction1.3 Because of round-otf errors, it is customary to specify the number of decimal places that should be included in the output and round up accordingly. Otherwise, numbers come out looking strange. We assume error checks have already been performed; the routine Separate is lef
2、t to the reader. Code is shown in Fig. 1.1.1.4 The general way to do this is to write a procedure with headingvoid ProccssFilc( const char *Fi)cNamcwhich opens FileNume. does whatever processing is needed, and then closes it. If a line of the forminclude SomeFileis delected, then the callProcessFile
3、( SomeFile );is made recursively. Self-rcfcrential includes can be detected by keeping a list of tiles for which a call to ProcessFile has not yet terminated, and checking this list before making a new call to ProcessFile.1.5(a) The proof is by induction. The theorem is clearly true for 0X L since i
4、t is true for X = 1, and for X h log X is negative. It is also easy to see that the theorem holds for X 2. since it is true for X = 2. and for X 2. log X is at most 1. Suppose the theorem is true for p X 2p (where p is a positive integer), and consider any 2p Y 4p (p 1). Then log X = 1 + log (Y /2)
5、1 + Y/2Y/2 + Y/2Y where the first inequality follows by the inductive hypothesis.(b) Let 2* =A. Then Au =(2X)H =2XJf. Thus ogAB =XB. Since X =log4, the theorem is proved.(a) Tlw sum is 4/3 and follows directly from the formula.(b) 5 = -7 + T + T + .45=+ . Subtracting the first equation from4444*the
6、second gives 35 = l + + + . By part (ah 3S = 4/ 3 so S =4/9. 44*14949|6(c) 5= + 7 +r+.45 = I+ r + r+ .Subtractingthefirstequa-44-444- 4tionfromthesecondgives3S= l+-y + A + +.Rewriting,wegete44243o o35 =2-y+ -7. Tlius 35 = 2(4/9)+ 4/3 = 2(V9. ThusS=2(V27. 1=0(d) Let SN = 227. Follow the same method a
7、s in parts (a) - (c) to obtain a formula for SN i-0 4，in terms of SN_i, ，and solve the recurrence. Solving the recurrence is very difficult，double RoundUp( double N. int DccPlaccs ) Iint i;double AmountToAdd = 0.5;fort i = 0: i DccPlaccs; i+ ) AmountToAdd /= 10; return N + AmounlToAdd:void PrintFrac
8、honPart( double FractionParl. int DevPIaces ) (int i. Adigit;fort i = 0; i DecPlaces; i+ ) FractionPart *= 10: ADigit = InlPart( FractionPart); PrintDigit( Adigit);FractionPart = DecPiirK FractionPart);void PrintReal( double N，int DecPlaces ) (int IntegerPart;double FractionPart:if( N 0)putchart*.*)
9、;PrintFractionPart( FractionPart, DccPlaccs);Fig. 1.1.N 1 N 1 pV/2-IJ 11.7 十=十- z - = ln/V - In N/2nl./-LAT/2J 1卜 I 1/-I11.8 2*= 16= I (mod 5). (24)25 s l25 (mod 5). Thus 2,0e 1 (mod 5).1.9 (a) Proof is by induction. The statement is clearly true for N = I and N =2. Assume true4+1 kfor N = L 2. k. T
10、hen= 2L 尸，+ 厂By the induction hypothesis, the value of the/Isum on the right is FA+2 - 2 + F*+i =- 2. where the latter equality follows from thedefinition of the Fibonacci numbers. This proves the claim for N = k + h and hence for all N.(b) As in (he text the proof is by induction. Observe that 0 +
11、I = This implies that 0一 1 +(r2 = 1. For N = 1 and N =2. the statement is true. Assume the ckiim is true for N = L Z k.=+F*-Iby the delinition and we can use the inductive hypothesis on the right-hand side, obtaining f川 w-1o-V+,+0-+,么1拎-| +WW1 and proving the theorem.(c) See any of the advanced math
12、 references at the end of the chapter. The derivation involves the use of generating functions.JVNNi1.10(a) (2i-l) = 2； - l=AT(JV+l)-JV=jV2./I/-I i-l(b) Tlw easiest way to prove this is by induction. The case /V = I is trivial. Otherwise.p = (iV+l)3 +=.+1p+= 0V+2t+(/v+,)卜2 + 4/V +4(N+Ir(+2)2(N+1X/V+2)2222