![Bi t畉p Bi 2.
Bi 1: T鱈nh th畛i gian th畛c hi畛n c畛a c叩c o畉n ch動董ng tr狸nh sau:
a) T鱈nh t畛ng c畛a c叩c s畛
Sum := 0;
for i:=1 to n do begin
readln(x);
Sum := Sum + x;
end;
b) T鱈nh t鱈ch hai ma tr畉n vu担ng c畉p n C = A*B:
for i := 1 to n do
for j := 1 to n do begin
c[i,j] := 0;
for k := 1 to n do c[i,j] := c[i,j] + a[i,k] * b[k,j];
end;
Bi 2: Gi畉i c叩c ph動董ng tr狸nh 畛 quy sau v畛i T(1) = 1 v
a) T(n) = 3T(n/2) + n
b) T(n) = 3T(n/2) + n2
c) T(n) = 8T(n/2) + n3
Bi 3: Gi畉i c叩c ph動董ng tr狸nh 畛 quy sau v畛i T(1) = 1 v
a) T(n) = 4T(n/3) + n
b) T(n) = 4T(n/3) + n2
c) T(n) = 9T(n/3) + n2
Bi 4: Gi畉i c叩c ph動董ng tr狸nh 畛 quy sau v畛i T(1) = 1 v
a) T(n) = T(n/2) + 1
b) T(n) = 2T(n/2) + logn
c) T(n) = 2T(n/2) + n
d) T(n) = 2T(n/2) + n2
Bi 5: Cho m畛t m畉ng n s畛 nguy棚n 動畛c s畉p th畛 t畛 tng. Vi畉t hm t狸m m畛t s畛 nguy棚n
trong m畉ng 坦, n畉u t狸m th畉y th狸 tr畉 v畛 TRUE, ng動畛c l畉i tr畉 v畛 FALSE.
S畛 d畛ng hai ph動董ng ph叩p t狸m ki畉m tu畉n t畛 v t狸m ki畉m nh畛 ph但n. V畛i m畛i ph動董ng ph叩p h達y
vi畉t m畛t hm t狸m v t鱈nh th畛i gian th畛c hi畛n c畛a hm 坦.
Bi 6: T鱈nh th畛i gian th畛c hi畛n c畛a gi畉i thu畉t 畛 quy gi畉i bi to叩n Th叩p H n畛i v畛i n
t畉ng?](https://image.slidesharecdn.com/bitu1eadpbi2-150427150308-conversion-gate02/85/Bai-tap-lap-trinh-1-320.jpg)
Bai tap lap trinh
- 1. Bi t畉p Bi 2. Bi 1: T鱈nh th畛i gian th畛c hi畛n c畛a c叩c o畉n ch動董ng tr狸nh sau: a) T鱈nh t畛ng c畛a c叩c s畛 Sum := 0; for i:=1 to n do begin readln(x); Sum := Sum + x; end; b) T鱈nh t鱈ch hai ma tr畉n vu担ng c畉p n C = A*B: for i := 1 to n do for j := 1 to n do begin c[i,j] := 0; for k := 1 to n do c[i,j] := c[i,j] + a[i,k] * b[k,j]; end; Bi 2: Gi畉i c叩c ph動董ng tr狸nh 畛 quy sau v畛i T(1) = 1 v a) T(n) = 3T(n/2) + n b) T(n) = 3T(n/2) + n2 c) T(n) = 8T(n/2) + n3 Bi 3: Gi畉i c叩c ph動董ng tr狸nh 畛 quy sau v畛i T(1) = 1 v a) T(n) = 4T(n/3) + n b) T(n) = 4T(n/3) + n2 c) T(n) = 9T(n/3) + n2 Bi 4: Gi畉i c叩c ph動董ng tr狸nh 畛 quy sau v畛i T(1) = 1 v a) T(n) = T(n/2) + 1 b) T(n) = 2T(n/2) + logn c) T(n) = 2T(n/2) + n d) T(n) = 2T(n/2) + n2 Bi 5: Cho m畛t m畉ng n s畛 nguy棚n 動畛c s畉p th畛 t畛 tng. Vi畉t hm t狸m m畛t s畛 nguy棚n trong m畉ng 坦, n畉u t狸m th畉y th狸 tr畉 v畛 TRUE, ng動畛c l畉i tr畉 v畛 FALSE. S畛 d畛ng hai ph動董ng ph叩p t狸m ki畉m tu畉n t畛 v t狸m ki畉m nh畛 ph但n. V畛i m畛i ph動董ng ph叩p h達y vi畉t m畛t hm t狸m v t鱈nh th畛i gian th畛c hi畛n c畛a hm 坦. Bi 6: T鱈nh th畛i gian th畛c hi畛n c畛a gi畉i thu畉t 畛 quy gi畉i bi to叩n Th叩p H n畛i v畛i n t畉ng?
- 2. Bi 7: X辿t 畛nh ngh挑a s畛 t畛 h畛p ch畉p k c畛a n nh動 sau: Cn k = 1 n畉u k=0 ho畉c k=n Cn k = Cn k-1 +Cn-1 k-1 n畉u k>0 v k<n a) Vi畉t m畛t hm 畛 quy 畛 t鱈nh s畛 t畛 h畛p ch畉p k c畛a n. T鱈nh th畛i gian th畛c hi畛n c畛a gi畉i thu畉t n坦i tr棚n.