Diferențe

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

Link către această vizualizare comparativă

--- laboratoare:laborator-11 [2017/05/11 22:44]
iulian.matesica
+++ laboratoare:laborator-11 [2017/05/12 02:37] (curent)
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 ===
+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 ====

Structuri de Date și Algoritmi (seria 1AB)

Unelte utilizator

Unelte site

Diferențe

Unelte pagină