Metoda Trierii

Get Started. It's Free
or sign up with your email address
Metoda Trierii by Mind Map: Metoda Trierii

1. Ce presupune metoda trierii?

2. Schema generala

2.1. Schema generală

2.2. a unui algoritm bazat pe metoda trierii poate fi redată cu ajutorul unui ciclu:

2.3. For i:=1 to k do SolutiePosibila(Si) then PrelucrareaSolutiei(Si)

2.4. unde solutia posibila

2.4.1. SoluţiaPosibilă

2.5. este o funcţie booleană care returnează valoarea truedacă elementul Si satisface condiţiile problemei şi false în caz contrar, iar PrelucrareaSolutiei este o procedura care efectuează prelucrarea elementuluiselectat. De obicei, această procedura soluţia Si este afişată pe ecran.

3. În cele mai simple cazuri elementele Si, Si ∈ S, pot fi reprezentate prin valori aparţinind unor tipuri ordinale de date: integer, Boolean, char, enumerare sau subdomeniu.În problemele mai complicate sîntem nevoiţi să reprezentăm aceste elemente prin tablouri, articole sau mulţimi.Menţionăm că în majoritatea problemelor soluţiile posibile S 1 , S 2 , …, S k nu sunt indicate explicit în enunţul problemei şi elaborarea algoritmilor pentru calcularea lor cade în sarcina programatorului.

4. Exemplul 1: Se consideră numerele naturale din mulţimea {0, 1, 2, …, n}. Elaboraţi un program care determină pentru cîte numere K din această mulţime suma cifrelor fiecărui număr este egală cu m. În particular, pentru n=100 si m=2, în mulţimea{0, 1, 2, …, 100} există 3 numere care satisfac condiţiile problemei: 2, 11 si 20.Prin urmare, K=3.

4.1. Rezolvare:

4.2. Program P151;Type Natural=0..MaxInt;Var I, k, m, n : Natural;Function SumaCifrelor(i:Natural): Natural; Var suma: Natural;BeginSuma:=0;RepeatSuma:=suma+(I mod 10);i:=i div 10;until i=0;SumaCifrelor:=suma;End;Function SolutiePosibila(i:Natural):Boolean;BeginIf SumaCifrelor(i)=m then SolutiaPosibila:=trueElseSolutiePosibila:=false;End;Procedure PrelucrareaSolutiei(i:Natural);BeginWriteln(‘i=’, i);K:=k+1;End;BeginWrite(‘Dati n=’); readln(n);Write(‘Dati m=’); readln(m);K:=0;For i:=0 to n doIf SolutiePosibila(i) then PrelucrareaSolutiei(i);Writeln(‘K=’, K);Readln;End.

5. Schema de aplicare http://image.slidesharecdn.com/infor-140406104020-phpapp01/95/inform-3-638.jpg?cb=1396780845

6. Exemplul 2. Se consideră mulţimea P={ P1, P2, …, Pn} formată din n puncte (2 ≤ n ≤30) pe un plan Euclidian. Fiecare punct Pj este definit prin coordonatele sale Xj,Yj.Elaboraţi un program care afişează la ecran coordonatele punctelor Pa, Pb distanţa dintre care este maximă.

6.1. rezolvare

6.1.1. Mulţimea soluţiilor posibile S=P×P. Elementele (Pj, Pm) ale produsului cartezian P×P pot fi generate cu ajutorul a doua cicluri imbricate: For j:=1 to n do si For m:=1 to n do; SolutiePosibila(Pj, Pm) then PrelucrareaSolutiei( Pj, Pm) Distanţa dintre punctele Pj, Pm se calculează cu ajutorul formulei: D jm = √(X j -X m )2+ (Y j - Y m )2. Program P152;Const nmax=30; Type Punct = record X, y: real;End;Indice = 1..nmax;Var P:array[Indice] of Punct;J, m, n:Indice;Dmax:real;PA, PA: Punct;Function Distanta(A, B: Punct): real;BeginDitanta:=sqrt(sqr(A.x-B.x)+sqr(A.y-B.y));End;Function SolutiePosibila(j, m:Indice):Boolean;BeginIf j<>m then SolutiePosibila:=trueElse SolutiePosibila:=false;End;Procedure PrelucrareaSolutiei(A, B: Punct);BeginIf Distanta(A,B)>dmax thenBeginPA:=A; PB:=B;Dmax:=Distanta(A,B);End;End;BeginWrite(‘Dati n=’); readln(n);Writeln(‘Dati coordonatele x, y ale punctelor’);For j:=1 to n doBeginWrite(‘P[‘, j,’]: ‘); readln(P[j].x, P[j].y);End;Dmax:=0;For j:=1 to n doFor m:=1 to n doIf SolutiePosibila(j, m) thenPrelucrareaSolutiei(P[j], P[m]);Writeln(‘Solutia: PA=(‘, PA.x:5:2, ‘,’, PA.y:5:2, ‘)’);Wtieln(‘Solutia: PB=(‘, PB.x:5:2, ‘,’, PB.y:5:2, ’)’);Readln;End.

6.2. https://ru.scribd.com/doc/60874739/Proiect-la-informatica

7. Avantajul principal al algoritmilor bazaţi pe metoda trierii constă în faptul că programele respective sînt relative simple, iar depanarea lor nu necesita teste sofisticate. Complexitatea temporală a acestor algoritmi este determinată denumărul de elemente k din mulţimea soluţiilor posibile S. În majoritatea problemelor de o reala importanţă practica metoda trierii conduce la algoritmii exponenţiali. Întrucit algoritmii exponenţiali sînt inacceptabili in cazul datelor de intrare foarte mari, metoda trierii este aplicată numai în scopuri didactice sau pentru elaborarea unor programe al căror timp de execuţie nu este critic.