Nu obții 100 de puncte sau ai nelămuriri în privința problemelor? Scrie-mi pe Instagram.
Ai găsit o greșeală, vrei să raportezi un utilizator sau vrei să comunici altceva? Folosește formularul de contact.
Vrei să ne transmiți o părere despre platformă? Folosește formularul de feedback.
Folosește următoarele shortcuturi pentru a naviga mai ușor pe platformă.
Meniu shortcuturi | ? |
Căutare probleme sau utilizatori | / |
Navigare printre rezultatele căutării | ↑, ↓ |
Meniu de contact și feedback | CTRL + Shift + F |
Ieșire din meniuri | Esc |
Setări editor | CTRL + Shift + S |
Schimbare stil editor | CTRL + Shift + E |
Șabloane de cod | CTRL + Shift + 1/2/3 |
Golire editor | CTRL + Shift + 4 |
Această problemă poate apărea sub mai multor forme:
n
și k
, să se afle numărul combinărilor de n
luate câte k
: Cnk
.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ă?k
-lea termen din binomul (1 + x)n
.Numărul de combinări este egal cu Cnk =
.
Pentru n = 5
și k = 3
, avem C53 =
.
Se consideră că pentru k > n
, Cnk = 0
.
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.
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 <= factn; i++)
factn = factn * i;
for(int i = 1; i <= factk; i++)
factk = factk * i;
for(int i = 1; i <= factnk; i++)
factnk = factnk * i;
//Calculăm și afișăm numărul de combinări
int nCk = factn / (factk * factnk);
cout << nCk;
return 0;
}
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 de pe InfoArena explică și exemplifică foarte ușor operațiile cu numere mari.