Calculul combinărilor de n luate câte k (nCk) în C++
Această problemă poate apărea sub mai multe forme:
- Dându-se două numere naturale $n$ și $k$, să se afle numărul combinărilor de $n$ luate câte $k$: $C_n^k$.
- Într-o clasă sunt $n$ elevi, dintre care doar $k$ pot fi selectați în echipa clasei de fotbal. Câte modalități de alegere a echipei sunt, știind că ordinea elevilor nu contează?
- Să se afle coeficientul lui $x^k$ din dezvoltarea binomului $(1 + x)^n$.
Formula numărului de combinări
Numărul de combinări este egal cu $C_n^k = \cfrac{n!}{k!(n-k)!}$.
Exemplu
Pentru $n = 5$ și $k = 3$, avem $C_5^3 = \cfrac{5!}{3! \cdot 2!} = \cfrac{120}{6 \cdot 2} = \cfrac{120}{12} = 10$.
Se consideră că pentru $k > n$, $C_n^k = 0$.
Calcularea combinărilor (metodă normală)
O metodă obișnuită calculează factorialele celor trei numere dorite — n, k
și n - k, după care se afișează formula menționată mai devreme.
Implementare C++
Avem următoarea implementare în C++:
#include <iostream>
using namespace std;
int main()
{
//Citim și declarăm variabilele n și k
int n, k;
cin >> n >> k;
//Determinăm factorialele dorite
int factn = 1, factk = 1, factnk = 1; //n!, k! și (n - k)!
for(int i = 1; i <= n; i++)
factn = factn * i;
for(int i = 1; i <= k; i++)
factk = factk * i;
for(int i = 1; i <= n - k; i++)
factnk = factnk * i;
//Calculăm și afișăm numărul de combinări
int nCk = factn / (factk * factnk);
cout << nCk;
return 0;
}
O metodă care evită factorialele
Putem calcula combinările direct, înmulțind și împărțind pe rând, fără a ajunge la valori uriașe. După pasul i, valoarea este $C_{n-k+i}^{i}$, deci este mereu un număr întreg și împărțirea este exactă. Înmulțirea trebuie făcută înaintea împărțirii:
int n, k;
long long nCk = 1;
cin >> n >> k;
for(int i = 1; i <= k; i++) {
nCk = nCk * (n - k + i) / i;
}
cout << nCk;
Calcularea combinărilor mai mari
Factorialele cresc foarte repede — 13! nici măcar nu intră în tipul de date
int. Desigur, putem să extindem limita folosind tipul de date long long,
însă o să întâlnim destul de rapid o limită.
Unele probleme cer răspunsul combinărilor modulo un anumit număr prim. Prin
această operație, putem să folosim tipul de date int și totodată să calculăm
factoriale imense.
Cu toate acestea, dacă vrem să aflăm cu exactitate numărul, putem să ne folosim de numere mari, prin care în loc să folosim un tip de date pentru a păstra un număr, vom folosi un vector, fiecare element al vectorului conținând câte o cifră.
Soluția cu numere mari este brutală — operațiile sunt extrem de dificil de implementat. Însă, din fericire, acest articol despre Numere Mari explică și exemplifică foarte ușor operațiile cu aceste numere mari.
Bibliografie sau alte resurse
Exerciții propuse
Se încarcă…
Avem pregătite 5 exerciții pentru tine, pentru a-ți testa cunoștințele și a-ți îmbunătăți abilitățile.
Exercițiul 1
Răspuns corect!
Ce greșeală există în ciclul de mai jos, care ar trebui să calculeze n!?
int factn = 1;
for(int i = 1; i <= factn; i++)
factn = factn * i;
Exercițiul 2
Răspuns corect!
De ce metoda cu trei factoriale nu este potrivită pentru valori mari ale lui n, chiar dacă C(n, k) este mic?
Exercițiul 3
Răspuns corect!
De ce în nCk = nCk * (n - k + i) / i; împărțirea la i este întotdeauna exactă?
Exercițiul 4
Răspuns corect!
Care este rolul calculării răspunsului modulo un număr prim, atunci când se cer combinări foarte mari?
Exercițiul 5
Răspuns corect!
Care este valoarea lui C(n, k) pentru k > n, conform convenției din lecție?
DS
Autorul acestei lecții
Dominic Satnoianu
Această lecție a fost redactată de către Dominic Satnoianu.
© 2021 – 2026 Aspire Education Labs SRL. Toate drepturile rezervate.
Așa cum este specificat și în termeni și condiții, conținutul acestei pagini este protejat de legea drepturilor de autor și este interzisă copierea sau modificarea acestuia fără acordul scris al autorilor.
Încălcarea drepturilor de autor este o infracțiune și se pedepsește conform legii.
Comentarii 0