Clasa X - Ora 12: Șiruri și dicționare - probleme combinate

SINTEZĂ TEORETICĂ ȘI EXEMPLE GHIDATE

Ce vei învăța astăzi?

După această lecție vei combina șirurile cu dicționarul: vei număra frecvența cuvintelor cu tablouri paralele, vei determina cuvântul cel mai frecvent și vei calcula rapoarte și procente de apariție.

Dicționarul ca model cheie-valoare

Frecvența cuvintelor cu tablouri paralele

Cuvântul și litera cele mai frecvente

Rapoarte și procente de apariție

Dicționarul în acțiune: frecvența cuvintelor

Definiție: Un dicționar este o colecție de perechi cheie-valoare. La frecvența cuvintelor, cheia este cuvântul, iar valoarea este numărul de apariții. În C++ modelăm dicționarul cu tablouri paralele: cuvinte[i] reține cheia, frecventa[i] reține valoarea, iar n spune câte perechi există. Cheile sunt unice: un cuvânt apare o singură dată în tabloul de chei.

Modelul funcționează identic pentru litere: cheia este litera, iar valoarea este frecvența ei. Cum alfabetul are 26 de litere, frecvența literelor se reține simplu într-un tablou cu 26 de poziții.

Analogia: tabelul de scor al campionatului

Un dicționar de frecvențe seamănă cu tabelul de scor al unui campionat: fiecare echipă (cheia) apare o singură dată în tabel, iar lângă ea stă numărul ei de puncte (valoarea). Când o echipă marchează, nu adăugăm un rând nou, ci creștem valoarea de pe rândul ei existent. Doar echipele noi primesc un rând nou, cu punctajul de plecare.

Cheia

Cuvântul (unic în dicționar)

Valoarea

Numărul de apariții

Paralele

Cheie și valoare pe aceeași poziție i

Numărarea frecvenței cuvintelor

Pentru fiecare cuvânt al textului: căutăm cheia printre cuvintele deja introduse (căutare liniară cu strcmp); dacă o găsim, incrementăm valoarea; dacă nu, adăugăm o pereche nouă cu frecvența 1. După parcurgerea textului, dicționarul conține toate cuvintele distincte și frecvențele lor.

Algoritm frecvențăCuvinte citește text n = 0 (numărul de cuvinte distincte) pentru fiecare cuvânt din text execută găsit = fals pentru i = 0, n - 1 execută dacă cuvinte[i] = cuvânt atunci frecventa[i] = frecventa[i] + 1 găsit = adevărat sfârșit dacă sfârșit pentru dacă găsit = fals atunci cuvinte[n] = cuvânt frecventa[n] = 1 n = n + 1 sfârșit dacă sfârșit pentru scrie toate perechile (cuvânt, frecvență) Sfârșit algoritm

C++ - frecvența cuvintelor dintr-un text

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

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

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

    char *p = strtok(text, " ");

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

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

    return 0;
}

Ce învățăm: trucul if (i == n) verifică dacă bucla de căutare a ajuns la capăt fără să găsească cheia; atunci cuvântul este nou și primește un rând nou în dicționar.

Cuvântul cel mai frecvent

După construirea dicționarului, parcurgem valorile și reținem maximul: frecventa[i] comparat cu maximul curent. Reținem și poziția i a maximului, ca să putem afișa cheia corespunzătoare, cuvinte[i]. La egalitate, convenția uzuală este să rămână primul cuvânt găsit.

Algoritm cuvântCelMaiFrecvent (după construirea dicționarului cu n perechi) pozMax = 0 pentru i = 1, n - 1 execută dacă frecventa[i] > frecventa[pozMax] atunci pozMax = i sfârșit dacă sfârșit pentru scrie cuvinte[pozMax], "cu", frecventa[pozMax], "apariții" Sfârșit algoritm

C++ - cuvântul cu cele mai multe apariții

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

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

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

    char *p = strtok(text, " ");

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

    int pozMax = 0;

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

    cout << cuvinte[pozMax] << " apare de "
         << frecventa[pozMax] << " ori" << endl;

    return 0;
}

Ce învățăm: căutarea maximului în dicționar este identică cu cea dintr-un tablou obișnuit, doar că reținem poziția pentru a accesa și cheia de pe aceeași poziție (tablouri paralele).

Rapoarte și procente de apariție

Definiție: Raportul de apariție al unui element este frecvența lui împărțită la numărul total de elemente. Procentul este raportul înmulțit cu 100. De exemplu, dacă litera a apare de 3 ori într-un text cu 10 litere, raportul ei este 0,3, iar procentul este 30%. Pentru litere, totalul este lungimea textului, iar frecvențele se rețin pe pozițiile litera - 'a'.

Algoritm rapoarteLitere citește text frec[26] = 0 (un tablou pentru fiecare literă mică) pentru i = 0, strlen(text) - 1 execută dacă text[i] este literă mică atunci frec[text[i] - 'a'] = frec[text[i] - 'a'] + 1 sfârșit dacă sfârșit pentru pentru fiecare literă cu frecvență nenulă execută procent = (frec[litera] * 100) / numărul total de litere scrie litera, procent, "%" sfârșit pentru Sfârșit algoritm

C++ - procentul de apariție al fiecărei litere

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

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

    int frec[26] = {0};
    int n = strlen(s);
    int totalLitere = 0;

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

    for (int i = 0; i < 26; i++)
    {
        if (frec[i] > 0)
        {
            char litera = 'a' + i;
            int procent = (frec[i] * 100) / totalLitere;
            cout << litera << ": " << procent
                 << "%" << endl;
        }
    }

    return 0;
}

Ce învățăm: împărțirea întreagă a două int-uri dă câtul; înmulțirea cu 100 înainte de împărțire evită pierderea zecimalelor. Pentru un procent exact, se lucrează cu double.

Exercițiu de completare

Completează enunțul despre dicționare:

Un dicționar este o colecție de perechi ______. În C++ îl modelăm cu ______: cheia într-un tablou de cuvinte, valoarea într-un tablou de numere. Dacă un cuvânt există deja, ______ frecvența; dacă este nou, îl adăugăm cu frecvența ______.

Bancă de cuvinte:

cheie-valoare tablouri paralele incrementăm 1

Exercițiu de completare a codului

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

#include <iostream>

#include <cstring>

using namespace std;

int main()

{

char s[1001];

cin.getline(s, 1001);

int frec[______] = {0};

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

{

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

{

frec[______]++;

}

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

{

if (frec[i] > ______)

{

cout << (char)('a' + i) << " " << frec[i] << endl;

}

return 0;

}

Bancă de cuvinte:

26 s[i] - 'a' 0

Test de înțelegere

Test rapid - dicționare și frecvențe:

1. Ce verificăm când un cuvânt apare deja în dicționar?

strcmp(cuvinte[i], cuvant) == 0 cuvinte[i] == cuvant strlen(cuvinte[i]) == strlen(cuvant)

2. Ce facem când un cuvânt este nou în dicționar?

nu facem nimic îl adăugăm la final cu frecvența 1 și creștem n îl adăugăm la final cu frecvența 0

3. Pe ce poziție se numără litera 'b'?

frec[2] frec['b' - 'a'] adică frec[1] frec['b' - 'a']

Ai grijă la: la procente, împărțirea a două valori int dă rezultat întreg: 2 / 7 este 0, nu 0,28. Folosește double și înmulțirea cu 100.0, altfel toate procentele devin 0 sau 100.

Aprofundare

Cazuri particulare și detalii avansate:

Text cu spații multiple: strtok le tratează automat; dacă separi manual, verifică ca lungimea cuvântului să fie mai mare decât 0 înainte de căutarea în dicționar.
Egalități la maxim: folosind frecventa[i] > frecventa[pozMax] (nu >=), la egalitate rămâne primul cuvânt întâlnit; cu >= rămâne ultimul.
Majuscule: 'A' și 'a' sunt caractere diferite; pentru un dicționar uniform, transformăm tot textul în litere mici înainte de numărare.
Procente exacte: pentru valori cu zecimale folosim double procent = (frec[i] * 100.0) / total;, iar afișarea se face cu fixed și setprecision.
Sortarea după frecvență: dicționarul poate fi sortat descrescător după valoare, interschimbând perechi întregi (cu strcpy pentru chei), pentru a afișa un top al cuvintelor.

Dicționarul transformă un text într-o statistică: numărul de cuvinte distincte, cuvântul dominant, frecvența literelor și procentele sunt exact informațiile din analizele lingvistice, sondaje și rapoarte de utilizare.

APLICARE ȘI REZOLVARE DE PROBLEME

PbInfo - Cuvântul cel mai 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, împreună cu numărul de apariții.

Date de intrare:

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

Date de ieșire:

Programul va afișa cuvântul cel mai frecvent și numărul de apariții, separate printr-un spațiu.

Restricții și precizări:

Textul are cel mult 1000 de caractere; cuvintele au cel mult 100 de litere; dacă mai multe cuvinte au același număr maxim de apariții, se afișează primul dintre ele în ordinea apariției.

Exemplu:

Intrare:

ana are ana si ana are mere

Ieșire:

ana 3

Cum gândim soluția:

Separăm cuvintele cu strtok
Construim dicționarul cu tablouri paralele (cuvinte + frecvențe)
Căutăm poziția cu frecvența maximă
Afișăm cheia și valoarea de pe poziția respectivă

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[501][101];
    int frecventa[501] = {0};
    int n = 0;

    char *p = strtok(text, " ");

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

    int pozMax = 0;

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

    cout << cuvinte[pozMax] << " " << frecventa[pozMax] << endl;

    return 0;
}

Ce învățăm: pentru textul dat, ana apare de 3 ori, are de 2 ori, iar si și mere o dată; maximul este 3, pe cheia ana.

PbInfo - Litera cea mai frecventă

Enunț:

Cerință: Se citește un cuvânt format din litere mici. Să se afișeze litera care apare de cele mai multe ori; dacă sunt mai multe litere cu același număr maxim de apariții, se afișează litera alfabetic cea mai mică.

Date de intrare:

Programul citește de la tastatură cuvântul s.

Date de ieșire:

Programul va afișa litera cerută.

Restricții și precizări:

Cuvântul are cel mult 100 de caractere și conține doar litere mici ale alfabetului englez.

Exemplu:

Intrare:

bacalaureat

Ieșire:

Cum gândim soluția:

Construim tabloul de frecvențe cu 26 de poziții, folosind s[i] - 'a'
Parcurgem pozițiile în ordine crescătoare (alfabetică) și reținem prima cu frecvența maximă
Afișăm litera cu (char)('a' + pozitie)

Scrie soluția în C++:

Soluție corectă:

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

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

    int frec[26] = {0};

    for (int i = 0; i < strlen(s); i++)
    {
        frec[s[i] - 'a']++;
    }

    int pozMax = 0;

    for (int i = 1; i < 26; i++)
    {
        if (frec[i] > frec[pozMax])
        {
            pozMax = i;
        }
    }

    cout << (char)('a' + pozMax) << endl;

    return 0;
}

Ce învățăm: pentru bacalaureat, litera a apare de 4 ori și este și cea mai mică alfabetic dintre cele cu frecvență maximă; parcurgerea crescătoare a pozițiilor rezolvă automat egalitatea.

EXERCIȚII PRACTICE

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

Sarcini de lucru

Completează următoarele sarcini pentru a consolida prelucrarea cu dicționare

Sarcina 1: Cuvinte distincte

Cerință: Scrie un program C++ complet care citește un text de cuvinte și afișează numărul de cuvinte distincte (fiecare cuvânt numărat o singură dată). Pentru intrarea ana are ana si are mere se afișează 4.

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[501][101];
    int n = 0;

    char *p = strtok(text, " ");

    while (p != NULL)
    {
        int i;
        for (i = 0; i < n; i++)
        {
            if (strcmp(cuvinte[i], p) == 0)
            {
                break;
            }
        }
        if (i == n)
        {
            strcpy(cuvinte[n], p);
            n++;
        }
        p = strtok(NULL, " ");
    }

    cout << n << endl;

    return 0;
}

Verifică: cuvintele distincte sunt ana, are, si, mere, deci răspunsul este 4.

Sarcina 2: Procentul vocalei

Cerință: Scrie un program C++ complet care citește un cuvânt și afișează procentul (număr întreg) reprezentat de litera a în cuvânt. Pentru intrarea ana se afișează 66 (2 litere a din 3 litere).

Scrie programul aici:

Soluție pentru Sarcina 2:

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

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

    int n = strlen(s);
    int aparitii = 0;

    for (int i = 0; i < n; i++)
    {
        if (s[i] == 'a')
        {
            aparitii++;
        }
    }

    int procent = (aparitii * 100) / n;

    cout << procent << endl;

    return 0;
}

Verifică: pentru ana, aparitii = 2, iar (2 * 100) / 3 = 66.

Ora 12: Șiruri și dicționare - probleme combinate

Înainte de a începe

Ce știi deja?

Ce vei învăța astăzi?

Dicționarul în acțiune: frecvența cuvintelor

Analogia: tabelul de scor al campionatului

Numărarea frecvenței cuvintelor

Cuvântul cel mai frecvent

Rapoarte și procente de apariție

Exercițiu de completare

Completează enunțul despre dicționare:

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ționare și frecvențe:

Aprofundare

PbInfo - Cuvântul cel mai 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ă:

PbInfo - Litera cea mai 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ționare în acțiune

Sarcini de lucru

Sarcina 1: Cuvinte distincte

Soluție pentru Sarcina 1:

Sarcina 2: Procentul vocalei

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