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ă

Both sides previous revision Versiuni anterioare
Urmatoarea versiune
Versiuni anterioare
laboratoare:laborator-11 [2017/05/11 19:44]
iulian.matesica
laboratoare:laborator-11 [2017/05/11 23: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 ==== ==== Exerciții ====
laboratoare/laborator-11.txt · Ultima modificare: 2017/05/11 23:37 de către mihai.iacov