Tehnici de programareMetoda trierii
DescriereFie P o problem, soluia creia se afl printre elementele mulimii S cu un numr finit de elemente. S={s1, s2 , s3 , ... , sn} Soluia se determin prin analiza fiecrui element si din mulimea S.
Schema de aplicare
Problem prototipSe consider numerele naturale din mulimea {1, 2, 3, ..., n}. S se determine toate elementele acestei mulimi, pentru care suma cifrelor este egal cu un numr dat m.
Schema de rezolvare Pentru i de la 1 pn la n:Se calculeaz suma cifrelor numrului i. Dac suma cifrelor este egal cu m includem i n soluie
Particulariti de implementareGenerarea i cercetarea consecutiv a elementelor mulimii S. Utilizarea funciilor i procedurilor pentru fiecare din subproblemele: Verificarea apartenenei elementului cercetat si la soluiePlasarea elementului curent n soluieGenerarea urmtorului element al mulimii (dac e necesar)
Analiza problemeiNumrul secvenelor binare de lungime n este 2n, finit. (vezi: Informatica, manual pentru clasa X)
Prin urmare, pentru problema dat poate fi aplicat metoda trierii.
Modelul matematicElementele mulimii S pot fi interpretate ca numere {0, 1, 2, ..., 2n-1}, reprezentate pe n poziii binare.Pentru generarea consecutiv a secvenelor binare se va utiliza formula: s0 = 0; si = si-1 + 1; i=1, ..., 2n-1
Separarea subproblemelorGenerarea secvenelor binare de lungime n Determinarea numrului de uniti n secvena curent Prelucrarea soluiei curente
Structuri de datetablou unidimensional cu n elemente, ce pot primi valoarea 0 sau 1. Pentru problema propus n nu depete valoarea 20. fiier text pentru stocarea soluiei.
AlgoritmIniializm variabilele n i k, fiierul de ieire, tabloul B.Pasul 1. Cercetarea secvenei curente Se calculeaz numrul de uniti (r) n secvena curent B Pasul 2. Prelucrarea soluiei Dac r k, secvena curent B este nscris n fiierul de ieire. Pasul 3. verificarea prezenei secvenelor necercetateDac r = n se nchide fiierul de ieire, apoi STOP. Pasul 4. Generarea secvenei urmtoareDac B[n]=0 atunci B[n] 1n caz contrar:i n att timp ct B[i] = 1 repetm B[i] 0; i i1;pentru indicele curent iB[i] 1Revenim la Pasul 1.
DeclaraiiProgram Triere;const nmax=20;type secventa01= array[1..nmax] of 0..1;var b:secventa01; r,i,n,k:integer; f:text;
Funciifunction numara1:integer; var s,j:integer; begin s:=0; for j:=1 to n do s:=s+b[j]; numara1:=s; end;
Proceduriprocedure scrie; var j: integer; begin for j:=1 to n do write (f,b[j]); writeln(f); end;
procedure urmator (var x:secventa01); var j:integer; begin j:=n; while x[j]=1 do begin x[j]:=0; j:=j-1; end; x[j]:=1; end;
Blocul de calculbegin readln(n,k); assign(f,'OUT.TXT');rewrite(f); for i:=1 to n do b[i]:=0; repeat r:= numara1; if r >= k then scrie; if r < n then urmator(b); until r=n; close(f);end.
Literatura recomandat:Gremalschi A. Informatica. Tehnici de programare, manual pentru clasa a 11-a. Chiinu, tiina, 2003.Cerchez Emanuela. Programarea n limbajul C / C++ pentru liceu. Vol. I III. Polirom, Iai, 2007
Mulimea S nu va mai conine elemente necercetate dup generarea secvenei formate doar din uinti
Top Related