第一章
15
P
1-3. 最大公约数为 1。快 1414 倍。
主要考虑循环次数, 程序 1-2 的 while 循环体做了 10 次,程序 1-3 的 while 循环体做了 14141 次( 14142-2
循环)
若考虑其他语句,则没有这么多,可能就 601 倍。
第二章
32
P
2-8.(1)画线语句的执行次数为
log n
。
(log )n
。划线语句的执行次数应该理解为一格整体。
( 2)画线语句的执行次数为
1 1 1
( 1)( 2)
1
6
j
n i
i j k
n n n
。
3
( )n
。
( 3)画线语句的执行次数为 n 。
( )n
。
( 4)当 n 为奇数时画线语句的执行次数为
( 1)( 3)
4
n n
,
当 n 为偶数时画线语句的执行次数为
2
( 2)
4
n
。
2
( )n
。
2-10. ( 1 ) 当 1n 时 ,
2 2
5 8 2 5n n n , 所 以 , 可 选 5c ,
0
1n 。 对 于
0
n n ,
2 2
( ) 5 8 2 5f n n n n ,所以,
2 2
5 8 2 ( )n n n 。
( 2) 当 8n 时,
2 2 2 2
5 8 2 5 2 4n n n n n
,所以,可选 4c ,
0
8n 。对于
0
n n ,
2 2
( ) 5 8 2 4f n n n n ,所以,
2 2
5 8 2 ( )n n n 。
( 3) 由( 1)、(2)可知,取
1
4c
,
2
5c
,
0
8n
,当
0
n n
时,有
2 2 2
1 2
5 8 2c n n n c n
,所
以
2 2
5 8 2 ( )n n n 。
2-11. (1) 当 3n 时,
3
log logn n n ,所以 ( ) 20 log 21f n n n n,
3
( ) log 2g n n n n 。可
选
21
2
c
,
0
3n 。对于
0
n n ,
( ) ( )f n cg n
,即
( ) ( ( ))f n g n
。注意:是 f(n)和 g(n)的关系。
( 2) 当
4n
时,
2
log logn n n ,所以
2 2
( ) / logf n n n n ,
2 2
( ) logg n n n n 。可选
1c
,
0
4n
。对于
0
n n
,
2
( ) ( )f n n cg n
,即
( ) ( ( ))f n g n
。
( 3)因为
log log(log )
( ) (log )
n n
f n n n
,
( ) /log log 2
n
g n n n n
。当 4n 时,
log(log )
( )
n
f n n n
,
评论0
最新资源