Post on 26-Jun-2015
PROIECT LA PROIECT LA INFORMATICAINFORMATICA
Clasa a XI-a I1;Clasa a XI-a I1;
3 March 20093 March 200911
PROGRAMAREA DINAMICAPROGRAMAREA DINAMICA
Programarea dinamica face parte dintr-o categorie de metode Programarea dinamica face parte dintr-o categorie de metode matematice numite metode de scufundare.O problemã de matematice numite metode de scufundare.O problemã de
programare dinamicã contine subprobleme comune (care nu programare dinamicã contine subprobleme comune (care nu sunt independente) din a cãror rezolvare si combinare se sunt independente) din a cãror rezolvare si combinare se
obtine solutia unei (sub)probleme mai mari.Deci rezolvarea obtine solutia unei (sub)probleme mai mari.Deci rezolvarea unei (sub)probleme se poate face doar dupã solutionarea unei (sub)probleme se poate face doar dupã solutionarea
(sub)problemelor, care alcãtuiesc problema respectivã.Spunem (sub)problemelor, care alcãtuiesc problema respectivã.Spunem cã programarea dinamica actioneaza de jos in sus,prelucrând si cã programarea dinamica actioneaza de jos in sus,prelucrând si
combinând subcazuri mici,obtinând astfel solutia pentru combinând subcazuri mici,obtinând astfel solutia pentru subcazuri tot mai mari.subcazuri tot mai mari.
3 March 20093 March 2009 22
Totodatã programarea dinamicã evitã rezolvarea de Totodatã programarea dinamicã evitã rezolvarea de mai multor ori a aceleiasi subprobleme(rezolvându- mai multor ori a aceleiasi subprobleme(rezolvându-se doar problemele independente ),prin memorarea se doar problemele independente ),prin memorarea rezultatelor partiale.rezultatelor partiale.
Nu există un criteriu pe baza căruia să identificăm Nu există un criteriu pe baza căruia să identificăm cu siguranţă o problemă pentru rezolvarea căreia cu siguranţă o problemă pentru rezolvarea căreia trebuie să utilizăm metoda programării dinamice, dar trebuie să utilizăm metoda programării dinamice, dar putem formula două proprietăţi care sugerează o putem formula două proprietăţi care sugerează o soluţie prin programare dinamică.soluţie prin programare dinamică.
3 March 20093 March 2009 33
PRINCIPII FUNDAMENTALE ALE PRINCIPII FUNDAMENTALE ALE PROGRAMARII DINAMICEPROGRAMARII DINAMICE
Programarea dinamica, ca si metoda divide et impera, Programarea dinamica, ca si metoda divide et impera, rezolva problemele combinand solutiile rezolva problemele combinand solutiile subproblemelor. Dupa cum am vazut, algoritmii subproblemelor. Dupa cum am vazut, algoritmii divide et impera partitioneaza problemele in divide et impera partitioneaza problemele in subprobleme independente, rezolva subproblemele in subprobleme independente, rezolva subproblemele in mod recursiv, iar apoi combina solutiile lor pentru a mod recursiv, iar apoi combina solutiile lor pentru a rezolva problema initiala. Daca subproblemele contin rezolva problema initiala. Daca subproblemele contin subsubprobleme comune, in locul metodei divide et subsubprobleme comune, in locul metodei divide et impera este mai avantajos de aplicat tehnica impera este mai avantajos de aplicat tehnica programarii dinamice.programarii dinamice.
3 March 20093 March 2009 44
3 March 20093 March 2009 55
Sa analizam insa pentru inceput ce se intampla Sa analizam insa pentru inceput ce se intampla cu un algoritm divide et impera in aceasta din cu un algoritm divide et impera in aceasta din urma situatie. Descompunerea recursiva a urma situatie. Descompunerea recursiva a cazurilor in subcazuri ale aceleiasi probleme, cazurilor in subcazuri ale aceleiasi probleme, care sunt apoi rezolvate in mod independent, care sunt apoi rezolvate in mod independent, poate duce uneori la calcularea de mai multe poate duce uneori la calcularea de mai multe ori a aceluiasi subcaz, si deci, la o eficienta ori a aceluiasi subcaz, si deci, la o eficienta scazuta a algoritmului. scazuta a algoritmului.
Primul principiu de baza al programarii Primul principiu de baza al programarii dinamice: evitarea calcularii de mai multe ori a dinamice: evitarea calcularii de mai multe ori a aceluiasi subcaz, prin memorarea rezultatelor aceluiasi subcaz, prin memorarea rezultatelor intermediare.intermediare.
Al doilea principiu fundamental al programarii Al doilea principiu fundamental al programarii dinamice este faptul ca ea opereaza de jos in dinamice este faptul ca ea opereaza de jos in sus (bottom-up). Se porneste de obicei de la sus (bottom-up). Se porneste de obicei de la cele mai mici subcazuri. Combinand solutiile cele mai mici subcazuri. Combinand solutiile lor, se obtin solutii pentru subcazuri din ce in lor, se obtin solutii pentru subcazuri din ce in ce mai mari, pina se ajunge, in final, la solutia ce mai mari, pina se ajunge, in final, la solutia cazului initial.cazului initial.
3 March 20093 March 2009 66
al treilea principiu fundamental, programarea al treilea principiu fundamental, programarea dinamica este utilizata pentru a optimiza o problema dinamica este utilizata pentru a optimiza o problema care satisface principiul optimalitatii: intr-o secventa care satisface principiul optimalitatii: intr-o secventa optima de decizii sau alegeri, fiecare subsecventa optima de decizii sau alegeri, fiecare subsecventa trebuie sa fie de asemenea optima. Cu toate ca pare trebuie sa fie de asemenea optima. Cu toate ca pare evident, acest principiu nu este intotdeauna valabil si evident, acest principiu nu este intotdeauna valabil si aceasta se intampla atunci cand subsecventele nu sunt aceasta se intampla atunci cand subsecventele nu sunt independente, adica atunci cand optimizarea unei independente, adica atunci cand optimizarea unei secvente intra in conflict cu optimizarea celorlalte secvente intra in conflict cu optimizarea celorlalte subsecvente.subsecvente.
3 March 20093 March 2009 77
AgricultorulAgricultorul
Pentru a mari productia de porumb un Pentru a mari productia de porumb un agricultor trebuie sa elimine toti porumbii care se agricultor trebuie sa elimine toti porumbii care se afla la distanta mai mica decat un X dat fata de afla la distanta mai mica decat un X dat fata de vecinii sai. Determinati porumbii care trebuie sa vecinii sai. Determinati porumbii care trebuie sa ramana cunoscand locul in care au iesit printr-o ramana cunoscand locul in care au iesit printr-o singura coordonata pe axa OX data.singura coordonata pe axa OX data.
3 March 20093 March 2009 88
DESCRIEREDESCRIERE
Folosim programare dinamica;Folosim programare dinamica; Construim vectorul l, l[i] reprezinta numarul Construim vectorul l, l[i] reprezinta numarul
maxim de porumbi pastrand porumbul I si maxim de porumbi pastrand porumbul I si eliminare incepe de la i+1;eliminare incepe de la i+1;
Productia maxima este egala cu l[1];Productia maxima este egala cu l[1]; Plecand de la primul porumb gasim primul de Plecand de la primul porumb gasim primul de
dupa el la distanta X care are productia de la el dupa el la distanta X care are productia de la el egala cu max-1;egala cu max-1;
3 March 20093 March 2009 99
type vector=array [-1..100] of integer;type vector=array [-1..100] of integer;var a,l:vector;p,n,h,i,j,max:integer;var a,l:vector;p,n,h,i,j,max:integer;procedure citire;procedure citire;var i:integer;var i:integer;beginbeginreadln(n,h);readln(n,h);for i:=1 to n dofor i:=1 to n doread(a[i]);read(a[i]);end;end;beginbegincitire;citire;l[n]:=1;l[n]:=1;for i:=n-1 downto 1 do beginfor i:=n-1 downto 1 do beginmax:=0;max:=0;for j:=i+1 to n dofor j:=i+1 to n doif (a[j]-a[i]>=h) and (l[j]>max) then max:=l[j];if (a[j]-a[i]>=h) and (l[j]>max) then max:=l[j];l[i]:=1+max;end;l[i]:=1+max;end;writeln(l[1]);writeln(l[1]);p:=1; max:=l[1];p:=1; max:=l[1];while max>0 dowhile max>0 dobeginbeginwrite(a[p],' ');write(a[p],' ');dec(max);dec(max);for i:=p+1 to n dofor i:=p+1 to n doif (a[i]-a[p]>=h) and (l[i]=max) then break;p:=i;if (a[i]-a[p]>=h) and (l[i]=max) then break;p:=i;end;end;end.end.
Sursaexecutabila
3 March 20093 March 2009 1010
type vector=array[1..10000] of integer;type vector=array[1..10000] of integer;
var a, v:vector;var a, v:vector;
var i ,j,max,n,gmax,x,p:integer;var i ,j,max,n,gmax,x,p:integer;
f,g:text;f,g:text;
beginbegin
assign(f,'porumbi.in'); reset(f);assign(f,'porumbi.in'); reset(f);
assign(g,'porumbi.out');rewrite(g);assign(g,'porumbi.out');rewrite(g);
read(f,n,x);read(f,n,x);
for i:= 1 to n dofor i:= 1 to n do
read(f,v[i]);read(f,v[i]);
a[n]:=1;a[n]:=1;
for i := n-1 downto 1 dofor i := n-1 downto 1 do
beginbegin
max:=0;max:=0;
for j:= i+1 to n dofor j:= i+1 to n do
if (v[j]-v[i]>=x)and(a[j]>max) thenif (v[j]-v[i]>=x)and(a[j]>max) then
max:=a[j];max:=a[j];
a[i]:=max+1;a[i]:=max+1;
end;end;
writeln(g,v[1],' ');writeln(g,v[1],' ');
p:= 1;p:= 1;
max:=a[1]-1;max:=a[1]-1;
for i:= 2 to n dofor i:= 2 to n do
if (v[i]-v[p]>=x) and(a[i]=max) thenif (v[i]-v[p]>=x) and(a[i]=max) then
beginbegin
write(g,v[i],' ');write(g,v[i],' ');
p:=i;p:=i;
dec(max);dec(max);
end;end;
close(g);close(g);
end.end.
Sursa executabilaSursa executabila
3 March 20093 March 2009 1111
2 5 6 9 10
X=2
N=5
2 5 6 9 10
3 March 20093 March 2009 1212
SolutiiSolutii
2 5 6 9 10
X=2
N=5
A:2 5 6 9 10
L:3 2 2 1 1
2 5 6 9 10
2 5 9
3 March 20093 March 2009 1313
3 March 20093 March 2009 1414
BIBLIOGRAFIECULEGERE DE PROBLEME PENTRU CLASA AXI-A;CAIET DE INFORMATICA;INTERNET;
SFARSIT.