tehnici_de_programare_triere

8/7/2019 tehnici_de_programare_triere

1/17

Tehnici de programare

Metoda trierii


2/17

Descriere

Fie P o problem, soluia creia se afl printreelementele mulimii S cu un numr finit deelemente.

S={s1, s2 , s3 , ... , sn}

Soluia se determin prin analiza fiecruielementsi din mulimea S.


3/17

Schema de aplicare

x satisfacecondiia problemei

x s1

n S exist

elemente necercetate

STOP

START

Includem x n soluie

da

x un element necercetat din S

da

nu

nu


4/17

Problem prototip

Se consider numerele naturale din mulimea

{1, 2, 3, ..., n}. S se determine toateelementele acestei mulimi, pentru care sumacifrelor este egal cu un numr datm.

Schema de rezolvare

Pentru i de la 1 pn la n:

Se calculeaz suma cifrelor numrului i.

Dac suma cifrelor este egal cu mincludem i n soluie


5/17

Particulariti de implementare

Generarea i cercetarea consecutiv a

elementelor mulimii S.

Utilizarea funciilor i procedurilor pentru

fiecare din subproblemele: Verificarea apartenenei elementului cercetatsi la

soluie

Plasarea elementului curent n soluie Generarea urmtorului element al mulimii

(dac e necesar)


6/17

Problem

S se scrie un program care determin toatesecvenele binare de lungime n, fiecare din eleconinnd nu mai puin de k cifre de 1.

Intrare: numere naturale n, 1


7/17

Analiza problemei

Numrul secvenelor binare de lungime neste 2n, finit.(vezi: Informatica, manual pentru clasa X)

Prin urmare, pentru problema dat poate

fi aplicat metoda trierii.


8/17

Modelul matematic

;1211...111

;2210...111

...

;2010...00

;101...000

;000...000

!

!

!

!

!

n

n

n

n

n

n

n

Elementele mulimii

S

pot fiinterpretate ca numere {0, 1,2, ..., 2n-1}, reprezentate pen poziii binare.

Pentru generarea consecutiva secvenelor binare se vautiliza formula:

s0 = 0;si = si-1 + 1; i=1, ..., 2n-1


9/17

Separarea subproblemelor

Generarea secvenelor binare de lungime ncu r, r>k uniti

Generareasecvenelorbinare delungime n

Determinareanumrului de

uniti n

secvena curent

Prelucrareasoluieicurente


10/17

Structuri de date

tablou unidimensional cu n elemente, ce potprimi valoarea 0 sau 1. Pentru problemapropus n nu depete valoarea 20.

fiier text pentru stocarea soluiei.


11/17

Algoritm

Iniializm variabilele n ik, fiierul deieire, tabloul B.

Pasul 1. Cercetarea secvenei curente

Se calculeaznumrul deuniti (r) n secvena curentB

Pasul 2. Prelucrarea soluiei

Dac r u k, secvena curentB este nscris n fiierul deieire.

Pasul 3. verificarea prezenei secvenelor necercetate Dac r = n se nchide fiierul deieire, apoi STOP.

Pasul 4. Generarea secvenei urmtoare

Dac B[n]=0 atunciB[n] 1

n caz contrar: i n

att timp ct B[i] = 1 repetm

B[i] 0; i i1;

pentruindicele curent i B[i] 1

Revenim laPasul 1.


12/17

Declaraii

P

rogram Triere;const

nmax=20;

type

secventa01=

array[1..nmax] of 0..1;

var

b:secventa01;r,i,n,k:integer;

f:text;


13/17

Funcii

function numara1:integer;

var

s,j:integer;

begin

s:=0;

forj:=1 ton dos:=s+b[j];

numara1:=s;

end;


14/17

Proceduriprocedure scrie;

var j: integer;

beginfor 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 dobegin x[j]:=0; j:=j-1; end;

x[j]:=1;

end;


15/17

Blocul de calcul

begin

readln(n,k);assign(f,'OUT.TXT');rewrite(f);

fori:=1 ton dob[i]:=0;

repeat

r:= numara1;ifr >=k then scrie;

ifr < n then urmator(b);

until r=n;

close(f);

end.


16/17

Literatura recomandat:

Gremalschi A. Informatica. Tehnici de

programare, manual pentru clasa a 11-a.Chiinu, tiina, 2003.

Gremalschi A., Mocanu Iu., Gremalschi L.Informatica. Structura calculatorului. Manualpentru clasa a 10-a. Chiinu, tiina, 2000.


17/17

Probleme pentru rezolvare

prin metoda trierii

Compartimentul VI. Probleme de generalizare

Itemii:19, 20, 21, 22, 30, 31, 32, 33,34, 35, 40, 41, 45, 46, 47, 48.

tehnici_de_programare_triere

Documents