![畛 13 1/2
畛 thi tuy畛n sinh cao h畛c ngnh c担ng ngh畛 th担ng tin
M担n: Ng担n ng畛 l畉p tr狸nh
Th畛i gian 180 ph炭t - Kh担ng 動畛c s畛 d畛ng ti li畛u
Bi 1. Cho d達y s畛 nguy棚n d動董ng kh叩c nhau t畛ng 担i m畛t A=a1,a2,,an, n<=100
v ho叩n v畛 P = [p1,p2,,pn] c畛a c叩c s畛 [1,2,,n]
H達y vi畉t c叩c ch動董ng tr狸nh con th畛c hi畛n c叩c c担ng vi畛c sau 但y:
1. 畛c c叩c d達y s畛 A, P t畛 bn ph鱈m v ki畛m tra t鱈nh 炭ng 畉n c畛a d畛 li畛u nh畉p
vo.
2. T畉o ra m畛t n畛i dung m畛i c畛a d達y A=a[p1],,a[pn] m kh担ng d湛ng m畉ng
ph畛 no kh叩c ngoi A v P 達 cho.
V鱈 d畛, v畛i d達y A=8,6,2,1,3,4 v ho叩n v畛 P=5,4,6,2,1,3 ta c坦 n畛i dung m畛i
c畛a d達y A=3,1,4,6,8,2. Vi畉t hai ph動董ng 叩n l畉p v 畛 quy.
3. V畛i d達y A 達 cho, h達y x叩c 畛nh m畛t ho叩n v畛 no 坦 P sao cho
a[p1]<=<=a[pn].
V鱈 d畛, v畛i d達y A nh動 tr棚n, ta c坦 P=4,3,5,6,2,1 th畛a m達n t鱈nh ch畉t tr棚n. Vi畉t
hai ph動董ng 叩n 畛 quy v l畉p.
Bi 2. Khai b叩o ki畛u c畛a m畛t danh s叩ch tuy畉n t鱈nh m坦c n畛i v m畛t c但y nh畛 ph但n
nh動 sau:
Type tro=^ptu;
Ptu=record
Gtri:integer;
Tiep:tro;
End;
Pointer=^nut;
Nut=record
Value:integer;
Trai,phai:pointer;
End;
Var ds:tro;
Goc:point;
Vi畉t c叩c ch動董ng trinh con th畛c hi畛n c叩c c担ng vi畛c sau 但y:
1. Procedure Dungcay(ds:tro; var goc:pointer);
Nh畉m x但y d畛ng c但y nh畛 ph但n t狸m ki畉m c坦 g畛c 動畛c tr畛 b畛i goc tr棚n c董 s畛
c叩c ph畉n t畛 c畛a danh s叩ch ds 達 cho. Gi畉 thi畉t r畉ng c叩c ph畉n t畛 c畛a danh
s叩ch c坦 gi叩 tr畛 kh叩c nhau t畛ng 担i m畛t.
V鱈 d畛, v畛i danh s叩ch c叩c ph畉n t畛:
8 3 9 4 1 10
Ta x但y d畛ng 動畛c c但y nh畛 ph但n t狸m ki畉m nh動 sau:
Tr狸nh by: Tr畉n Hoi Nh但n](https://image.slidesharecdn.com/ctdl-deso13-150427150951-conversion-gate02/85/Ctdl-de-so-13-1-320.jpg)
Ctdl de so 13
- 1. 畛 13 1/2 畛 thi tuy畛n sinh cao h畛c ngnh c担ng ngh畛 th担ng tin M担n: Ng担n ng畛 l畉p tr狸nh Th畛i gian 180 ph炭t - Kh担ng 動畛c s畛 d畛ng ti li畛u Bi 1. Cho d達y s畛 nguy棚n d動董ng kh叩c nhau t畛ng 担i m畛t A=a1,a2,,an, n<=100 v ho叩n v畛 P = [p1,p2,,pn] c畛a c叩c s畛 [1,2,,n] H達y vi畉t c叩c ch動董ng tr狸nh con th畛c hi畛n c叩c c担ng vi畛c sau 但y: 1. 畛c c叩c d達y s畛 A, P t畛 bn ph鱈m v ki畛m tra t鱈nh 炭ng 畉n c畛a d畛 li畛u nh畉p vo. 2. T畉o ra m畛t n畛i dung m畛i c畛a d達y A=a[p1],,a[pn] m kh担ng d湛ng m畉ng ph畛 no kh叩c ngoi A v P 達 cho. V鱈 d畛, v畛i d達y A=8,6,2,1,3,4 v ho叩n v畛 P=5,4,6,2,1,3 ta c坦 n畛i dung m畛i c畛a d達y A=3,1,4,6,8,2. Vi畉t hai ph動董ng 叩n l畉p v 畛 quy. 3. V畛i d達y A 達 cho, h達y x叩c 畛nh m畛t ho叩n v畛 no 坦 P sao cho a[p1]<=<=a[pn]. V鱈 d畛, v畛i d達y A nh動 tr棚n, ta c坦 P=4,3,5,6,2,1 th畛a m達n t鱈nh ch畉t tr棚n. Vi畉t hai ph動董ng 叩n 畛 quy v l畉p. Bi 2. Khai b叩o ki畛u c畛a m畛t danh s叩ch tuy畉n t鱈nh m坦c n畛i v m畛t c但y nh畛 ph但n nh動 sau: Type tro=^ptu; Ptu=record Gtri:integer; Tiep:tro; End; Pointer=^nut; Nut=record Value:integer; Trai,phai:pointer; End; Var ds:tro; Goc:point; Vi畉t c叩c ch動董ng trinh con th畛c hi畛n c叩c c担ng vi畛c sau 但y: 1. Procedure Dungcay(ds:tro; var goc:pointer); Nh畉m x但y d畛ng c但y nh畛 ph但n t狸m ki畉m c坦 g畛c 動畛c tr畛 b畛i goc tr棚n c董 s畛 c叩c ph畉n t畛 c畛a danh s叩ch ds 達 cho. Gi畉 thi畉t r畉ng c叩c ph畉n t畛 c畛a danh s叩ch c坦 gi叩 tr畛 kh叩c nhau t畛ng 担i m畛t. V鱈 d畛, v畛i danh s叩ch c叩c ph畉n t畛: 8 3 9 4 1 10 Ta x但y d畛ng 動畛c c但y nh畛 ph但n t狸m ki畉m nh動 sau: Tr狸nh by: Tr畉n Hoi Nh但n
- 2. 畛 13 2/2 8 3 9 1 4 10 2. Procedure cay_NP_min(ds:tro;var goc:pointer); Nh畉m x但y d畛ng c但y ngh畛 ph但n t狸m ki畉m c坦 g畛c 動畛c tr畛 b畛i goc, t動ng 畛ng v畛i m畛t c但y ho叩n v畛 no 坦 c畛a c叩c ph但n t畛 trong danh s叩ch ds sao cho 畛 cao c畛a c但y nh畉n 動畛c l nh畛 nh畉t. Bi 3. Tr棚n 挑a c坦 m畛t t畛p vn b畉n (TEXT) c坦 t棚n l VB.TXT. M畛i d嘆ng c坦 畛 di kh担ng qu叩 80, g畛m nhi畛u t畛. M畛i t畛 l m畛t d達y li棚n ti畉p c叩c k箪 t畛 動畛c ph但n c叩ch b畉ng d畉u tr畉ng, d畉u ph畉y, d畉u ch畉m, d畉u ch畉m ph畉y, d畉u hai ch畉m, d畉u ch畉m than, d畉u h畛i, d畉u ngo畉c 董n 坦ng v d畉u ngo畉c 董n m畛. L畉p ch動董ng tr狸nh con th畛c hi畛n c叩c c担ng vi畛c sau 但y: 1. 畛c c叩c d嘆ng c畛a t畛p vn b畉n. 2. V畛i m畛i d嘆ng, 畉m s畛 t畛 xu畉t hi畛n trong 坦 v 動a ra mn h狸nh k畉t qu畉 t鱈nh 動畛c. 3. 動a ra mn h狸nh t畛 di nh畉t trong vn b畉n. Tr狸nh by: Tr畉n Hoi Nh但n