Contact și feedback

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.

Shortcuturi

Folosește următoarele shortcuturi pentru a naviga mai ușor pe platformă.

Generale

Meniu shortcuturi?
Căutare probleme sau utilizatori/
Navigare printre rezultatele căutării↑, ↓
Meniu de contact și feedbackCTRL + Shift + F
Ieșire din meniuriEsc

Editor probleme

Setări editorCTRL + Shift + S
Schimbare stil editorCTRL + Shift + E
Șabloane de codCTRL + Shift + 1/2/3
Golire editorCTRL + Shift + 4

Calculul combinărilor de n luate câte k (nCk) în C++

Această problemă poate apărea sub mai multor forme:

  • Dându-se două numere naturale n și k, să se afle numărul combinărilor de n luate câte k: Cnk.
  • Î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 celui de-al k-lea termen din binomul (1 + x)n.

Formula numărului de combinări

Numărul de combinări este egal cu Cnk = n factorial supra k factorial înmulțit cu n minus k factorial.

Exemplu

Pentru n = 5 și k = 3, avem C53 = 10.

Se consideră că pentru k > n, Cnk = 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 <= 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;
}

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 de pe InfoArena explică și exemplifică foarte ușor operațiile cu numere mari.

Bibliografie sau alte resurse

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

Cuprinsul lecției

Se încarcă…

Citește și

Combinatorică în C++: permutări, aranjamente, combinări și alteleOperații cu numere mari în C++ - Toate funcțiile explicateRădăcina cubică a unui număr în C++ (cube root)Numărul de apariții al unui număr într-un vector în C++Cum să citești și să afișezi în fișiere în C++Maximul și minimul unui vector în C++Aria unui triunghi folosind coordonatele acestora în C++Copiuțe: Cifrele unui numărInversarea unui șir de caractere în C++Calculul combinărilor de n luate câte k (nCk) în C++Radicalul unui număr în C++ (rădăcina pătrată)Ce înseamnă variabilă globală și locală în C++?Tipuri de date în C++: numere întregi, reale, caractere și alteleBordarea unei matrice în C++Citește un șir de caractere cu spații în C++Aria și circumferința unui cerc în C++Divide et Impera (metodă de programare C++)Numărul de divizori al unui număr în C++Afișarea divizorilor primi ai unui număr în C++Vectorii în C++: citire și afișareValoarea absolută (modulul) unui număr în C++Ridicarea la putere în timp logaritmic în C++. Exponențiere rapidăComentarii în C++Suma divizorilor unui număr în C++Cea mai lungă secvență de elemente crescătoare în C++Instrucțiunea break (structuri repetitive)Verifică dacă un caracter este literă în C++Cel mai mic/mare divizor prim al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Pointer în C++. Variabile de tipul char * (char steluță)Cel mai puțin semnificativ bit în C++Instrucțiunea de decizie în C++: if, else, switch, caseComplexitatea unui algoritm (timp și spațiu) în C++Al N-lea termen dintr-o progresie geometricăVerifică dacă trei puncte sunt coliniare C++Verifică dacă o literă este vocală în C++Verifică dacă un număr este par sau impar fără modulo în C++Instrucțiunea do while (structuri repetitive)Maximul și minimul a trei valori în C++Ciurul lui Eratostene în C++Matrice în C++. Declararea și parcurgerea tablourilor bidimensionaleVerifică dacă un număr dat este o putere de 2 în C++Interclasarea a doi vectori în C++Instrucțiunea while (structuri repetitive)Funcții predefinite în C++ (matematice, șiruri de caractere)Indicatorul lui Euler în C++Verificare număr prim în C++ (Clasa a IX-a)Cel mai frecvent element dintr-un șir în C++Citirea și afișarea matricelor în C++Numărul aranjamentelor în C++ (formula aranjamentelor)Cifra de control a unui numărDe ce cer unele probleme răspunsul modulo 666013 sau modulo 1.000.000.007?Ce înseamnă endl în C++?Cifra maximă a unui număr recursiv în C++CMMDC recursiv a două numere naturale în C++Instrucțiunea for (structuri repetitive)Transformarea unei litere mici în literă mare în C++Verificare dacă șir de caractere este palindrom în C++Cifra maximă și minimă a unui număr în C++Codul ASCII (tabel complet)Prima cifră a unui număr în C++Numărul de cifre ale factorialului unui numărAplicații cu ciurul lui Eratostene în C++: suma divizorilor, numărul divizorilorAflă secolul unui an citit de la tastatură în C++Structuri repetitive (while, do while, for, etc)Ce este o variabilă unsigned în C++?Verifică dacă un bit de pe o anumită poziție este 1 sau 0 în C++Suma numerelor naturale dintr-un interval dat în C++Ce este o funcție void în C++?Șiruri de caractere în C++. Tot ce trebuie să știiAflarea sumei primelor N sume GaussOglinditul recursiv al unui număr în C++Cum să calculezi instant 2 la puterea N în C++Oglinditul unui număr în C++Afișarea elementelor unui vector recursiv în C++Algoritm recursiv pentru căutare binară (clasa a X-a)Interschimbarea a două variabile în C++ (3 metode)Maximul și minimul a două valori în C++Numere triunghiulare. Verificarea unui număr triunghiularTipul struct în C++. Ce sunt structurile de date neomogeneVerificarea unui an bisect în C++Factorialul unui număr în C++Suma divizorilor numerelor de la 1 la N (Folosind ciurul lui Eratostene)Matrice pătratice în C++. Diagonala principală și secundarăCMMMC a două numere în C++ (cel mai mic multiplu comun)Materia pentru olimpiada de informatică - tot ce trebuie să știiDistanța dintre două puncte în C++Numărul de divizori primi ai unui număr în C++Numărul permutărilor în C++ (formula permutărilor)Vectorii în C++: declarare și parcurgereNumărul de divizori al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Sortare crescătoare recursivă în C++ - Merge sort și Bubble sortVectori de frecvență (de apariții) în C++Inversarea unui vector în C++Do while vs while în C++ - Care e diferența?Verifică dacă o literă este mică sau mare în C++Verifică dacă un caracter este cifră în C++Transformarea unui număr din baza 2 în baza 10 în C++Instrucțiunea continue (structuri repetitive)Recursivitate în C++Verifică dacă un număr aparține șirului Fibonacci în C++Numărul minim de peroane pentru o gară în C++Cel mai mic număr cu suma cifrelor N în C++Șirul lui Fibonacci în C++Indicatorul lui Euler al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Suma 1 + 2 + 3 + ... + N în C++Numărul combinărilor în C++ (formula combinărilor)Mediana unui șir de valori în C++Tutorial instalare CodeBlocks (ușor) - Introducere în informatică C++Cum să afișezi partea întreagă a unui număr real în C++Căutare binară în C++Cel mai mare divizor comun (CMMDC) a două numere în C++Generarea șirului Fibonacci generalizat în C++Maximul și minimul a n valori în C++Câte numere naturale sunt într-un interval dat? (C++)Cifrele unui număr. Prelucrarea cifrelor unui număr în C++Funcții în C++. Ce sunt subprogrameleVerificare dacă un număr este palindrom în C++Al N-lea termen Fibonacci în C++Matrice Fibonacci - al n-lea termen Fibonacci în timp logaritmicTransformarea unui număr din baza 10 în baza 2 în C++Cel mai semnificativ bit în C++Al N-lea termen dintr-o progresie aritmeticăSuma elementelor unui vector recursiv în C++Transformarea unei litere mari în literă mică în C++

© Drepturi de autor

Echipa InfoAs își rezervă drepturile de autor pentru conținutul acestei pagini. Copierea conținutului fără acordul scris expres al InfoAs reprezintă o încălcare a Legii 8/1996 și va fi tratată ca atare.

Trimite lecția

Toată lecția

Doar videoclipul pe YouTube

Informatica devine ușoară cu InfoAs

Intră în cont