链接：https://pan.baidu.com/s/1VDf1XhyJlS6MS7QkfZ2Peg 

提取码：qiza 

 

Introduction

 

1.4The general way to do this is to write a procedure with heading

 

void processFile( String fileName );

 

which opens fileName, does whatever processing is needed, and then closes it. If a line of the form

 

#include SomeFile

 

is detected, then the call

 

processFile( SomeFile );

 

is made recursively. Self-referential includes can be detected by keeping a list of files for which a call to

 

processFile has not yet terminated, and checking this list before making a new call to processFile.

 

1.5public static int ones( int n )

{

if( n < 2 ) return n;

return n % 2 + ones( n / 2 );

}

 

1.7(a) The proof is by induction. The theorem is clearly true for 0 < X  1, since it is true for X = 1, and for X < 1, log X is negative. It is also easy to see that the theorem holds for 1 < 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 Y = 1 + log(Y/2)< 1 + Y/2 < Y/2 + Y/2  Y, where the first inequality follows by the inductive hypothesis.

(b) Let 2X = A. Then AB = (2X)B = 2XB. Thus log AB = XB. Since X = log A, the theorem is proved.

 

1.8(a) The sum is 4/3 and follows directly from the formula.

 

 

(b)

 

S  1  2  3 

 

Subtracting the first equation from the second gives

 

4 42 43

 

 

3S  1  1  2 

4 42

 

. By part (a), 3S = 4/3 so S = 4/9.

 

 

 

(c)

 

S  1  4  9 

 

Subtracting the first equation from the second gives

 

4 42 43

 

 

3S  1   3   5   7  Rewriting, we get 3S  2 i   1 . Thus 3S = 2(4/9) + 4/3 = 20/9. Thus S =

 

 

4 42 43

 

i0 4

 

i0 4

 

20/27.

 



(d) Let SN =  iN . Follow the same method as in parts (a) – (c) to obtain a formula for SN in terms of SN–1,

i0

 

SN–2,..., S0 and solve the recurrence. Solving the recurrence is very difficult.

 

N N  N / 21

 

1.9

 

 1   1 

 

 1  ln N  ln N / 2  ln 2.

 

i N / 2 i1

 

i1

 

 

1.10 24 = 16  1 (mod 5). (24)25  125 (mod 5). Thus 2100  1 (mod 5).

 

1.11 (a) Proof is by induction. The statement is clearly true for N = 1 and N = 2. Assume true for N = 1, 2, ... , k.

 

k  1 k

 

Then

 

 Fi   Fi  Fk 1. By the induction hypothesis, the value of the sum on the right is Fk+2 – 2 + Fk+1 =

 

i1 i1

 

Fk+3 – 2, where the latter equality follows from the definition of the Fibonacci numbers. This proves the claim for N = k + 1, and hence for all N.

(b)As in the text, the proof is by induction. Observe that  + 1 = 2. This implies that  –1 +  –2 = 1. For N = 1 and N = 2, the statement is true. Assume the claim is true for N = 1, 2, ... , k.

Fk 1  Fk  Fk 1

 

by the definition, and we can use the inductive hypothesis on the right-hand side, obtaining

 

Fk 1   k    k1

 1 k 1   2 k 1

Fk 1  ( 1   2 ) k 1   k 1

 

and proving the theorem.

 

(c)See any of the advanced math references at the end of the chapter. The derivation involves the use of generating functions.

N N N

1.12 (a) (2i  1)  2i  1 = N(N + 1) – N = N2.

 

i1

 

i1

 

i1

 

 

(b) The easiest way to prove this is by induction. The case N = 1 is trivial. Otherwise,