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

Vectori de frecvență (de apariții) în C++

Ce este un vector de apariții (de frecvență)?

Vectorul de frecvență este un vector care reține numărul de apariții al fiecărei valori dintr-un șir. Mai exact, un astfel de vector de apariții ne ajută să determinăm pentru orice valoare, de câte ori apare în șirul nostru (chestie care ne poate ajuta în cazul unor probleme mai dificile).

Să luăm un exemplu — dacă avem vectorul (1, 4, 4, 5, 2, 4, 5, 7, 4, 1) cu valori între 0 și 9, atunci putem să aflăm de câte ori apare fiecare număr în parte.

Animație cu vectorii de frecvență

În exemplul de mai sus am implementat un vector de frecvențe pe care l-am numit intuitiv fr[]. Acest vector are lungimea 10 (cuprinde elemente de la 0 la 9), iar elementul fr[i] reține numărul de apariții al numărului i în șirul dat, unde 0 ≤ i ≤ 9.

Implementarea unui vector de frecvență în C++

Să zicem că avem un șir cu elemente mai mici decât 100. Atunci, vectorul nostru de frecvență (pe care noi îl vom numi fr) trebuie să aibă lungimea de cel puțin 100, astfel încât toate valorile posibile din șir să aibă o poziție în vectorul fr.

Cum se adaugă un element în vectorul de apariții

Să zicem că vrem să adăugăm un număr x în vectorul nostru de frecvență fr. Atunci, va trebui să marcăm faptul că numărul de apariții ale numărului x crește cu 1; așadar, fr[x]++.

Algoritm

Citim numerele pe rând și le adăugăm în vectorul de frecvență, urmând să afișăm pe ecran numărul de apariții al fiecărui număr în parte.

#include <iostream>

using namespace std;

int n, fr[101]; //Pentru ca vectorul să rețină numerele de la 1 la 100, trebuie să aibă lungimea minimă 101

int main()
{
    //Citim n și n numere naturale între 1 și 100
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int x;
        cin >> x;

        fr[x]++; //Îl adăugăm pe x, incrementând numărul său de apariții cu 1
    }

    //Afișăm numărul de apariții ale fiecărui element
    for(int i = 1; i <= 100; i++) {
        if(fr[i] > 0) { //Dacă numărul i apare în șir (de mai mult de 0 ori)
            cout << i << " apare de " << fr[i] << " ori in sir\n";
        }
    }
    return 0;
}

Ce este un vector caracteristic?

Similar cu vectorul de frecvență, vectorul caracteristic reține, pentru fiecare valoare în parte, doar dacă aceasta apare sau nu în șir. Mai precis, vectorul caracteristic reține:

  • 0, dacă elementul nu apare în șir;
  • 1, dacă elementul apare în șir.

Implementarea unui vector caracteristic în C++

Vom adapta codul de mai devreme. Adăugarea unui element în vectorul caracteristic constă în transformarea valorii sale în vector în 1, pentru a marca faptul că există. De asemenea, am numit vectorul carac pentru a avea un nume mai intuitiv.

#include <iostream>

using namespace std;

int n, carac[101]; //Pentru ca vectorul să rețină numerele de la 1 la 100, trebuie să aibă lungimea minimă 101

int main()
{
    //Citim n și n numere naturale între 1 și 100
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int x;
        cin >> x;

        carac[x] = 1; //Îl adăugăm pe x, marcând în vector cu 1 faptul că există
    }

    //Afișăm elementele care apar în șir
    for(int i = 1; i <= 100; i++) {
        if(carac[i] > 0) { //Dacă numărul i apare în șir
            cout << i << " apare in sir\n";
        }
    }
    return 0;
}

Probleme rezolvate

#525 Numere1 (PbInfo)

Se dau n numere naturale. Determinați cele mai mari două numere cu trei cifre care nu apar printre numerele date. Puteți să vedeți enunțul complet și să vă testați soluția pe această pagină.

Exemplu: Pentru n = 10 numere: 10, 994, 1010, 999, 1010, 998, 1005, 994, 996, 995, cele mai mari două numere care nu apar printre numerele date sunt 993 și 997.

Rezolvare: Vom utiliza un vector caracteristic. Deoarece numerele date pot avea orice valoare, dar pe noi ne interesează doar numerele de trei cifre, vom lua în considerare, în citire, doar numerele cu exact trei cifre (între 100 și 999 inclusiv). La final, vom parcurge numerele de la 999 în jos, iar când întâlnim câte un număr care nu apare în vectorul caracteristic, îl luăm în considerare. Dacă am găsit ambele numere, atunci le afișăm, altfel, afișăm pe ecran mesajul NU EXISTA.

#include <iostream>

using namespace std;

int carac[1000]; //Elementele sunt între 100 și 999, așadar vectorul trebuie să fie de minimum 1000 de elemente pentru ca numerele să poată încăpea

int main()
{
    //Citim n și cele n numere naturale
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if(100 <= x && x <= 999) { //Ne interesează doar numerele cu exact trei cifre
            carac[x] = 1;
        }
    }
    int nr1 = -1, nr2 = -1; //Cele două numere căutate
    for(int i = 999; i >= 100; i--) {
        if(v[i] == 0) { //Am găsit un număr care nu apare în șir
            if(nr2 == -1) nr2 = i;
            else if(nr1 == -1) {
                nr1 = i;
                break; //Ne oprim după ce am găsit ambele numere
            }
        }
    }
    if(nr1 == -1) cout << "NU EXISTA";
    else cout << nr1 << " " << nr2;
    return 0;
}

#244 CifreOrd (PbInfo)

Se dau n cifre zecimale. Să se afișeze aceste cifre în ordine crescătoare. Puteți să vedeți enunțul complet și să vă testați soluția pe această pagină.

Exemplu: Pentru n = 25 și cifrele 1 1 2 7 3 5 1 5 3 6 7 8 0 1 0 5 6 3 8 2 9 7 9 5 7, cifrele în ordine crescătoare sunt 0 0 1 1 1 1 2 2 3 3 3 5 5 5 5 6 6 7 7 7 7 8 8 9 9.

Rezolvare: Deoarece vorbim de cifre, va trebui să formăm un vector de frecvență fr cu 10 poziții (de la 0 la 9). Citim cifrele și le adăugăm în vector, după care parcurgem cifrele de la 0 la 9. Pentru fiecare cifră i, știm că aceasta apare de fr[i] ori în șirul inițial, așadar va trebui să afișăm cifra i pe ecran de fr[i] de ori. Deoarece afișăm cifrele de la 0 la 9, se garantează faptul că le afișăm în ordine crescătoare. Nu în ultimul rând, deoarece așa specifică enunțul inițial al problemei, odată la 20 de numere afișate trebuie să trecem la un rând nou.

#include <fstream>

using namespace std;

ifstream fin("cifreord.in");
ofstream fout("cifreord.out");

int fr[10], nrafis; //nrafis reprezintă numărul de numere afișate

int main()
{
    //Citim n și cele n cifre
    int n;
    fin >> n;
    for(int i = 1; i <= n; i++) {
        int cif;
        fin >> cif;
        fr[cif]++;
    }
    for(int i = 0; i <= 9; i++) {
        for(int j = 1; j <= fr[i]; j++) { //Afișăm cifra i de fr[i] ori (de atâtea ori apare)
            fout << i << " ";
            nrafis++;
            if(nrafis % 20 == 0) fout << "\n";
        }
    }
    return 0;
}

Exerciții propuse

Completează următoarele secvențe de cod:

Vectorul carac reține dacă un număr apare sau nu într-un șir. Să se verifice dacă există cel puțin un element nul în șir:

if(carac[???] == 1)
    cout << "Da";
else
    cout << "Nu";

Vectorul ani reține numărul de evenimente înregistrate pentru fiecare an în parte. Care este cel mai mare an care poate fi reținut în vector?

int ani[10000];
cout << ani[???];

Probleme propuse

# Problemă Dificultate
749. Siruri prietene Grea (8 )
770. Castel Grea (8 )
750. Numere Grea (8 )
41. Cate cifre de fiecare tip Ușoară (2 )
717. Alinieri Grea (8 )
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

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