Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.
Ambele părți revizuirea anterioară Versiuni anterioare Urmatoarea versiune | Versiuni anterioare | ||
laboratoare:laborator-11 [2017/05/08 15:31] mihai.iacov [2.3 Probleme tip rezolvate cu acest algoritm] |
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< | ||
+ | \\ | ||
+ | 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); | ||
+ | |||
+ | </ | ||
+ | |||
+ | Totodată, dacă definim polinoamele P(n) := (X + 1)< | ||
+ | \\ | ||
+ | \\ | ||
+ | Fie coef(P, k) = coeficientul lui X< | ||
+ | * 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< | ||
+ | \\ | ||
+ | //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), | ||
+ | |||
+ | Dar coef(P(n), k) = C(n, k), deci am obţinut o recurenţă ce foloseşte doar o adunare. | ||
+ | </ | ||
==== Exerciții ==== | ==== Exerciții ==== | ||
Linia 54: | Linia 82: | ||
- Construiți o funcție care calculează f(n), unde f = șirul lui Fibonacci; | - 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; | - 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 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< | ||
+ | - 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:// | ||
+ | |||
+ | === Linux=== | ||
+ | Puteti folosi utilitarul '' | ||
+ | |||
+ | * '' | ||
+ | * '' | ||
+ | |||
+ | Pentru compilare folositi comanda '' | ||
+ |