Tehnica Greedy
(Adăugător la punctul 2.3. (pag. 32) din manualul pentru clasa 11 INFORMATICA. Tehnici de programare.[1])
Este foarte dificil de a scrie forma generală a unei probleme rezolva folosind tehnica Greedy.
Să considerăm o mulţime A cu n elemente. Se cere o submulţime a sa cu m elemente (în cazul m=n este importantă ordinea alegerii elementelor), astfel încât să fie îndeplinite anumite condiţii (acestea diferă de la o problemă la alta).
Exemplu: se consideră o mulţime de n numere reale. Se cere o submulţime a sa, astfel încât suma elementelor sale să fie maximă.
Pentru rezolvare, vom alege un prim element al mulţimii de numere reale. Dacă este posibil, acesta va fi adăugat soluţiei, iniţial vide. Posibilitatea ca acesta să fie adăugat este dată de semnul numărului (acesta trebuie să fie mai mare ca O). Se alege un al doilea număr, cu care se procedează în mod asemănător. Algoritmul se încheie când au fost alese şl eventual adăugate toate elementele mulţimii.
Pentru a rezolva o problemă cu Greedy, soluţia se construieşte, după regula:
Pentru fiecare element care urmează să fie adăugat soluţiei finale, se efectuează o alegere a sa din elementele mulţimii A (după un mecanism specific fiecărei probleme în parte), iar dacă este posibil, acesta este adăugat. Algoritmul se termină fie când a fost găsită soluţia cerută, fie când s-a constatat inexistenţa acesteia.
Intuitiv, alegem un element, al doilea,....până când obţinem ce dorim sau până când au fost testate toate elementele mulţimii. De aici provine si numele metodei (greedy=lacom).
Greedy pare atât de simplă încât, la început, ne miră faptul că a fost evidenţiată ca tehnică. La o analiză atentă, vom observa că lucrurile nu stau chiar aşa. Exemplul prezentat este didactic (îl rezolvam şi fără să ştim că există această tehnică), el nu are alt rol decât de a evidenţia caracteristicile tehnicii.
Tehnica Greedy poate fi privita ca o particularizare a tehnicii Backtracking, în care se renunţa la mecanismul de Întoarcere.
Să analizăm în paralel, cele două tehnici, pentru a putea stabili asemănările şi diferenţele existente între ele:
=> ambele tehnici oferă soluţii sub formă de vector;
=> tehnica Backtracking poate oferi toate soluţiile problemei, în timp ce
tehnica Greedy oferă o singură soluţie => tehnica Greedy nu dispune de mecanismul întoarcerii, specific tehnicii Backtracking. :
Aceasta este diferenţa esenţială dintre cele doua tehnici, diferenţă care are consecinţe uriaşe în ce priveşte aplicabilitatea lor.
Consecinţa 1.
Este necesar ca cel care elaborează un algoritm Greedy să ştie faptul ca, procedând în modul ales de el, ajunge la rezultatul dorit. Pentru fiecare problemă în parte, după ce se identifica un algoritm, este obligatoriu să se demonstreze că acesta conduce la soluţia optima. Demonstraţia faptului ca se ajunge la soluţia optimă este specifică fiecărei probleme în parte.
Consecinţa 2. Tehnica Greedy conduce la timp de calcul polinomial.
Motivul care conduce la acest timp de calcul, tine de mecanismul tehnicii. Să presupunem că mulţimea din care se face alegerea are n elemente si că soluţia are tot n elemente (caz maxim). Se fac n alegeri, la fiecare alegere se fac n teste, rezulta un algoritm cu timp O(n2).
De multe ori, este necesar ca elementele mulţimii. A să fie sortate, pentru ca apoi să alegem din acestea, iar sortarea necesita un timp minim O(n x log2n). Insă sortarea se efectuează la început. Prin urmare, acest timp se adună, deci nu influenţează rezultatul.
0 întrebare firească: fiind dată o problemă, există întotdeauna un algoritm de tip Greedy care găseşte soluţia optimă? Evident, NU. Există probleme pentru care nu se cunosc astfel de algoritmi. Mai mult, pentru cele mai multe probleme nu se cunosc algoritmi Greedy.
Avantajul timpului polinomial, conduce la necesitatea utilizării tehnicii Greedy. Din alt punct de vedere, nu tuturor problemelor li se pot aplica algoritmi de acest tip. Ce este de făcut?
=> Pentru problemele pentru care nu se cunosc algoritmi care necesită timp polinomial, se caută soluţii, chiar dacă nu obţine, dar apropiate de acestea, dar care au fost obţinute în timp util. Multe din aceste soluţii sunt obţinute cu Greedy.
Astfel de algoritmi se numesc algoritmi euristici.
În continuare, vom da mai multe exemple de probleme care se rezolvă cu Greedy.
Probleme pentru care Greedy obţine soluţia optimă
Problema banilor (Problema nr. 7, testul 3 Bacalaureat 2002.)
Scrieţi un program, care afişează modalitatea de plată, folosind un număr minim de bancnote, a unei sume întregi S de lei (S<20000). Plata se efectuează folosind bancnote cu valoarea 1, 5, 10, 50, 100, 200 şi 500 de lei. Numărul de bancnote de fiecare valoare se citeşte din fişierul text BANI.IN, care conţine 7 rânduri, în fiecare din care sunt indicate numărul de bancnote respectiv de 1, 5, 10, 50, 100, 200 şi 500 de lei.
Intrare: Fişierul text BANI.IN şi de la tastatură se citeşte suma S.
Ieşire: Dacă e posibil de plătit această sumă S, atunci la ecran se va afişa valoarea bancnotei şi numărul de bancnote respective utilizate la plată. Dacă bancnote de careva valoare nu se folosesc, atunci nu se afişează această valoare. Dacă nu este posibil de efectuat plata cu bancnotele indicate – afişaţi mesajul respectiv.
Menţionăm, că probleme asemănătoare, cu banii, sunt mai multe. De obicei se presupune că bancnote de fiecare fel avem oricât de multe. Această problemă ne limitează numărul de bancnote.
Ideea algoritmului de rezolvare a aceste probleme constă în faptul că trebuie să începem eliberarea restului de la cea mai mare bancnotă. Există 2 variante, dacă suma necesară e mai mare ca produsul dintre numărul de bancnote şi nominalul atunci se iau toate bancnotele de acest nominal, dacă nu – atunci se iau atâtea bancnote, câte „încap”, care se află prin împărţirea sumei rămase la nominal. Pentru rezolvare se foloseşte un tablou cu 3 rânduri şi 7 coloane (pentru fiecare nominal câte o coloană). În primul rând al tabloului vom păstra nominalul bancnotelor, în al doilea rând - numărul bancnotelor citite din fişier şi în al treilea rând - numărul bancnotelor obţinute la schimb, practice ceea ce aflăm.
Calculul se va începe cu coloana a 7, adică începem de la sfârşit.
Program V3P7_02;
type tablou=array[1..3,1..7] of integer;
var s,ss,i : integer; a:tablou; f:text;
{In primul rind al tabelului vom pastra nominalul bancnotelor}
{In al doilea rind - numarul bancnotelor citite din fisier}
{In al treilea rind - numarul bancnotelor obtinute la schimb}
Procedure Afisare(sa:integer);
begin writeln('suma ',s);
if sa<>0
then writeln('nu poate fi transformata cu bancnotele date ')
else
begin writeln('se plateste cu urmatoarele bancnote');
for i:=1 to 7 do
if a[3,i]<>0
then writeln('bancnote de ',a[1,i]:6,' sau folosit ',a[3,i]);
end
end; { Afisare }
Procedure calcul(var sa:integer);
var nb:integer;
begin
i:=7;
while (i>=1) and (sa>0) do
begin nb:=sa div a[1,i];
if nb<>0 then if nb>= a[2,i]
then a[3,i]:=a[2,i]
else a[3,i]:=nb;
sa:=sa-a[3,i]*a[1,i];
i:=i-1;
end;
end; { calcul }
begin
a[1,1]:=1; a[1,2]:=5; a[1,3]:=10; a[1,4]:=50;
a[1,5]:=100; a[1,6]:=200; a[1,7]:=500;
assign (f,'bani.in'); reset(f);
for i:=1 to 7 do readln(f,a[2,i]);
write ('introduceti suma de lei S ');readln(s);
ss:=s; calcul(ss); Afisare(ss);
end.
Problema rucsacului (nr. 6, pag. 35 [1])
O persoană are un rucsac cu care poate transporta o greutate maximă G. Persoana are la dispoziţie n obiecte si cunoaşte pentru fiecare obiect greutatea si câştigul care se obţine în urma transportului său la destinaţie. Se cere să se precizeze ce obiecte trebuie să transporte persoana în aşa fel încât câştigul sa fie maxim.
O precizare în plus transformă această problema în alte două probleme distincte. Această precizare se referă la faptul că obiectele pot fi sau nu tăiate pentru transportul la destinaţie. In prima situaţie, problema poartă numele de problema continuă a rucsacului, iar în a doua avem problema discreta a rucsacului. Aceste două probleme se rezolvă diferit Varianta continuă a problemei rucsacului este rezolvată mai jos, iar cea discretă se rezolvă cu ajutorul programării dinamice.
Problema continuă a rucsacului, în care persoana are posibilitatea să taie obiectele. În acest fel, se poate obţine o încărcare mai eficientă a rucsacului.
Algoritmul este următorul:
• se calculează, pentru fiecare obiect în parte, eficienţa de transport rezultată prin împărţirea câştigului la greutate (de fapt, acesta reprezintă câştigul obţinut prin transportul unităţii de greutate);
• obiectele se sortează în ordine descrescătoare a eficienţei de transport si se preiau în calcul în această ordine;
• câştigul iniţial va fi 0, iar greutatea rămasă de încărcat va fi greutatea rucsacului;
• atât timp cât nu a fost completată greutatea maximă a rucsacului si nu au fost luate in considerare toate obiectele, se procedează astfel:
• dintre obiectele neîncărcate se selectează acela cu cea mai ridicată eficienţă de transport şi avem două posibilităţi:
• acesta încape în totalitate în rucsac, deci se scade din greutatea rămasă de încărcat greutatea obiectului, la câştig se cumulează câştigul datorat transportului acestui obiect; se tipăreşte 1, în sensul că întregul obiect a fost încărcat;
• obiectul nu încape în totalitate în rucsac, caz în care se calculează ce parte din el poate fi transportată, se cumulează câştigul obţinut cu transportul acestei părţi din obiect, se tipăreşte procentul care s-a încărcat din obiect, iar greutatea rămasă de încărcat devine 0.
Vom considera un exemplu numeric.
Greutatea care poate fi transportată cu ajutorul rucsacului aste 3
Avem la dispoziţie 3 obiecte. Greutatea şi câştigul pentru fiecare obiect sunt prezentate mai jos:
Eficienţa de transport este 1 pentru primul obiect, 4 pentru al doilea si 2 pentru al treilea.
In concluzie, obiectul 2 se încarcă în întregime în rucsac, obţinând un câştig de 4 şi rămâne o capacitate de transport de două unităţi de greutate.
Se încarcă 2/3 din obiectul 3 (care este al doilea în ordinea eficienţei de transport) pentru care se obţine câştigul 4. Câştigul obţinut în total este 8. Se remarca strategia Greedy prin alegerea obiectului care va fi transportat, alegere asupra căreia nu se revine.
program rucsac;
type tablou=array [1..4] of real;
matrice=array [1..10] of tablou;
{In prima coloana se inscrie costul,
In a II - greutatea, in a III - eficienta,
si in a IV - a cata parte se ia
tabloul c il folosim la sortare, "al treilea pahar"}
var a:matrice; c:tablou; f:text;
loc,n,g,i,j:integer; max,castig,dg:real;
begin
assign (f,'rucsac.txt'); reset (f);
readln(f,n,g);
for i:=1 to n do
begin readln(f,a[i,1],a[i,2]);
a[i,3]:=a[i,1]/a[i,2]; a[i,4]:=0;
end;
{sortam tabloul dupa eficienta}
for i:=1 to n-1 do
begin max:=a[i,3];loc:=i;
for j:=i+1 to n do
if a[j,3]>max then begin max:=a[j,3]; loc:=j; end;
c:=a[i]; a[i]:=a[loc]; a[loc]:=c;
end;
{Aflam cat din fiecare obiect se pune in rucsac si calculam castigul}
castig:=0;
i:=1; dg:=g;
writeln ('greutatea ','costul ','eficienta ','rucsac');
while (i<=n) and (dg>0) do
begin;
if dg>=a[i,2]
then begin castig:=castig+a[i,1];
dg:=dg-a[i,2]; a[i,4]:=1;
end
else begin castig:=castig+dg*a[i,3];
a[i,4]:=dg/a[i,2];dg:=0;
end;
writeln (a[i,1]:6:2,a[i,2]:8:2,a[i,3]:12:2,a[i,4]:10:2);
i:=i+1;
end;
writeln ('greutatea rucsacului este ',g-dg:0:2);
writeln ('costul este ',castig:0:2);
end.
Variabile statice şi variabile dinamice.
(Acest material a fost pregătit la Şcoala de Vară la Informatică 2003 de către grupa A, sub conducerea dlui S. Corlat.
Acest material îl puteţi vedea la www.cnti.moldnet.md)
Variabilele pot fi statice sau dinamice. Cele statice au o zonă de memorie bine definită. Structura, locul, tipul acestei zone nu poate fi schimbată în procesul execuţiei programului. Accesul la variabilele statice se face direct, după nume. Structurile statice de date au un număr fix de elemente, care nu poate fi modificat. Alocarea memoriei se face într-un spaţiu strict determinat al memoriei, care permite adresarea directă.
O altă categorie de variabile, accesibile în limbajul Pascal este cea dinamică. Pentru acest tip de variabile poate fi modificat volumul de memorie rezervat, ceea ce face mai flexibilă alocarea memoriei în procesul de lucru al programului. Structurile dinamice pot acumula elemente în procesul de funcţionare al programului, sau pot lichida elementele ce au devenit neutilizabile. Accesul la aceste variabile şi declararea lor se face în mod diferit de cel al variabilelor statice. Accesarea (definirea) este indirectă, prin intermediul unui tip mediator de variabile – tipul referinţă.
Variabile de tip referinţă conţin referiri (adresări indirecte) la variabilele dinamice. Referirea se realizează prin memorarea în variabila referinţă a adresei unde e stocată variabila dinamică.
Pentru variabilele tip referinţă se alocă un spaţiu de memorie de 4 octeţi, care conţin adresa variabilei dinamice. Memoria pentru variabilele dinamice se alocă dintr-o zonă specială, care foloseşte adresarea indirectă, numită heap. Această zonă este diferită de zona pentru variabilele statice.
Variabilele dinamice ocupă un spaţiu de memorie în corespundere cu tipul lor: Integer, real, string etc.
Definirea tipului referinţă.
Pentru a defini un tip referinţă vom folosi secţiunea Type în blocul de declarare a variabilelor. Procedura de definire este următoarea:
type = ^;
^ - se citeşte ca “pointer la…” sau “adresare la…“
Mulţimea valorilor variabilelor tip referinţă este formată dintr-o mulţime de adrese, fiecare din ele identificând o variabilă dinamică. Mulţimea de valori mai e completată prin valoarea Nil, care nu conţine nici o adresă.
zona HEAP
Memoria
program
zona variabilelor statice
variabilă tip referinţă (4 bytes) ® adresa variabilei dinamice
variabila dinamică referităSchema de lucru a variabilelor referinţă:
(Adăugător la punctul 2.3. (pag. 32) din manualul pentru clasa 11 INFORMATICA. Tehnici de programare.[1])
Este foarte dificil de a scrie forma generală a unei probleme rezolva folosind tehnica Greedy.
Să considerăm o mulţime A cu n elemente. Se cere o submulţime a sa cu m elemente (în cazul m=n este importantă ordinea alegerii elementelor), astfel încât să fie îndeplinite anumite condiţii (acestea diferă de la o problemă la alta).
Exemplu: se consideră o mulţime de n numere reale. Se cere o submulţime a sa, astfel încât suma elementelor sale să fie maximă.
Pentru rezolvare, vom alege un prim element al mulţimii de numere reale. Dacă este posibil, acesta va fi adăugat soluţiei, iniţial vide. Posibilitatea ca acesta să fie adăugat este dată de semnul numărului (acesta trebuie să fie mai mare ca O). Se alege un al doilea număr, cu care se procedează în mod asemănător. Algoritmul se încheie când au fost alese şl eventual adăugate toate elementele mulţimii.
Pentru a rezolva o problemă cu Greedy, soluţia se construieşte, după regula:
Pentru fiecare element care urmează să fie adăugat soluţiei finale, se efectuează o alegere a sa din elementele mulţimii A (după un mecanism specific fiecărei probleme în parte), iar dacă este posibil, acesta este adăugat. Algoritmul se termină fie când a fost găsită soluţia cerută, fie când s-a constatat inexistenţa acesteia.
Intuitiv, alegem un element, al doilea,....până când obţinem ce dorim sau până când au fost testate toate elementele mulţimii. De aici provine si numele metodei (greedy=lacom).
Greedy pare atât de simplă încât, la început, ne miră faptul că a fost evidenţiată ca tehnică. La o analiză atentă, vom observa că lucrurile nu stau chiar aşa. Exemplul prezentat este didactic (îl rezolvam şi fără să ştim că există această tehnică), el nu are alt rol decât de a evidenţia caracteristicile tehnicii.
Tehnica Greedy poate fi privita ca o particularizare a tehnicii Backtracking, în care se renunţa la mecanismul de Întoarcere.
Să analizăm în paralel, cele două tehnici, pentru a putea stabili asemănările şi diferenţele existente între ele:
=> ambele tehnici oferă soluţii sub formă de vector;
=> tehnica Backtracking poate oferi toate soluţiile problemei, în timp ce
tehnica Greedy oferă o singură soluţie => tehnica Greedy nu dispune de mecanismul întoarcerii, specific tehnicii Backtracking. :
Aceasta este diferenţa esenţială dintre cele doua tehnici, diferenţă care are consecinţe uriaşe în ce priveşte aplicabilitatea lor.
Consecinţa 1.
Este necesar ca cel care elaborează un algoritm Greedy să ştie faptul ca, procedând în modul ales de el, ajunge la rezultatul dorit. Pentru fiecare problemă în parte, după ce se identifica un algoritm, este obligatoriu să se demonstreze că acesta conduce la soluţia optima. Demonstraţia faptului ca se ajunge la soluţia optimă este specifică fiecărei probleme în parte.
Consecinţa 2. Tehnica Greedy conduce la timp de calcul polinomial.
Motivul care conduce la acest timp de calcul, tine de mecanismul tehnicii. Să presupunem că mulţimea din care se face alegerea are n elemente si că soluţia are tot n elemente (caz maxim). Se fac n alegeri, la fiecare alegere se fac n teste, rezulta un algoritm cu timp O(n2).
De multe ori, este necesar ca elementele mulţimii. A să fie sortate, pentru ca apoi să alegem din acestea, iar sortarea necesita un timp minim O(n x log2n). Insă sortarea se efectuează la început. Prin urmare, acest timp se adună, deci nu influenţează rezultatul.
0 întrebare firească: fiind dată o problemă, există întotdeauna un algoritm de tip Greedy care găseşte soluţia optimă? Evident, NU. Există probleme pentru care nu se cunosc astfel de algoritmi. Mai mult, pentru cele mai multe probleme nu se cunosc algoritmi Greedy.
Avantajul timpului polinomial, conduce la necesitatea utilizării tehnicii Greedy. Din alt punct de vedere, nu tuturor problemelor li se pot aplica algoritmi de acest tip. Ce este de făcut?
=> Pentru problemele pentru care nu se cunosc algoritmi care necesită timp polinomial, se caută soluţii, chiar dacă nu obţine, dar apropiate de acestea, dar care au fost obţinute în timp util. Multe din aceste soluţii sunt obţinute cu Greedy.
Astfel de algoritmi se numesc algoritmi euristici.
În continuare, vom da mai multe exemple de probleme care se rezolvă cu Greedy.
Probleme pentru care Greedy obţine soluţia optimă
Problema banilor (Problema nr. 7, testul 3 Bacalaureat 2002.)
Scrieţi un program, care afişează modalitatea de plată, folosind un număr minim de bancnote, a unei sume întregi S de lei (S<20000). Plata se efectuează folosind bancnote cu valoarea 1, 5, 10, 50, 100, 200 şi 500 de lei. Numărul de bancnote de fiecare valoare se citeşte din fişierul text BANI.IN, care conţine 7 rânduri, în fiecare din care sunt indicate numărul de bancnote respectiv de 1, 5, 10, 50, 100, 200 şi 500 de lei.
Intrare: Fişierul text BANI.IN şi de la tastatură se citeşte suma S.
Ieşire: Dacă e posibil de plătit această sumă S, atunci la ecran se va afişa valoarea bancnotei şi numărul de bancnote respective utilizate la plată. Dacă bancnote de careva valoare nu se folosesc, atunci nu se afişează această valoare. Dacă nu este posibil de efectuat plata cu bancnotele indicate – afişaţi mesajul respectiv.
Menţionăm, că probleme asemănătoare, cu banii, sunt mai multe. De obicei se presupune că bancnote de fiecare fel avem oricât de multe. Această problemă ne limitează numărul de bancnote.
Ideea algoritmului de rezolvare a aceste probleme constă în faptul că trebuie să începem eliberarea restului de la cea mai mare bancnotă. Există 2 variante, dacă suma necesară e mai mare ca produsul dintre numărul de bancnote şi nominalul atunci se iau toate bancnotele de acest nominal, dacă nu – atunci se iau atâtea bancnote, câte „încap”, care se află prin împărţirea sumei rămase la nominal. Pentru rezolvare se foloseşte un tablou cu 3 rânduri şi 7 coloane (pentru fiecare nominal câte o coloană). În primul rând al tabloului vom păstra nominalul bancnotelor, în al doilea rând - numărul bancnotelor citite din fişier şi în al treilea rând - numărul bancnotelor obţinute la schimb, practice ceea ce aflăm.
Calculul se va începe cu coloana a 7, adică începem de la sfârşit.
Program V3P7_02;
type tablou=array[1..3,1..7] of integer;
var s,ss,i : integer; a:tablou; f:text;
{In primul rind al tabelului vom pastra nominalul bancnotelor}
{In al doilea rind - numarul bancnotelor citite din fisier}
{In al treilea rind - numarul bancnotelor obtinute la schimb}
Procedure Afisare(sa:integer);
begin writeln('suma ',s);
if sa<>0
then writeln('nu poate fi transformata cu bancnotele date ')
else
begin writeln('se plateste cu urmatoarele bancnote');
for i:=1 to 7 do
if a[3,i]<>0
then writeln('bancnote de ',a[1,i]:6,' sau folosit ',a[3,i]);
end
end; { Afisare }
Procedure calcul(var sa:integer);
var nb:integer;
begin
i:=7;
while (i>=1) and (sa>0) do
begin nb:=sa div a[1,i];
if nb<>0 then if nb>= a[2,i]
then a[3,i]:=a[2,i]
else a[3,i]:=nb;
sa:=sa-a[3,i]*a[1,i];
i:=i-1;
end;
end; { calcul }
begin
a[1,1]:=1; a[1,2]:=5; a[1,3]:=10; a[1,4]:=50;
a[1,5]:=100; a[1,6]:=200; a[1,7]:=500;
assign (f,'bani.in'); reset(f);
for i:=1 to 7 do readln(f,a[2,i]);
write ('introduceti suma de lei S ');readln(s);
ss:=s; calcul(ss); Afisare(ss);
end.
Problema rucsacului (nr. 6, pag. 35 [1])
O persoană are un rucsac cu care poate transporta o greutate maximă G. Persoana are la dispoziţie n obiecte si cunoaşte pentru fiecare obiect greutatea si câştigul care se obţine în urma transportului său la destinaţie. Se cere să se precizeze ce obiecte trebuie să transporte persoana în aşa fel încât câştigul sa fie maxim.
O precizare în plus transformă această problema în alte două probleme distincte. Această precizare se referă la faptul că obiectele pot fi sau nu tăiate pentru transportul la destinaţie. In prima situaţie, problema poartă numele de problema continuă a rucsacului, iar în a doua avem problema discreta a rucsacului. Aceste două probleme se rezolvă diferit Varianta continuă a problemei rucsacului este rezolvată mai jos, iar cea discretă se rezolvă cu ajutorul programării dinamice.
Problema continuă a rucsacului, în care persoana are posibilitatea să taie obiectele. În acest fel, se poate obţine o încărcare mai eficientă a rucsacului.
Algoritmul este următorul:
• se calculează, pentru fiecare obiect în parte, eficienţa de transport rezultată prin împărţirea câştigului la greutate (de fapt, acesta reprezintă câştigul obţinut prin transportul unităţii de greutate);
• obiectele se sortează în ordine descrescătoare a eficienţei de transport si se preiau în calcul în această ordine;
• câştigul iniţial va fi 0, iar greutatea rămasă de încărcat va fi greutatea rucsacului;
• atât timp cât nu a fost completată greutatea maximă a rucsacului si nu au fost luate in considerare toate obiectele, se procedează astfel:
• dintre obiectele neîncărcate se selectează acela cu cea mai ridicată eficienţă de transport şi avem două posibilităţi:
• acesta încape în totalitate în rucsac, deci se scade din greutatea rămasă de încărcat greutatea obiectului, la câştig se cumulează câştigul datorat transportului acestui obiect; se tipăreşte 1, în sensul că întregul obiect a fost încărcat;
• obiectul nu încape în totalitate în rucsac, caz în care se calculează ce parte din el poate fi transportată, se cumulează câştigul obţinut cu transportul acestei părţi din obiect, se tipăreşte procentul care s-a încărcat din obiect, iar greutatea rămasă de încărcat devine 0.
Vom considera un exemplu numeric.
Greutatea care poate fi transportată cu ajutorul rucsacului aste 3
Avem la dispoziţie 3 obiecte. Greutatea şi câştigul pentru fiecare obiect sunt prezentate mai jos:
Eficienţa de transport este 1 pentru primul obiect, 4 pentru al doilea si 2 pentru al treilea.
In concluzie, obiectul 2 se încarcă în întregime în rucsac, obţinând un câştig de 4 şi rămâne o capacitate de transport de două unităţi de greutate.
Se încarcă 2/3 din obiectul 3 (care este al doilea în ordinea eficienţei de transport) pentru care se obţine câştigul 4. Câştigul obţinut în total este 8. Se remarca strategia Greedy prin alegerea obiectului care va fi transportat, alegere asupra căreia nu se revine.
program rucsac;
type tablou=array [1..4] of real;
matrice=array [1..10] of tablou;
{In prima coloana se inscrie costul,
In a II - greutatea, in a III - eficienta,
si in a IV - a cata parte se ia
tabloul c il folosim la sortare, "al treilea pahar"}
var a:matrice; c:tablou; f:text;
loc,n,g,i,j:integer; max,castig,dg:real;
begin
assign (f,'rucsac.txt'); reset (f);
readln(f,n,g);
for i:=1 to n do
begin readln(f,a[i,1],a[i,2]);
a[i,3]:=a[i,1]/a[i,2]; a[i,4]:=0;
end;
{sortam tabloul dupa eficienta}
for i:=1 to n-1 do
begin max:=a[i,3];loc:=i;
for j:=i+1 to n do
if a[j,3]>max then begin max:=a[j,3]; loc:=j; end;
c:=a[i]; a[i]:=a[loc]; a[loc]:=c;
end;
{Aflam cat din fiecare obiect se pune in rucsac si calculam castigul}
castig:=0;
i:=1; dg:=g;
writeln ('greutatea ','costul ','eficienta ','rucsac');
while (i<=n) and (dg>0) do
begin;
if dg>=a[i,2]
then begin castig:=castig+a[i,1];
dg:=dg-a[i,2]; a[i,4]:=1;
end
else begin castig:=castig+dg*a[i,3];
a[i,4]:=dg/a[i,2];dg:=0;
end;
writeln (a[i,1]:6:2,a[i,2]:8:2,a[i,3]:12:2,a[i,4]:10:2);
i:=i+1;
end;
writeln ('greutatea rucsacului este ',g-dg:0:2);
writeln ('costul este ',castig:0:2);
end.
Variabile statice şi variabile dinamice.
(Acest material a fost pregătit la Şcoala de Vară la Informatică 2003 de către grupa A, sub conducerea dlui S. Corlat.
Acest material îl puteţi vedea la www.cnti.moldnet.md)
Variabilele pot fi statice sau dinamice. Cele statice au o zonă de memorie bine definită. Structura, locul, tipul acestei zone nu poate fi schimbată în procesul execuţiei programului. Accesul la variabilele statice se face direct, după nume. Structurile statice de date au un număr fix de elemente, care nu poate fi modificat. Alocarea memoriei se face într-un spaţiu strict determinat al memoriei, care permite adresarea directă.
O altă categorie de variabile, accesibile în limbajul Pascal este cea dinamică. Pentru acest tip de variabile poate fi modificat volumul de memorie rezervat, ceea ce face mai flexibilă alocarea memoriei în procesul de lucru al programului. Structurile dinamice pot acumula elemente în procesul de funcţionare al programului, sau pot lichida elementele ce au devenit neutilizabile. Accesul la aceste variabile şi declararea lor se face în mod diferit de cel al variabilelor statice. Accesarea (definirea) este indirectă, prin intermediul unui tip mediator de variabile – tipul referinţă.
Variabile de tip referinţă conţin referiri (adresări indirecte) la variabilele dinamice. Referirea se realizează prin memorarea în variabila referinţă a adresei unde e stocată variabila dinamică.
Pentru variabilele tip referinţă se alocă un spaţiu de memorie de 4 octeţi, care conţin adresa variabilei dinamice. Memoria pentru variabilele dinamice se alocă dintr-o zonă specială, care foloseşte adresarea indirectă, numită heap. Această zonă este diferită de zona pentru variabilele statice.
Variabilele dinamice ocupă un spaţiu de memorie în corespundere cu tipul lor: Integer, real, string etc.
Definirea tipului referinţă.
Pentru a defini un tip referinţă vom folosi secţiunea Type în blocul de declarare a variabilelor. Procedura de definire este următoarea:
type
^ - se citeşte ca “pointer la…” sau “adresare la…“
Mulţimea valorilor variabilelor tip referinţă este formată dintr-o mulţime de adrese, fiecare din ele identificând o variabilă dinamică. Mulţimea de valori mai e completată prin valoarea Nil, care nu conţine nici o adresă.
zona HEAP
Memoria
program
zona variabilelor statice
variabilă tip referinţă (4 bytes) ® adresa variabilei dinamice
variabila dinamică referităSchema de lucru a variabilelor referinţă:
type pointReal = ^Real;var ar, br, cr : pointReal;
Exemplu
type pointReal = ^Real;
var ar, br, cr : pointReal;
Begin
New (ar); New (br); New (cr);
Readln (ar^, br^);
cr^ := ar^+ br^;
Writeln (cr^);
End.
Variabila tip_referinţă păstrează adresa adresei variabilei dinamice. Pentru a putea utiliza variabilele dinamice în program ele trebuie iniţializate prin procedura NEW.
Ca variabilele dinamice pot fi declarate şi structuri de tip Record, iar tipul lor poate fi definit (declarat) mai târziu, dat în aceaşi secţiune de declaraţii type:
type num_complex = ^complex;
complex = record
re, im : Real
end;
var
num1, num2 : num_complex;
num3 : ^complex;
simbol : ^char;
De cele mai multe ori însă, variabilele dinamice se folosesc în calitate de structuri, stocate în HEAP. Să vedem cum se formează structurile dinamice de date.
Logica creării unei liste (este cea mai simplă structură) e următoarea: pentru fiecare element al listei vom avea nevoie de spaţiu pentru el însuşi şi de spaţiu pentru adresa elementului următor al listei.
Exemplu:
type lista = ^element;
element = record
a: integer,
urmator : lista
end;
Var lis : lista;
Schema creării listei:
type pointReal = ^Real;
var ar, br, cr : pointReal;
Begin
New (ar); New (br); New (cr);
Readln (ar^, br^);
cr^ := ar^+ br^;
Writeln (cr^);
End.
Variabila tip_referinţă păstrează adresa adresei variabilei dinamice. Pentru a putea utiliza variabilele dinamice în program ele trebuie iniţializate prin procedura NEW.
Ca variabilele dinamice pot fi declarate şi structuri de tip Record, iar tipul lor poate fi definit (declarat) mai târziu, dat în aceaşi secţiune de declaraţii type:
type num_complex = ^complex;
complex = record
re, im : Real
end;
var
num1, num2 : num_complex;
num3 : ^complex;
simbol : ^char;
De cele mai multe ori însă, variabilele dinamice se folosesc în calitate de structuri, stocate în HEAP. Să vedem cum se formează structurile dinamice de date.
Logica creării unei liste (este cea mai simplă structură) e următoarea: pentru fiecare element al listei vom avea nevoie de spaţiu pentru el însuşi şi de spaţiu pentru adresa elementului următor al listei.
Exemplu:
type lista = ^element;
element = record
a: integer,
urmator : lista
end;
Var lis : lista;
Schema creării listei:
Aşa dar, memorarea şi atribuirea valorilor se realizează după schema:a. declararea variabilei dinamice
b. alocarea memoriei pentru variabila dinamică prin procedura
New (nume variabilă dinamică)
c. atribuirea valorii numerice prin unul din procedeele standard.
Eliberarea memoriei ocupate de variabila dinamică se va realiza prin procedura
Dispose (nume variabilă dinamică)
type lista = ^element;
element = record
a: integer; {elementul propriu zis}
urmator : lista {adresa următorului element al listei}
end;
Var
lisinit, liscurent : lista;
raspuns : char;
begin
lisinit := Nil; {lista nu contine nici un element, ea se initializeaza}
repeat
begin
New(liscurent); {un nou element in lista }
Writeln ('Elementul curent');
readln(liscurent^.a); {dam valori elemetului listei}
liscurent^.urmator := lisinit;
{indicam urmatoarea adresă, acea a primului element din listă, transformîndu-l în al doilea. De fapt plasăm elementul la începutul listei, împingîndu-le pe toate celelalte spre dreapta}
lisinit:=liscurent; {Lista nou formată o memorăm în variabila listinit}
writeln ('Continuati? [D - Da, N / Nu]'); readln(raspuns);
end;
until (raspuns='N') or (raspuns='n');
while liscurent <> Nil do
begin
writeln (liscurent^.a);
liscurent:= liscurent^.urmator;
end;
end.
6
Nil
2
4
Nil
2
4
Nil
2
lisinit
Nil Astfel prgramul prezentat mai sus crează mai întâi o listă dinamică vidă, apoi adaugă elemente în stânga ei până nu întrerupem operaţia. Întrucât la fiecare iteraţie noi revenim la începutul listei, realizăm parcurgerea ei pentru a tipări elementele.
În continuare propunem rezolvarea problemei 1 pagina 192.function nr(b:AdresaCelula):AdresaCelula;
{ Returneaza adresa virfului - recursie }
begin
if b^.urm=nil then nr:=b
else nr:=nr(b^.urm);
end; { nr}
function nr1 (b:AdresaCelula):AdresaCelula;
{ Returneaza adresa virfului - iteratii }
var i, pr : AdresaCelula;
begin i:=b;
while i<>nil do begin nr1:=i; i:=i^.urm; end;end; { nr1}
Сообщения
Комментариев нет:
Отправить комментарий