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

Combinatorică în C++: permutări, aranjamente, combinări și altele

Combinatorica este o arie din matematică care studiază modalitățile de numărare sau aranjare ale unor elemente.

Probleme de combinatorică apar deseori în concursuri sau olimpiade de informatică, însă chiar și dacă nu te pregătești la acel nivel, cunoașterea acestor noțiuni o să te ajute mult (plus, se studiază și la matematică!).

Mai jos am atașat câteva noțiuni importante, împreună cu o secvență de cod în C++.

Produs cartezian

Fie n mulțimi: A1, A2, A3, …, An. Produsul cartezian, A1 × A2 × A3 × … × An reprezintă numărul de moduri de alege câte un element din fiecare mulțime, formând un grup de n elemente.

Produsul cartezian este egal cu |A1| × |A2| × |A3| × … × |An|, unde |A| reprezintă numărul de elemente ale mulțimii A.

Exemplu

Numărul numerelor de două cifre cu prima cifră impară este |{1, 3, 5, 7, 9}| × |{0, 1, 2, 3, …, 9}| = 5 × 10 = 50.

Implementare C++

Vom citi de la tastatură lungimile șirurilor, nu și elementele acestora, deoarece nu afectează cu nimic produsul nostru final.

int n, lungMult[101], produsCartezian = 1; //lungMult[i] = lungimea mulțimii i
cin >> n;
for(int i = 1; i <= n; i++) {
    cin >> lungMult[i];
    produsCartezian *= lungMult[i];
}
cout << produsCartezian;

Submulțimile unei mulțimi

Fie o mulțime A, cu n elemente. Atunci putem afirma faptul că A are 2n submulțimi.

Demonstrație

Demonstrația 1 (produs cartezian). Pentru fiecare element al mulțimii A, pentru a forma o submulțime, putem să alegem să adăugăm sau nu elementul curent la submulțime. Astfel, există 2 variante pentru primul element, 2 variante pentru al doilea element, …, 2 variante pentru al n-lea element. În total, sunt 2 × 2 × … × 2 = 2n variante.

Demonstrația 2 (combinări). O submulțime reprezintă o modalitate de a alege k numere dintre cele n ale mulțimii A, unde 0 ≤ k ≤ n. Pentru k = 0, există Cn0 variante. Pentru k = 1, există Cn1 variante. Pentru k = 2, există Cn2 variante. Asemănător pentru restul k-urilor până la n. În total, sunt Cn0 + Cn1 + Cn2 + Cn3 + … + Cnn = 2n elemente.

Exemplu

Pentru mulțimea {1, 2, 3}, avem 8 submulțimi:

  1. {1, 2, 3}
  2. {1, 2}
  3. {1, 3}
  4. {2, 3}
  5. {1}
  6. {2}
  7. {3}
  8. {} (Mulțimea vidă)

Implementare C++

Vom folosi o structură repetitivă de tip for pentru a calcula 2n, însă se poate folosi ridicarea la putere în timp logaritmic sau chiar manipulare de biți.

int n, nrSubmultimi = 1;
cin >> n;
for(int i = 1; i <= n; i++) {
    nrSubmultimi *= 2;
}
cout << nrSubmultimi;

Permutări

O permutare a unei mulțimi este o aranjare a elementelor sale într-o anumită ordine. Mai tehnic spus, PbInfo vine cu următoarea definiție:

Se numește permutare o corespondență biunivocă (bijecție) între o mulțime finită și ea însăși.

Exemplu

Pentru mulțimea {1, 2, 3}, avem 6 permutări:

  1. (1, 2, 3)
  2. (1, 3, 2)
  3. (2, 1, 3)
  4. (2, 3, 1)
  5. (3, 1, 2)
  6. (3, 2, 1)

Numărul permutărilor

Pentru o mulțime de n elemente, avem numărul permutărilor Pn = n!.

Demonstrație. Să zicem că vrem să generăm o permutare. Primul element poate să fie oricare dintre cele n numere — așadar are n posibilități. Al doilea element poate să fie oricare număr, mai puțin primul număr (deoarece a fost ales deja) — așadar rămân n - 1 posibilități. Continuăm, până când ultimul element rămâne cu 1 singură posibilitate. Folosind regula produsului, avem în total Pn = n × (n - 1) × (n - 2) × … × 1 = n! permutări.

int n; //Numărul elementelor mulțimii
cin >> n;
int nrPermutari = 1;
for(int i = 1; i <= n; i++) {
    nrPermutari *= i;
}
cout << nrPermutari;

Permutări circulare

Să zicem că vrem să așezăm numerele pe un cerc și vrem să determinăm câte permutări diferite sunt în acest caz. Diferența dintre permutările normale sunt că la permutările circulare, o rotație circulară a elementelor spre oricare direcție nu se consideră ca fiind o permutare diferită (e.g. (1, 2, 3) = (2, 3, 1)), deoarece, dacă așezăm circular numerele, obținem același rezultat.

Numărul permutărilor circulare ale unei mulțimi cu n elemente este (n - 1)!.

Exemplu. Trei prieteni, 1, 2, 3, stau la o masă. În câte moduri se pot așeza? (Răspuns: 2! = 2). Putem observa cele două moduri în imaginea de mai jos (roșu și albastru) — pentru fiecare modalitate, există 3 permutări care defapt dau aceeași permutare circulară:

https://i.ibb.co/hFwsHxF/image.png

Implementarea permutărilor circulare este următoarea:

int n; //Numărul elementelor mulțimii
cin >> n;
int nrPermutariCirculare = 1;
for(int i = 1; i <= n - 1; i++) {
    nrPermutariCirculare *= i;
}
cout << nrPermutariCirculare;

Permutări cu repetiție

Avem n1 elemente de un tip, n2 elemente de alt tip, …, nk elemente de alt tip. În total, sunt n = n1 + n2 + … + nk elemente. Numărul permutărilor distincte este: n factorial supra n1 factorial ori n2 factorial ori ... ori nk factorial.

Exemplu. Numărul de anagrame ale cuvântului tata este 6: aatt, atat, atta, taat, tata, ttaa.

Implementarea în C++ calculează factorialul lui n, precum și factorialul celor k numere și calculează răspunsul astfel.

Aranjamente

Să zicem că n persoane sunt într-o competiție, iar primii k vor obține un premiu (ordinea acestora contează). Câte moduri distincte de alegere a celor k persoane există?

Exemplu

Candidează n = 3 persoane pe k = 2 locuri. Astfel, rezultatele posibile sunt:

  1. 1 ocupă primul loc, 2 ocupă al doilea loc;
  2. 1 ocupă primul loc, 3 ocupă al doilea loc;
  3. 2 ocupă primul loc, 1 ocupă al doilea loc;
  4. 2 ocupă primul loc, 3 ocupă al doilea loc;
  5. 3 ocupă primul loc, 1 ocupă al doilea loc;
  6. 3 ocupă primul loc, 2 ocupă al doilea loc.

Numărul aranjamentelor de n luate câte k este Ank = n factorial supra n minus k factorial.

Implementare C++

int n, k, aranjamente = 1;
cin >> n >> k;
for(int i = n - k + 1; i <= n; i++) { //1 * 2 * 3 * … * n / (1 * 2 * 3 * … * (n - k))
    aranjamente *= i;
}
cout << aranjamente;

Combinări

Să zicem că avem n persoane care candidează pe k locuri (unde toate locurile sunt la fel, așadar ordinea alegerii nu contează). În câte moduri putem alege cele k persoane?

Exemplu

Pentru n = 4, k = 2, putem alege:

  • Persoanele 1, 2 (2, 1 este aceeași alegere);
  • Persoanele 1, 3
  • Persoanele 1, 4
  • Persoanele 2, 3
  • Persoanele 2, 4
  • Persoanele 3, 4

Numărul combinărilor de n luate câte k este Cnk = n factorial supra k factorial înmulțit cu n minus k factorial.

Această formulă mai poate fi rescrisă astfel: Cnk = aranjamente de n luate câte k supra permutări de k; n * (n - 1) * ... * (n - k + 1) / 1 * 2 * 3 * ... * k

Implementare

int n, k, factn = 1, factk = 1, factnk = 1; //n, k, n!, k!, (n - k)!
cin >> n >> k;
for(int i = 1; i <= n; i++) {
    factn *= i;
}
for(int i = 1; i <= k; i++) {
    factk *= i;
}
for(int i = 1; i <= n - k; i++) {
    factnk *= i;
}
int combinari = factn / (factk * factnk);
cout << combinari;

Probleme propuse

Probleme cu permutări

# Problemă Dificultate
653. Numere prin rearanjare Medie (4 )
654. Aranjare numere Ușoară (2 )
187. Permutari Ușoară (2 )
651. Numarul de anagrame Medie (4 )
649. Permutari cu repetitie Ușoară (2 )
Vrei mai multe probleme? Pe această pagină găsești întreaga listă de probleme propuse.

Probleme cu aranjamente

# Problemă Dificultate
663. Numarare cuvinte 5 Ușoară (2 )
306. Triplu stecher Ușoară (2 )
661. Anagrame 2 Medie (4 )
659. Steag Medie (4 )
658. Loterie Ușoară (2 )
Vrei mai multe probleme? Pe această pagină găsești întreaga listă de probleme propuse.

Probleme cu combinări

# Problemă Dificultate
671. Transformare sir Medie (4 )
672. Echipa de volei Ușoară (2 )
296. Reclama Ușoară (2 )
669. Curier Medie (4 )
667. Stars and bars 2 Ușoară (2 )
Vrei mai multe probleme? Pe această pagină găsești întreaga listă de probleme propuse.

Probleme diverse de combinatorică

# Problemă Dificultate
723. Arhitect Grea (8 )
754. Aeres Grea (8 )
189. Numar submultimi Ușoară (2 )
681. Drepte paralele 2 Ușoară (2 )
679. Baza de numeratie extraterestra Ușoară (2 )
Vrei mai multe probleme? Pe această pagină găsești întreaga listă de probleme propuse.

Alte resurse sau bibliografie

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

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