没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
















. 4S 1 2 3 .
4
42
. 4S 1 4 9 16 .
4
4243
CHAPTER 1
Introduction
1.4 The 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.5 public 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 2
X
= A. Then A
B
= (2
X
)
B
= 2
XB
. Thus log A
B
= 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
4
2
4
3
3S 1
1
2
4
4
2
. By part (a), 3S = 4/3 so S = 4/9.
(c)
S
1
4
9
Subtracting the first equation from the second gives
4
4
2
4
3

.
4
i i
3S 1
3
5
7
Rewriting, we get 3S 2
i
1
. Thus 3S = 2(4/9) + 4/3 = 20/9. Thus S =
4
4
2
4
3
i0
4
i0
4
20/27.
(d) Let S
N
=
i
N
. Follow the same method as in parts (a) – (c) to obtain a formula for S
N
in terms of S
N–1
,
i0
S
N–2
,..., S
0
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
i1
1.10 2
4
= 16 1 (mod 5). (2
4
)
25
1
25
(mod 5). Thus 2
100
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 F
k+2
– 2 + F
k+1
=
i1 i1
F
k+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.
F
k 1
F
k
F
k 1
by the definition, and we can use the inductive hypothesis on the right-hand side, obtaining
F
k
1
k
k
1
1
k 1
2
k 1
F
k
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 = N
2
.
i1 i1 i1
(b) The easiest way to prove this is by induction. The case N = 1 is trivial. Otherwise,
ii

N 1 N
i
3
(N 1)
3
i
3
i1
(N
1)
3
i1
N
2
(N 1)
2
4
2
N
2
(N 1)
4
(N 1)
2
N
2
4N 4
(N 1)
4
(N 1)
2
(N 2)
2
2
2
(N
1) (N
2)
2
2
N 1
2
i
i1

N
log N
L
CHAPTER 2
Algorithm Analysis
2.1 2/N, 37, , N, N log log N, N log N, N log(N
2
), N log
2
N, N
1.5
, N
2
, N
2
log N, N
3
, 2
N/2
, 2
N
.
N log N and N log (N
2
) grow at the same rate.
2.2 (a) True.
(b)
False. A counterexample is T
1
(N) = 2N, T
2
(N) = N, and f (N) = N.
(c)
False. A counterexample is T
1
(N) = N2, T
2
(N) = N, and f (N) = N2.
(d)
False. The same counterexample as in part (c) applies.
2.3 We claim that N log N is the slower growing function. To see this, suppose otherwise. Then, N
would grow slower than log N. Taking logs of both sides, we find that, under this assumption,
/ log N log N
grows slower than log log N. But the first expression simplifies to
log N . If L = log N,
then we are claiming that
grows slower than log L, or equivalently, that
2
L grows slower than log
2
L. But we know that log
2
L = o(L), so the original assumption is false, proving the claim.
2.4
Clearly, logk
1
N
o(logk
2
N ) if k
1
< k
2
, so we need to worry only about positive integers. The claim is
clearly true for k = 0 and k = 1. Suppose it is true for k < i. Then, by L’Hôpital’s rule,
lim
N
log
i
N
N
lim
i
N
log
i
1
N
N
The second limit is zero by the inductive hypothesis, proving the claim.
2.5 Let f(N) = 1 when N is even, and N when N is odd. Likewise, let g(N) = 1 when N is odd, and N when N is
even. Then the ratio f(N)/g(N) oscillates between 0 and inf.
2.6 (a) 2
2
N
(b) O(log log D)
2.7 For all these programs, the following analysis will agree with a simulation:
(I) The running time is O(N).
(II) The running time is O(N
2
).

N
(III) The running time is O(N
3
).
(IV) The running time is O(N
2
).
(V) j can be as large as i
2
, which could be as large as N
2
. k can be as large as j, which is N
2
. The running time
is thus proportional to NN
2
N
2
, which is O(N
5
).
(VI) The if statement is executed at most N
3
times, by previous arguments, but it is true only O(N
2
)
times (because it is true exactly i times for each i). Thus the innermost loop is only executed O(N
2
) times.
Each time through, it takes O(j
2
) = O(N
2
) time, for a total of O(N
4
). This is an example where multiplying
loop sizes can occasionally give an overestimate.
2.8 (a) It should be clear that all algorithms generate only legal permutations. The first two algorithms have tests
to guarantee no duplicates; the third algorithm works by shuffling an array that initially has no duplicates, so
none can occur. It is also clear that the first two algorithms are completely random, and that each permutation
is equally likely. The third algorithm, due to R. Floyd, is not as obvious; the correctness can be proved by
induction. See J. Bentley, “Programming Pearls,” Communications of the ACM 30 (1987), 754–757. Note
that if the second line of algorithm 3 is replaced with the statement
swap References( a[i], a[ ran dint( 0, n–1 ) ] );
then not all permutations are equally likely. To see this, notice that for N = 3, there are 27 equally likely ways
of performing the three swaps, depending on the three random integers. Since there are only 6 permutations,
and 6 does not evenly divide 27, each permutation cannot possibly be equally represented.
(b) For the first algorithm, the time to decide if a random number to be placed in a[i] has not been used
earlier is O(i). The expected number of random numbers that need to be tried is N/(N – i). This is obtained
as follows: i of the N numbers would be duplicates. Thus the probability of success is (N – i)/N. Thus the
expected number of independent trials is N/(N – i). The time bound is thus
N 1
Ni
N 1
N
2
N 1
2
2
N
1
2
i
0
i
0
N
N
i0
O(N
j 1
log N )
The second algorithm saves a factor of i for each random number, and thus reduces the time bound to
O(N log N) on average. The third algorithm is clearly linear.
(c,d) The running times should agree with the preceding analysis if the machine has enough memory. If not,
the third algorithm will not seem linear because of a drastic increase for large N.
N
N
1
剩余63页未读,继续阅读
资源评论

千里梦江山
- 粉丝: 0
- 资源: 1

上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助

会员权益专享
安全验证
文档复制为VIP权益,开通VIP直接复制
