Clasa X - Ora 9: Dicționarul - model conceptual asociativ

SINTEZĂ TEORETICĂ ȘI EXEMPLE GHIDATE

Ce vei învăța astăzi?

După această lecție vei înțelege modelul asociativ cheie-valoare al dicționarului, vei ști să-l implementezi în C++ cu tablouri paralele și vei număra aparițiile cuvintelor și literelor unui text.

Modelul cheie-valoare

Tablouri paralele

Numărarea aparițiilor cuvintelor

Frecvența literelor

Modelul cheie-valoare

Definiție: Un dicționar este un model asociativ în care fiecare cheie este legată de o valoare. După cheie găsim direct valoarea asociată. Este modelul din spatele agendelor telefonice, cataloagelor școlare sau dicționarelor de cuvinte.

Analogia: catalogul școlar

În catalog, cheia este numele elevului, iar valoarea este nota. Căutăm după nume și obținem nota. Într-un dicționar de frecvențe, cheia este cuvântul, iar valoarea este de câte ori apare.

Cheia

Elementul după care căutăm: un cuvânt, o literă

Valoarea

Informația asociată cheii: o frecvență, un număr

Asociere

Legătura dintre cheie și valoare este unică

Dicționarul de frecvențe al cuvintelor

Cheie (cuvânt)	Valoare (frecvență)
ana	3
are	2
mere	1

Implementarea cu tablouri paralele

În C++ modelăm dicționarul cu două tablouri paralele: cuvinte[i] reține cheia, iar frecventa[i] reține valoarea, pe aceeași poziție i. Numărul n spune câte perechi cheie-valoare există.

Algoritm frecvențăCuvinte declară cuvinte[], frecventa[], n = 0 cât timp mai există un cuvânt din text execută cuvant = următorul cuvânt găsit = fals pentru i = 0, n - 1 execută dacă cuvinte[i] = cuvant atunci frecventa[i] = frecventa[i] + 1 găsit = adevărat sfârșit dacă sfârșit pentru dacă găsit = fals atunci n = n + 1 cuvinte[n] = cuvant frecventa[n] = 1 sfârșit dacă sfârșit cât timp pentru i = 0, n - 1 execută scrie cuvinte[i], frecventa[i] sfârșit pentru Sfârșit algoritm

C++ - numărarea aparițiilor cuvintelor

#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    char text[1001];
    cin.getline(text, 1001);

    char cuvinte[101][101];
    int frecventa[101] = {0};
    int n = 0;

    char *p = strtok(text, " ");
    while (p != NULL)
    {
        int gasit = -1;
        for (int i = 0; i < n; i++)
        {
            if (strcmp(cuvinte[i], p) == 0)
            {
                gasit = i;
            }
        }
        if (gasit == -1)
        {
            strcpy(cuvinte[n], p);
            frecventa[n] = 1;
            n++;
        }
        else
        {
            frecventa[gasit]++;
        }
        p = strtok(NULL, " ");
    }

    for (int i = 0; i < n; i++)
    {
        cout << cuvinte[i] << " apare de " << frecventa[i] << " ori"
             << endl;
    }

    return 0;
}

Ce învățăm: strtok desparte textul în cuvinte; dacă un cuvânt există deja în dicționar, creștem frecvența, altfel îl adăugăm la final.

Frecvența literelor

Pentru litere, cheia este chiar litera: folosim indicele literei, s[i] - 'a', într-un singur tablou frecventa[26]. Aceasta este o formă specială de dicționar: cheia devine indice.

C++ - frecvența literelor unui text

#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    char s[1001];
    cin.getline(s, 1001);

    int frecventa[26] = {0};

    for (int i = 0; i < strlen(s); i++)
    {
        if (s[i] >= 'a' && s[i] <= 'z')
        {
            frecventa[s[i] - 'a']++;
        }
    }

    for (int i = 0; i < 26; i++)
    {
        if (frecventa[i] > 0)
        {
            cout << char('a' + i) << ": " << frecventa[i] << endl;
        }
    }

    return 0;
}

Ce învățăm: litera 'a' are indicele 0, 'b' indicele 1, ..., 'z' indicele 25. Astfel un singur tablou reține frecvențele tuturor literelor.

Exercițiu de completare

Completează enunțul despre dicționar:

Un dicționar asociază unei ______ o ______. În C++ modelăm dicționarul cu ______: pe aceeași poziție păstrăm cheia și valoarea. Frecvența unei litere se reține folosind ca indice expresia ______.

Bancă de cuvinte:

chei valoare tablouri paralele s[i] - 'a'

Exercițiu de completare a codului

Completează programul care numără frecvența literelor:

int frecventa[26] = {0};

for (int i = 0; i < strlen(s); i++)

{

if (s[i] >= 'a' && s[i] <= '______')

{

______[s[i] - 'a']++;

}

for (int i = 0; i < 26; i++)

{

if (frecventa[i] > 0)

{

cout << char('a' + ______) << ": "

<< frecventa[i] << endl;

}

Bancă de cuvinte:

z frecventa i

Test de înțelegere

Test rapid - dicționarul:

1. Într-un dicționar, cuvântul căutat este:

cheia valoarea indicele tabloului

2. Două tablouri se numesc paralele când:

au doar aceeași dimensiune elementele de pe același indice descriu aceeași entitate sunt sortate alfabetic

3. În frecventa[s[i] - 'a'], litera 'b' are indicele:

1 2 0

Ai grijă la: cheile (cuvintele) se compară cu strcmp, niciodată cu ==, care ar compara doar adresele; iar când adaugi o cheie nouă trebuie incrementat și numărul de perechi n, altfel dicționarul „pierde" ultimele cuvinte.

Aprofundare

Cazuri particulare și detalii avansate:

Dicționarul este un model asociativ cheie-valoare: pentru fiecare cheie (ex. cuvântul ana) păstrăm o valoare (ex. numărul de apariții). Aceeași idee stă la baza agendelor de telefon, a indexurilor de carte și a contoarelor de voturi.
Inserarea unei chei noi: dacă parcurgem toate cheile existente și nu găsim potrivirea, adăugăm o pereche nouă la sfârșitul tablourilor paralele: cuvinte[n] = cuvant; frecventa[n] = 1; n++;.
Căutarea liniară a cheii se face cu strcmp(cuvinte[i], cuvant) == 0; atenție, compararea cu == pe șiruri este greșită.
Frecvența literelor folosește poziția din alfabet ca „cheie": poz = s[i] - 'a' pentru litere mici, deci un singur tablou frec[26] este suficient.
Rapoarte și procente: după numărare, împărțim frecvența la numărul total de elemente pentru a obține proporții (ex. procentul de apariție al unei litere într-un text).

Dicționarul cu tablouri paralele este instrumentul cu care rezolvăm „câte de fiecare?" — de la frecvența cuvintelor dintr-un eseu până la statistica voturilor dintr-un scrutin.

APLICARE ȘI REZOLVARE DE PROBLEME

PbInfo - Frecvența literelor

Enunț:

Cerință: Se citește un șir format doar din litere mici. Să se afișeze, în ordine alfabetică, fiecare literă care apare, împreună cu numărul de apariții.

Date de intrare:

Programul citește de la tastatură șirul de litere.

Date de ieșire:

Programul va afișa, pe linii separate, perechile litera: frecventa.

Restricții și precizări:

Șirul are cel mult 1000 de caractere și conține doar litere mici, fără spații.

Exemplu:

Intrare:

anagrama

Ieșire:

a: 4
g: 1
m: 1
n: 1
r: 1

Cum gândim soluția:

Folosim un dicționar de 26 de poziții: frecventa[26]
Pentru fiecare literă incrementăm frecventa[s[i] - 'a']
Afișăm doar literele cu frecvența mai mare decât 0

Scrie soluția în C++:

Soluție corectă:

#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    char s[1001];
    cin.getline(s, 1001);

    int frecventa[26] = {0};

    for (int i = 0; i < strlen(s); i++)
    {
        if (s[i] >= 'a' && s[i] <= 'z')
        {
            frecventa[s[i] - 'a']++;
        }
    }

    for (int i = 0; i < 26; i++)
    {
        if (frecventa[i] > 0)
        {
            cout << char('a' + i) << ": " << frecventa[i] << endl;
        }
    }

    return 0;
}

Ce învățăm: parcurgerea indicilor 0..25 afișează literele automat în ordine alfabetică, pentru că indicele crește împreună cu litera.

PbInfo - Cuvântul frecvent

Enunț:

Cerință: Se citește un text format din cuvinte despărțite prin câte un spațiu. Să se afișeze cuvântul care apare de cele mai multe ori.

Date de intrare:

Programul citește de la tastatură textul, pe o singură linie.

Date de ieșire:

Programul va afișa cuvântul cu frecvența maximă.

Restricții și precizări:

Textul are cel mult 1000 de caractere; cuvintele sunt formate din litere mici.

Exemplu:

Intrare:

ana are ana si ion are ana

Ieșire:

ana

Cum gândim soluția:

Construim dicționarul cu tablouri paralele cuvinte și frecventa
Despărțim textul cu strtok
Căutăm poziția cu frecvența maximă și afișăm cuvântul de acolo

Scrie soluția în C++:

Soluție corectă:

#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    char text[1001];
    cin.getline(text, 1001);

    char cuvinte[101][101];
    int frecventa[101] = {0};
    int n = 0;

    char *p = strtok(text, " ");
    while (p != NULL)
    {
        int gasit = -1;
        for (int i = 0; i < n; i++)
        {
            if (strcmp(cuvinte[i], p) == 0)
            {
                gasit = i;
            }
        }
        if (gasit == -1)
        {
            strcpy(cuvinte[n], p);
            frecventa[n] = 1;
            n++;
        }
        else
        {
            frecventa[gasit]++;
        }
        p = strtok(NULL, " ");
    }

    int maxim = 0;
    for (int i = 1; i < n; i++)
    {
        if (frecventa[i] > frecventa[maxim])
        {
            maxim = i;
        }
    }

    cout << cuvinte[maxim];

    return 0;
}

Ce învățăm: după construirea dicționarului, găsim cuvântul frecvent căutând maximul din tabloul de frecvențe.

EXERCIȚII PRACTICE

Exercițiul Practic: dicționarul în acțiune

Sarcini de lucru

Completează următoarele sarcini pentru a consolida modelul asociativ

Sarcina 1: Dicționarul meu de cuvinte

Cerință: Scrie un program C++ complet care citește un text de cuvinte și afișează câte cuvinte distincte are (adică numărul de chei din dicționarul de frecvențe). Pentru textul ana are ana se afișează 2.

Scrie programul aici:

Soluție pentru Sarcina 1:

#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    char text[1001];
    cin.getline(text, 1001);

    char cuvinte[101][101];
    int n = 0;

    char *p = strtok(text, " ");
    while (p != NULL)
    {
        int gasit = -1;
        for (int i = 0; i < n; i++)
        {
            if (strcmp(cuvinte[i], p) == 0)
            {
                gasit = i;
            }
        }
        if (gasit == -1)
        {
            strcpy(cuvinte[n], p);
            n++;
        }
        p = strtok(NULL, " ");
    }

    cout << n;

    return 0;
}

Verifică: numărul de chei distincte este tocmai n, câte cuvinte am adăugat în dicționar.

Sarcina 2: Litera cea mai frecventă

Cerință: Scrie un program C++ complet care citește un șir de litere mici și afișează litera care apare de cele mai multe ori. Pentru intrarea anagrama se afișează a.

Scrie programul aici:

Soluție pentru Sarcina 2:

#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    char s[1001];
    cin.getline(s, 1001);

    int frecventa[26] = {0};

    for (int i = 0; i < strlen(s); i++)
    {
        if (s[i] >= 'a' && s[i] <= 'z')
        {
            frecventa[s[i] - 'a']++;
        }
    }

    int pozitieMax = 0;
    for (int i = 1; i < 26; i++)
    {
        if (frecventa[i] > frecventa[pozitieMax])
        {
            pozitieMax = i;
        }
    }

    cout << char('a' + pozitieMax);

    return 0;
}

Verifică: în anagrama, litera a apare de 4 ori, deci se afișează a.

Ora 9: Dicționarul - model conceptual asociativ

Înainte de a începe

Ce știi deja?

Ce vei învăța astăzi?

Modelul cheie-valoare

Analogia: catalogul școlar

Dicționarul de frecvențe al cuvintelor

Implementarea cu tablouri paralele

Frecvența literelor

Exercițiu de completare

Completează enunțul despre dicționar:

Bancă de cuvinte:

Exercițiu de completare a codului

Completează programul care numără frecvența literelor:

Bancă de cuvinte:

Test de înțelegere

Test rapid - dicționarul:

Aprofundare

PbInfo - Frecvența literelor

Enunț:

Date de intrare:

Date de ieșire:

Restricții și precizări:

Exemplu:

Cum gândim soluția:

Scrie soluția în C++:

Soluție corectă:

PbInfo - Cuvântul frecvent

Enunț:

Date de intrare:

Date de ieșire:

Restricții și precizări:

Exemplu:

Cum gândim soluția:

Scrie soluția în C++:

Soluție corectă:

Exercițiul Practic: dicționarul în acțiune

Sarcini de lucru

Sarcina 1: Dicționarul meu de cuvinte

Soluție pentru Sarcina 1:

Sarcina 2: Litera cea mai frecventă

Soluție pentru Sarcina 2:

Scrie pe caiet - De reținut

Titlul lecției

Definiția lecției

Definiții esențiale

Algoritmul cheie - pseudocod

Algoritmul cheie - cod C++

Greșeli comune de evitat

Sfaturi practice și trucuri

Exemplu practic