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
Ultima versiune Ambele părți următoarea reviziune
laboratoare:laborator-11 [2017/05/11 22:44]
iulian.matesica
laboratoare:laborator-11 [2017/05/12 02:34]
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 ==== ==== Exerciții ====
laboratoare/laborator-11.txt · Ultima modificare: 2017/05/12 02:37 de către mihai.iacov