Tehnici de programare (Greedy)

Greedy

“greedy” = “lacom”. Algoritmii de tip greedy vor să construiască într-un mod cât mai rapid soluția unei probleme. Ei se caracterizează prin luarea unor decizii rapide care duc la găsirea unei soluții potențiale a problemei. Nu întotdeauna asemenea decizii rapide duc la o soluție optimă; astfel ne vom concentra atenția pe identificarea acelor anumite tipuri de probleme pentru care se pot obține soluții optime.

Algoritmii greedy se numără printre cei mai direcți algoritmi posibili. Ideea de bază este simplă: având o problema de optimizare, de calcul al unui cost minim sau maxim, se va alege la fiecare pas decizia cea mai favorabilă, fără a evalua global eficiența soluţiei. În general exista mai multe soluții posibile ale problemei. Dintre acestea se pot selecta doar anumite soluții optime, conform unor anumite criterii. Scopul este de a găsi una dintre acestea sau dacă nu este posibil, atunci o soluție cât mai apropiată, conform criteriului optimal impus.

Problema:

Este dat ins-ora de inceput a unui spectacol si sfs-ora de sfarsit a unui spectacol. Calculati numarul maxim de spectacole la care un om poate sa se duca pana la miezul noptii.

Program P3;

type teatru=record

ins, sfs:integer; (ora de inceput si de sfarsit a unui spectacol calculata in minute scurse fata de miezul noptii)

ord:integer; (numarul de ordin al spectacolului)

end;

Var v:array [1..30] of teatru;

n, ultim, nr:integer; (n=numarul de spectacole, in variabila ultim avem in permanenta ultimul spectacol selectat, nr=numarul maxim de spectacole)

Procedure sortare_piese;

Var i,j:integer;

temp:teatru;

Begin

For i:=1 to n-1 do

for j:=i+1 to n do

if v[j].sfs<v[i].sfs then

begin

temp:=v[i];

v[i]:=v[j];

v[j]:=temp;

end;

Procedure citire_piese;

Var hh,mm,i:integer;

begin

Write (‘Numarul de piese de teatru n= ‘); Readln (n);

for i:=1 to n do begin

Write (‘Piesa cu nr ‘,i, cand incepe? (ora si minutul)’);

Readln (hh,mm);

v[i].ins:=hh*60+mm;

Write (‘Piesa cu nr ‘,i, cand se termina? (ora si minutul)’);

Readln (hh,mm);

v[i].ins:=hh*60+mm;

v[i].ord:=i;

end; end;

Procedure afis_piese;

Var i:integer;

Begin

Write (‘Inceputurile si sfarsiturile pieselor in minute scurse de la miezul noptii: ‘);

for i:=1 to n do

write (‘(‘,v[i].ins,’,’,v[i].sfs,’,’,v[i].ord,’)’);

writeln;

end;

Procedure algo_greedy;

Var i:integer;

Begin

Write (‘Piesele posibile, in ordine: ‘);

ultim:=1; nr:=1;

write (v[i], ‘ ‘);

for i:=2 to n do

If (v[i].ins>v[ultim].sfs) then

Begin

Write (v[i].ord, ‘ ‘);

ultim:=i;

nr:=nr+1; end;

Writeln (‘In total se pot alege maxim’,nr,’ piese’);

end;

Begin

citire_piese;

afis_piese;

sortare_piese;

afis_piese;

algo_greedy;

end.

Link:https://tpascalblog.wordpress.com/2012/12/14/program-teatru/