4
Ch ng1
CÁCKHÁINI M C N B N
Mônh c:Phântíchvàthi tk gi ithu t
5
N i dung
1. Ki u d li u tr u t ng
2. quy
3. Phân tíchgi i thu t
6
1.Ki u d li utr ut ng
• Mô t m tc utrúcd li utheocáctácv (operations) làm
vi ctrên c utrúc d li uthì ti n l i h n là di n t nó theo
nh ng chiti t thi công (implementation details).
• Chúngtanêntáchnh ngkháini mv c utrúcd li ura
kh i nh ngchiti tthi công.
• Khim tc utrúcd li u c nhngh atheocáchnh
v ytas cóm tki ud li utr ut ng (abstractdata type)
hay ADT.
M tki u d li utr u t ng là m tmôhìnhtoán
h c icùng v inh ngtác v c nhngh atrên
mô hìnhnày.
7
Vàithí d v Ki u d li utr u t ng
• M t t p (set)làm tt ph pg mzero hay nhi uph nt .
M tph nt không cphépxu thi nnhi uh nm t
l ntrongt p. M t t p g m n ph n t cký hi u là {a
1
,
a
2

Gi i m t bàitoán b ngADT
th y íchl i c aki ud li utr ut ng,th xétbàitoán
sau:
Cho m t m ng(array) g m n s , A[1 n], hãyxác nh k ph n
t l nnh ttrongm ng,v ik n.Thí d , n uA là {5,3, 1, 9,
6}, và k = 3, thì k t qu là {5, 9, 6}.
Không d xây d ng m t gi ithu t gi i bàitoántrên.
Tath dùngki ud li utr ut ng at p(multiset) v i các
tác v :
initialize(M),
insert(x, M),
deleteMin(M),
findMin(M)
10
Suy ngh trên a t pM,tacóth vi t m tgi ithu tnh
sau:
Initialize(M);
for i:= 1 to k do
Insert(A[i],M);
for i:= k+ 1 to n do
if A[i]>FindMin(M) then
begin
DeleteMin(M);Insert(A[i],M)
end;
Trongthí d trên,tath yki ud li utr ut ng ã làm
ngi nhóavi cxây d ng gi ithu tb ngcáchkhông b n
tâm nnh ng chiti tthi cônghayhi nth c hóa.
11
Thicông m tki ud li utr ut ng
Quá trìnhdùngm tc utrúc d li uc th hi nth chóa

begin
if N= 0
then factorial:= 1
else factorial:= N*factorial(N-1);
end;
14
H th ctruy h i
Thí d 2: S Fibonacci
H th ctruyh i:
F
N
= F
N-1
+ F
N-2
for N 2
F
0
= F
1
= 1
1, 1, 2, 3, 5, 8,13, 21, …
function fibonacci(N: integer): integer;
begin
if N<= 1
then fibonacci:= 1
else fibonacci:=fibonacci(N-1)+
fibonacci(N-2);
end;
15

o n1/8inch, v.v
procedure rule(l,r,h: integer);
/*l:left positionoftheruler;r:right
position
oftheruler*/
var m: integer;
begin
if h> 0 then
begin
m:=(1+r) div 2;mark(m, h);
rule(l,m, h-1);
rule(m,r , h-1)
end;
end;
Gi s th t c
mark(x,h) v m t
v ch h n v t i v
trí x.
18
Kh quy
V n :Gi ithu tkhông quy th ng làm vi c h u hi u
và d ki msoát h n1 gi ithu t quy.
Làm cáchnào chuy n i m tch ngtrình quy
thànhm tch ngtrìnhkhông- -quyt ng ng.
Ph ngpháp:
Cho m tth t c quyP, m i l ncóm tl nhg i quy
nP, giá tr hi nhànhc acácthams vàcácbi nc cb
cc tvàocácng nx p(stack) x lý sau.
M i l ncóm ts quay v quyv P,giá tr c acác
tham s và cácbi n c c b s ckhôiph cl i t cácng n

var t: integer;
begin
top:=0; /*preparation forstacks*/
1: if n=1then
begin writeln(beg,end); goto 5 end;
top:= top+1; /* firstrecursivecall*/
STN[top]:=n;STBEG[top]:=beg;
STAUX [top]:=aux;
STEND [top]:=end;
STADD [top]:=3;
/*savingreturnaddress*/
n:=n-1; t:=aux;aux:=end;
end:= t;
goto 1;
3:writeln(beg,end);
top:= top+1; /*second
recursivecall*/
STN[top]:=n;
STBEG[top]:=beg;
STAUX[top]:aux;
STEND[top]:=end;
STADD[top]:=5;
/*savingreturnaddress*/
n:=n-1; t:=beg;beg:=aux;
aux:= t; goto 1;
5. /* translationofreturnpoint*/
if top<>0then
begin
n:=STN[top];
beg:=STBEG [top];

begin
visit(t);
traverse(t.1);traverse(t.r)
end
end;
Tr ckhikh quyth t cnày,tacóth lo i b l nh g i
quyth haid dàngvìkhôngcómãch ngtrình isau
nó.
L nh g i quyth haicóth cchuy nthànhm tl nh
goto nh sau:
23
Kh quy uôi
procedure traverse(t:link);
label 0,1;
begin
0: if t= z thengoto 1;
visit(t);
traverse(t. l);
t:= t.r; goto 0;
1: end;
K thu tnày cg i là kh quy uôi (tail-recursion
removal).
24
procedure traverse(t: link);
label 0, 1, 2, 3;
begin
0:if t=zthen goto 1;
visit(t);
push(t); t:= t.l; goto 0;
3:t:= t.r; goto 0;

push(t.r);t:= t.l;
end;
until stack_empty;
end;
M tl nn atacóth lo i b hail nh goto cònl i b ngcách
dùngvòngl prepeat .
27
procedure traverse(t: link);
begin
push(t);
repeat
t:= pop;
if t<>zthen
begin
visit(t);
push(t.r); push(t.1);
end;
until stack_empty;
end;
Haivòngl pl ngnhaucóth c ngi nhóa
nh sau:
28
tránh anh ngcâycon r ngvàostack,tacóth s a
ch ngtrìnhtrênthành:
procedure traverse(t: link);
begin
push(t);
repeat
t:= pop;
visit(t);