Tehnici de programare (Triere)

Metoda Trierii

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. 

Metoda trierii poate fi folosită pentru rezolvarea următoarelor probleme din viață:

• aflarea numărului minim de monede care pot fi date drept plată sau rest;
• medicii deseori se confruntă cu necesitatea aplicării metodei trierii cazurilor, când numărul răniților sau bolnavilor este foarte mare, medicul fiind suprasolicitat, în cazul unui război, sau când își periclitează propria viață în cazul unei epidemii periculoase;
• aflarea ariei maxime a unui lot de teren, avînd la dispoziție o anumită lungime de sîrmă ghimpată, spre exemplu (ca perimetru dat);
• generarea submulțimilor unei mulțimi (aflarea tuturor combinațiilor posibile), ceea ce ne poate fi foarte util în viața de zi cu zi;
• afișarea coordonatelor a două puncte date ce au distanță minimă sau maximă, ceea ce va fi foarte folositor dacă plănuim o călătorie;
• calcularea șanselor de a lua premiul mare la loterie etc.

Problema:

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:

Program Pex;

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

Else SolutiePosibila:=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 do

If SolutiePosibila(i) then PrelucrareaSolutiei(i);

Writeln(‘K=’, K);

Readln;

Link:http://caterinamacovenco.blogspot.md/p/tehnici-de-programare.html