Metoda Trierii

Definiție :

Se numeşte metoda trierii o metodă ce indentifică toate soluţiile unei probleme în dependenţă de mulţimea soluţiilor posibile.  Toate soluţiile se identifică prin valori, ce aparţin tipurilor de date studiate: integer, boolean, enumerare, char, subdomeniu, tablouri unidimensionale.
Fie P o problemă, soluţia căreia se află printre elementele mulţimii S cu un număr finit de elemente. S={s1, s2 , s3 , … , sn} . Soluţia se determină prin analiza fiecărui element si din mulţimea S.

Descriere :

  • nFie P o problemă, soluţia căreia se află printre elementele mulţimii S cu un număr finit de elemente.

  •   S={s1, s2 , s3 , … , sn}

nSoluţia se determină prin analiza fiecărui element si din mulţimea S.

Particularităţi de implementare:

  • Generarea şi cercetarea consecutivă a elementelor mulţimii S.

  • Utilizarea funcţiilor şi procedurilor pentru fiecare din subproblemele:

  1.      Verificarea apartenenţei elementului cercetat si la soluţie

  2.      Plasarea elementului curent în soluţie

  3.      Generarea următorului element al mulţimii (dacă e necesar)

    Schema generală a unui algoritm bazat pe metoda trierii poate fi redată cu ajutorul unui ciclu:
     
    For i:=1 to k do If SolutiePosibila(Si) then PrelucrareaSolutiei(Si)
    Unde SoluţiaPosibilă este o funcţie booleană care returnează valoarea true dacă elementul Si satisface condiţiile problemei şi false în caz contrar, iar Prelucrarea Solutiei este o procedura care efectuează prelucrarea elementuluiselectat. De obicei, această procedura soluţia Si este afişată pe ecran.În continuare vom analiza doua exemple care pun în evidenţă
    Exemplu
    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.
     Rezolvare.
     
    Evident, mulţimea soluţiilor posibile S = {0, 1, 2, …, n}. În programul ce urmează suma cifrelor oricărui număr natural i, iS, se calculează cu ajutorul funcţiei SumaCifrelor. Separarea cifrelor zecimale din scrierea număruluinatural “i” se efectuează de la dreapta la stinga prin împărţirea numărului “i” si a cîturilor respective la baza 10. 
    Program P151;
    Type Natural=0..MaxInt;
    Var I, k, m, n : Natural;
    Function SumaCifrelor(i:Natural): Natural;
    Var suma: Natural;
    Begin
    Suma:=0;
    Repeat Suma:=suma+(I mod 10);
    i:=i div 10;
    until i=0;
    SumaCifrelor:=suma;
    End;
    Function SolutiePosibila(i:Natural):Boolean;
    Begin
    If SumaCifrelor(i)=m then SolutiaPosibila:=true 
    ElseSolutiePosibila:=false;
    End;
    Procedure PrelucrareaSolutiei(i:Natural);
    Begin
    Writeln(‘i=’, i);
    K:=k+1;
    End;
    Begin
    Write(‘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.
    schema

    Verifica Cunostinetel  Test

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s