Unelte utilizator

Unelte site


laboratoare:laborator-11

Diferențe

Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.

Link către această vizualizare comparativă

Ambele părți revizuirea anterioară Versiuni anterioare
Urmatoarea versiune
Versiuni anterioare
laboratoare:laborator-11 [2017/02/19 14:30]
florina_elena.barbu
laboratoare:laborator-11 [2017/05/12 02:37]
mihai.iacov [2.3 Probleme tip rezolvate cu acest algoritm]
Linia 49: Linia 49:
  
 ===2.3.3 Combinări de n luate câte k === ===2.3.3 Combinări de n luate câte k ===
 +Fie C<sub>n,k</sub> notat şi C(n, k) = combinări de n luate câte k.
 +\\
 +Atunci C(n, k) = n! / ( k! (n-k)! ).
 +<note important>
 +Se poate deduce o formulă ce necesită o înmulţire şi o împărţire pentru calcularea unei combinări, deşi există o recurenţă mai bună.
 +  * C(n+1, k) = (n+1)! / (k! (n+1-k)! ) = ( (n+1) / (n+1-k) ) C(n, k);
 +
 +</note>
 +
 +Totodată, dacă definim polinoamele P(n) := (X + 1)<sup>n</sup> , atunci se pot rescrie P(n) = ∏ (C<sub>n,k</sub> X<sup>k</sup>), unde k = 0,1,2,...,n.
 +\\
 +\\
 +Fie coef(P, k) = coeficientul lui X<sup>k</sup> din polinomul P. Atunci putem scrie următoarele 2 proprietăţi:
 +  * P1. Adunarea polinoamelor se face prin adunarea coeficienţilor de pe aceleaşi poziţii:
 +\\
 +//coef(P1 + P2, k) = coef(P1, k) + coef(P2, k)//, pentru orice polinoame (P1, P2) şi pentru orice număr natural k.
 +  * P2. Înmulţirea cu un X mută coeficienţii lui X<sup>k</sup> la X<sup>k+1</sup>:
 +\\
 +//coef(P, k) = coef(X P, k+1)//, pentru orice polinom P şi pentru orice număr natural k.
 +
 +Putem deduce o legătură între coeficienţii polinoamelor de tipul P(n) dacă scriem P(n + 1) = (X + 1) P(n) = X P(n) + P(n).
 +
 +<note tip>
 +Folosind proprietăţile de mai sus, observăm:
 +  * coef(**P(n + 1), k**) = coef( X P(n), k) + coef(P(n), k) = **coef(P(n), k-1) + coef(P(n), k)**, pentru orice număr natural (k-1).
 +
 +Dar coef(P(n), k) = C(n, k), deci am obţinut o recurenţă ce foloseşte doar o adunare.
 +</note>
 +
 +==== Exerciții ====
 +
 +  - Construiți o funcție care calculează f(n), unde f = șirul lui Fibonacci;
 +  - Construiți o funcție care calculează f(n, k), unde f = combinări de n luate câte k;
 +  - implementați problema rucsacului;
 +  - Construiți o funcție care indică ordinea operațiilor la înmulțirea a N matrici pentru a minimiza numărul de înmulțiri între 2 numere;
 +  - construiți o funcție care calculează f(n) = 5<sup>n</sup> % k, unde k este o valoare fixată de la începutul programului;
 +  - Se dă un vector cu N elemente (v = [v1 v2 ... vn]) ce poate fi secționat în piese după următoarele reguli: a) inițial, tot vectorul reprezintă o piesă; b) o piesă poate reprezenta doar o bucată continuă (nu sare peste vreun element) din vectorul inițial; c) secționarea unei piese duce la înlocuirea piesei respective cu 2 piese mai mici, fără a se pierde niciun element din vector; d) valoarea unei piese este val = (lungimea piesei) x (suma elementelor din piesă). Găsiți secțiunile ce maximizează suma valorilor pieselor.
 +
 +===== 3. Exerciţii de laborator (Linux) =====
 +Pentru acest laborator puteți descărca scheletul de cod de [[http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab11_programare_dinamica-skel.zip|aici]]. Descărcați arhiva și dezarhivați-o. 
 +
 +=== Linux===
 +Puteti folosi utilitarul ''%%wget%%'' pentru descarcare si utilitarul ''%%unzip%%'' pentru dezarhivare.
 +
 +  * ''%%wget http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab11_programare_dinamica-skel.zip%%''
 +  * ''%%unzip lab11_programare_dinamica-skel.zip%%''
 +
 +Pentru compilare folositi comanda ''%%make%%''.
 +
laboratoare/laborator-11.txt · Ultima modificare: 2017/05/12 02:37 de către mihai.iacov