Ce vei învăța astăzi?
După această lecție vei identifica toate capitolele clasei a X-a, vei folosi tabelul rezumativ mare al materiei și vei rezolva probleme integrate de recapitulare în C++.
Harta materiei clasei a X-a
Definiție: Programele de informatică din clasa a X-a sunt organizate în cinci module, construite progresiv: de la algoritmi simpli pe numere, la structuri de date complexe și subprograme recursive. Fiecare modul folosește cunoștințele modulelor anterioare.
Analogia: construcția unei clădiri
Materia clasei a X-a se construiește ca o clădire: fundația (algoritmii de bază pe numere), apoi etajele (structuri de date), apoi sistemul de comunicare (subprogramele) și, la final, automatizarea (recursivitatea). Fără fundație, etajele superioare nu pot sta în picioare.
Modulul 1-2: algoritmi pe numere, vectori
Modulul 3-4: șiruri, subprograme
Modulul 5: subprograme recursive
| Modul | Temă principală | Conținuturi esențiale |
|---|---|---|
| Modulul 1 | Algoritmi de bază | Divizori, numere prime, cifrele unui număr, divizibilitate |
| Modulul 2 | Structuri de date liniare | Vectori: parcurgere, căutare, sortare, elemente pare, maxime |
| Modulul 3 | Șiruri de caractere | Operații cu șiruri, inversare, palindrom, numărare de caractere |
| Modulul 4 | Subprograme | Funcții și proceduri, parametri, valori de return, modularizare |
| Modulul 5 | Recursivitate | Funcții recursive, factorial, Fibonacci, CMMDC, Hanoi, vectori, matrice |
Funcțiile recursive esențiale și tabelul rezumativ mare
Tabelul rezumativ mare concentrează toate funcțiile recursive învățate: pentru fiecare funcție reținem formula de recurență (formula care exprimă valoarea curentă prin valorile anterioare), cazul de bază și exemplul de verificare. Acest tabel este suficient pentru a reconstrui orice program la evaluare.
| Funcție | Recurența | Caz de bază | Verificare |
|---|---|---|---|
factorial(n) |
n · factorial(n − 1) | n == 0 → 1 | factorial(5) = 120 |
fib(n) |
fib(n − 1) + fib(n − 2) | n == 0 → 0; n == 1 → 1 | fib(10) = 55 |
cmmdc(a, b) |
cmmdc(b, a % b) | b == 0 → a | cmmdc(48, 18) = 6 |
suma_cifre(n) |
n % 10 + suma_cifre(n / 10) | n == 0 → 0 | suma_cifre(1234) = 10 |
numar_cifre(n) |
1 + numar_cifre(n / 10) | n < 10 → 1 | numar_cifre(12345) = 5 |
hanoi(n, s, a, d) |
hanoi(n−1, s, d, a); mutare; hanoi(n−1, a, s, d) | n == 1 → mutare directă | M(3) = 7 mutări |
suma_vector(v, i, n) |
v[i] + suma_vector(v, i + 1, n) | i == n → 0 | suma({1,2,3,4}) = 10 |
suma_matrice(a, n, m, i, j) |
a[i][j] + suma_matrice(i, j + 1); la j == m → i + 1, 0 | i == n → 0 | suma 2×3 = 21 |
#include <iostream>
using namespace std;
// Pasul 1: factorialul recursiv
long long factorial(int n)
{
if (n == 0)
return 1;
return n * factorial(n - 1);
}
// Pasul 2: suma cifrelor recursiv
int suma_cifre(int n)
{
if (n == 0)
return 0;
return n % 10 + suma_cifre(n / 10);
}
// Pasul 3: numarul de cifre recursiv
int numar_cifre(int n)
{
if (n < 10)
return 1;
return 1 + numar_cifre(n / 10);
}
// Pasul 4: CMMDC recursiv (algoritmul lui Euclid)
int cmmdc(int a, int b)
{
if (b == 0)
return a;
return cmmdc(b, a % b);
}
// Pasul 5: suma elementelor unui vector, recursiv
int suma_vector(int v[], int i, int n)
{
if (i == n)
return 0;
return v[i] + suma_vector(v, i + 1, n);
}
int main()
{
int n, a, b, v[1001];
// Pasul 6: prelucrarile numerice
cout << "n = ";
cin >> n;
cout << "Factorial = " << factorial(n) << endl;
cout << "Suma cifrelor = " << suma_cifre(n) << endl;
cout << "Numarul de cifre = " << numar_cifre(n) << endl;
// Pasul 7: CMMDC
cout << "a = ";
cin >> a;
cout << "b = ";
cin >> b;
cout << "CMMDC = " << cmmdc(a, b) << endl;
// Pasul 8: vectorul
cout << "Numarul de elemente ale vectorului: ";
cin >> n;
for (int i = 0; i < n; i++)
cin >> v[i];
cout << "Suma vectorului = " << suma_vector(v, 0, n);
return 0;
}
De reținut
- Tabelul rezumativ acoperă toate funcțiile recursive cerute la evaluare.
- Fiecare funcție are exact două părți: cazul de bază și pasul recursiv.
- Verificările din tabel (120, 55, 6, 10, 5) permit testarea rapidă a oricărui program.
Cum abordăm o problemă integrată de recapitulare
Definiție: O problemă integrată combină cel puțin două module: de exemplu, citirea unui vector (Modulul 2), prelucrarea lui printr-un subprogram (Modulul 4) și calcularea unei proprietăți recursive (Modulul 5). Pașii de rezolvare sunt: identificarea datelor, alegerea structurilor, scrierea funcțiilor și verificarea.
Pașii unei rezolvări corecte
- Pasul 1: identifică datele de intrare și de ieșire din enunț.
- Pasul 2: alege structurile de date potrivite (variabile, vector, matrice, șir).
- Pasul 3: scrie întâi funcțiile recursive, cu caz de bază și pas recursiv.
- Pasul 4: scrie main-ul: citire, apeluri, afișare.
- Pasul 5: verifică pe exemplul din enunț și pe cazuri limită.
Exercițiu de completare
Completează enunțul despre recapitulare cu cuvintele potrivite:
Materia clasei a X-a este organizată în ______ module. Modulul 5 tratează subprogramele ______. Tabelul rezumativ reține pentru fiecare funcție recurența, ______ și exemplul de verificare. O problemă care combină vectori cu funcții recursive se numește problemă ______.
Bancă de cuvinte:
Exercițiu de completare
Completează funcțiile din tabelul rezumativ:
Bancă de cuvinte:
Test de înțelegere
Test rapid - recapitulare:
1. Cazul de bază al funcției numar_cifre este:
2. fib(10) are valoarea:
3. Suma elementelor vectorului {1, 2, 3, 4}, calculată recursiv, este:
Aprofundare
Legăturile dintre module. Subprogramele din Modulul 4 sunt „instrumentele" folosite de recursivitate în Modulul 5: o funcție recursivă este un subprogram cu o proprietate specială. Șirurile de caractere din Modulul 3 se prelucrează recursiv prin indici (inversare, palindrom), iar vectorii și matricele din Modulul 2 se parcurg recursiv prin poziție.
Probleme integrate tipice la evaluare. Cele mai frecvente combinații sunt: număr + vector (de exemplu, afișarea divizorilor unui număr cu ajutorul unei funcții), vector + recursivitate (suma, maximul, numărarea parelor) și șir + recursivitate (palindrom, inversare). Rezolvarea urmează întotdeauna aceiași pași: date, structuri, funcții, verificare.
Complexitatea programelor de recapitulare. Tabelul rezumativ arată și eficiența: CMMDC și suma cifrelor sunt logaritmice sau liniare, în timp ce Fibonacci naiv este exponențial. La problemele cu restricții mari, varianta iterativă sau memoizarea devin obligatorii.
Pregătirea pentru evaluarea finală. Scrie din memorie toate funcțiile din tabel, verifică-le cu exemplele date și apoi rezolvă o problemă integrată completă, de la enunț la afișare. Această rutină de trei pași este cea mai eficientă formă de pregătire.
PbInfo - Suma cifrelor și numărul de cifre
Enunț:
Cerință: Se citește un număr natural n. Să se afișeze suma cifrelor și numărul de cifre ale lui n, folosind două funcții recursive.
Date de intrare:
Programul citește de la tastatură numărul natural n.
Date de ieșire:
Programul va afișa pe ecran, pe linii separate, suma cifrelor și numărul de cifre.
Restricții și precizări:
0 ≤ n ≤ 2.000.000.000.
Exemplu:
Intrare:
12345
Ieșire:
15 5
Cum gândim soluția:
- Definim
suma_cifre(n)cu cazul de bazăn == 0 - Definim
numar_cifre(n)cu cazul de bazăn < 10 - În main citim n și afișăm cele două rezultate
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int suma_cifre(int n)
{
if (n == 0)
return 0;
return n % 10 + suma_cifre(n / 10);
}
int numar_cifre(int n)
{
if (n < 10)
return 1;
return 1 + numar_cifre(n / 10);
}
int main()
{
int n;
cin >> n;
cout << suma_cifre(n) << endl;
cout << numar_cifre(n);
return 0;
}
Ce învățăm: aceeași descompunere n / 10 servește două funcții diferite; doar cazul de bază și operația aplicată cifrei se schimbă.
PbInfo - Suma elementelor unui vector cu subprogram recursiv
Enunț:
Cerință: Se citesc n și n numere naturale. Să se afișeze suma elementelor vectorului, folosind un subprogram recursiv de parcurgere.
Date de intrare:
Programul citește de la tastatură numărul n, apoi n numere naturale.
Date de ieșire:
Programul va afișa pe ecran suma elementelor vectorului.
Restricții și precizări:
1 ≤ n ≤ 1000, elemente numere naturale mai mici decât 1000.
Exemplu:
Intrare:
4 1 2 3 4
Ieșire:
10
Cum gândim soluția:
- Definim
suma_vector(v, i, n) - Cazul de bază: dacă
i == n, întoarcem 0 - Întoarcem
v[i] + suma_vector(v, i + 1, n) - În main citim vectorul și afișăm rezultatul
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int suma_vector(int v[], int i, int n)
{
if (i == n)
return 0;
return v[i] + suma_vector(v, i + 1, n);
}
int main()
{
int n, v[1001];
cin >> n;
for (int i = 0; i < n; i++)
cin >> v[i];
cout << suma_vector(v, 0, n);
return 0;
}
Ce învățăm: vectorul se transmite prin numele său (adresa primului element); parcurgerea se face cu indicele i, până la cazul de bază i == n.
Exercițiul Practic: Probleme integrate de recapitulare
Sarcini de lucru
Rezolvă sarcinile următoare, care combină modulele clasei a X-a
Sarcina 1: Numărul de elemente pare dintr-un vector
Cerință: Scrie un program C++ care afișează numărul de elemente pare dintr-un vector, folosind o funcție recursivă. Pentru v = {1, 4, 3, 8}, rezultatul este 2.
Soluție pentru Sarcina 1:
#include <iostream>
using namespace std;
int numara_pare(int v[], int i, int n)
{
if (i == n)
return 0;
int c = numara_pare(v, i + 1, n);
if (v[i] % 2 == 0)
c++;
return c;
}
int main()
{
int n, v[1001];
cin >> n;
for (int i = 0; i < n; i++)
cin >> v[i];
cout << numara_pare(v, 0, n);
return 0;
}
Verifică: pentru v = {1, 4, 3, 8}, elementele pare sunt 4 și 8, deci rezultatul este 2.
Sarcina 2: Verificarea unui palindrom recursiv
Cerință: Scrie un program C++ care verifică dacă un șir de caractere este palindrom, folosind o funcție recursivă cu doi indici (stânga și dreapta). Pentru „radar" răspunsul este DA, pentru „bac" este NU.
Soluție pentru Sarcina 2:
#include <iostream>
#include <cstring>
using namespace std;
int palindrom(char s[], int i, int j)
{
if (i >= j)
return 1;
if (s[i] != s[j])
return 0;
return palindrom(s, i + 1, j - 1);
}
int main()
{
char s[101];
cin >> s;
if (palindrom(s, 0, strlen(s) - 1))
cout << "DA";
else
cout << "NU";
return 0;
}
Verifică: pentru „radar", prima și ultima literă coincid și așa mai departe; cazul de bază este i ≥ j, când răspunsul este DA.