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/11 22:44] iulian.matesica |
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 ==== |