# data[].attributes.attachment_link.description
Tehnici de programare Pe parcursul dezvoltării informaticii s-a stabilit că multe probleme de o reală importanţă practică pot fi rezo...

# data[].attributes.attachment_link.description
Check out this presentation designed by Parascovia Tarîța.

# data[].attributes.attachment_link.readable_text
Metoda Greedy este una dintre cele mai directe tehnici de proiectare a algoritmilor care poate fi aplicată la o gamă largă de probleme.
Această metodă se aplică problemelor de optimizare, care constau în determinarea unei submultimi B, a unei mulţimi A cu n elemente care să îndeplinească anumite condiţii pentru a fi acceptate. Orice submulţime de acest fel, care respectă aceste condiţii se numeşte soluţie posibilă. Din mulţimea tuturor soluţiilor posibile se doreştedeterminarea unei soluţii care maximizează sau minimizează o funcţie de cost. O soluţie posibilă care realizează acest lucru se numeşte soluţie optimă.
Descrierea metodei
Exemplu:
Se dă o mulţime A cu n elemente şi se cere să se determine o submulţime B care satisface anumite restricţii. Această soluţie se numeşte soluţie posibilă. Se cere să se determine o soluţie posibilă care să maximizeze sau să minimizeze o anumită funcţie obiectiv dată. Această soluţie se numeşte soluţie optimă.
Specificul acestei metode constă în faptul că se construieşte soluţia optimă pas cu pas , la fiecare pas fiind selectat (sau "înghiţit") în soluţie elementul care pare "cel mai bun" la momentul respectiv, în speranţa că va duce la soluţia optimă globală.

Prezentare PowerPoint

PROGRAM BENZINARIE

Program p2;
Type benz=record
ins, sfs:integer;
ord:integer; end;
Var v:array [1..100] of benz;
n, ultim, nr:integer;
Procedure citire_clienti;
Var hh, mm, i:integer;
begin
Write ('n= '); Readln (n);
for i:=1 to n do begin
Write ('Clientul cu nr. ',i,'cand este servit? (ora si minutul)');
Readln (hh, mm);
v[i].ins:=hh*60+mm;
Write ('clientul cu nr ', i, ' cand a terminat alimentarea ? ');
Readln (hh, mm);
v[i].sfs:=hh*60+mm;
v[i].ord:=i; end; end;
Procedure afisare_clienti;
Var i:integer;
Begin
Write (' cand incepe sa fie servit si cand a terminat alimentarea: ');
for i:=1 to n Do
Write ('('v[i].ins,',',v[i].sfs, ',',v[i].ord')');
Writeln; end;
Procedure sortare_clienti;
Var i,j:integer;
t:benz;
Begin
for i:=1 to n-1 Do
for j:=i+1 to n Do
if (v[j].sfs<v[i].sfs) then
Begin
t:=v[i]; v[i]:=v[j];
v[j]:=t; end; end;
Procedure alg_greedy;
var i:integer;
Begin
Write ('posibilii clienti, in ordine: ');
ultim:=1;
nr:=1;
Write (v[i].ord, ' ');
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, 'clienti');
begin
citire_clienti;
afisare_clienti;
sortare_clienti;
afisare_clienti;
alg_greedy;
END.

# data[].attributes.attachment_link.description
Metoda Greedy este una dintre cele mai directe tehnici de proiectare a algoritmilor care poate fi aplicată la o gamă largă de probleme.Această metodă se aplică problemelor de optimizare, care constau în determinarea unei submultimi B, a unei mulţimi A cu n elemente care să îndeplinească anumite condiţii pentru a fi acceptate.

# data[].attributes.attachment_link.readable_text
Elaborati
un program care determina cate numere prime sunt mai mari decat numarul
natural dat m.

var i,k,n,m:integer;
function NrPrim(a:integer):boolean;
var i:integer;
t:boolean;r:real;
begin
t:=true;
r:=sqrt(a);
i:=2;
while (i<=r)and t do
begin
if (a mod i)=0 then t:=false;
i:=i+1;
end;
NrPrim:=t;
end;
function SolutiePosibila(i:integer):boolean;
begin
SolutiePosibila:=NrPrim(n);
end;
procedure PrelucrareaSolutiei(i:integer);
begin
writeln('i=',i);
k:=k+1;
end;
begin
writeln('Dati n=');readln(n);
writeln('Dati m=');readln(m);
k:=0;
writeln('raspuns');
if NrPrim(n) then writeln('numarul ',n,' este prim') else writeln('numarul
',n,' nu este prim');
for i:=n+1 to m do
if NrPrim(i)=true and (i<m) then PrelucrareaSolutiei(i);
writeln('k=',k);
end.

Dati n=
10
Dati m=
40
raspuns
numarul 10nu este prim
i=11
i=13
i=17
i=19
i=23
i=29
i=31
i=37
i=40
k=9
Problema 4.Un numar se numeste perfect daca este egal cu suma divizorilor
lui, in afara de el insusi.Sa se afle numerele perfecte mai mici decat
numarul natural dat.

var n,i,m,k,x,sum:integer;
function nrperfect(x:integer):boolean;
begin
i:=1; sum:=0;
repeat
if (x mod i)=0 then sum:=sum+i;
i:=i+1
until i>(x div 2);
if sum=x then nrperfect:=true else nrperfect:=false;
end;
procedure prelucrareasolutiei(x:integer);
begin
writeln(x);
k:=k+1; end;
begin
k:=0;
readln(m);
for x:=1 to m-1 do
if nrperfect(x) then prelucrareasolutiei(x);
writeln('k=',k);
end.

# data[].attributes.headline
METODA TRIERII. Exemplu de problemă: 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.

# data[].attributes.subject
METODA TRIERII. Exemplu de problemă: 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.

# data[].attributes.body
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 SolutiePosibila:=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;
End.

Resursa

# data[].attributes.attachment_link.readable_text
Este o metodă generală de elaborare a algoritmilor. În esenţă ea se aplică problemelor în care se dă o mulţime A conţinând n date de intrare cerându-se să se determine o submulţime B a sa care să îndeplinească anumite condiţii pentru a fi acceptată. Cum în general există mai multe astfel de mulţimi, se dă şi un criteriu conform căruia, dintre submulţimile acceptabile (numite soluţii posibile), se alege una singură (numită soluţie optimă) ca rezultat final.

Soluţiile posibile au următoarea proprietate: dacă submulţimea B A este o soluţie posibilă şi C B, atunci şi C este o soluţie posibilă. Vom presupune că mulţimea vidă este întotdeauna o soluţie posibilă.

Algoritmii greedy (greedy = lacom) sunt in general simpli si sunt folositi la probleme de optimizare, cum ar fi: sa se gaseasca cea mai buna ordine de executare a unor lucrari pe calculator, sa se gaseasca cel mai scurt drum intr-un graf etc. In cele mai multe situatii de acest fel avem:
· o multime de candidati (lucrari de executat, varfuri ale grafului etc)
· o functie care verifica daca o anumita multime de candidati constituie o solutie posibila, nu neaparat optima, a problemei
· o functie care verifica daca o multime de candidati este fezabila, adica daca este posibil sa completam aceasta multime astfel incat sa obtinem o solutie posibila, nu neaparat optima, a problemei
· o functie de selectie care indica la orice moment care este cel mai promitator dintre candidatii inca nefolositi
· o functie obiectiv care da valoarea unei solutii (timpul necesar executarii tuturor lucrarilor intr-o anumita ordine, lungimea drumului pe care l-am gasit etc); aceasta este functia pe care urmarim sa o optimizam (minimizam/maximizam)
http://vega.unitbv.ro/~andonie/Cartea%20de%20algoritmi/cap6.htm

# data[].attributes.attachment_link.description
Este o metodă generală de elaborare a algoritmilor. În esenţă ea se aplică problemelor în care se dă o mulţime A conţinând n date de intrare cerându-se să se determine o submulţime B a sa care să îndeplinească anumite condiţii pentru a fi acceptată.

# data[].attributes.attachment_link.title
Introduction to Greedy Algorithms in Python with Minimum Change

# data[].attributes.attachment_link.title
Informatica, Clasa a XI-a, Limbajul de programare C++Tablouri bidimensionale

# data[].attributes.attachment_link.title
Metoda GREEDY - problema  #1340 Rucsac - pbinfo.ro