Școala Româno-Britanică
Modulul 5 Clasa a X-a | C++

Ora 9: Recapitulare generală

Ce vei învăța astăzi: Recapitularea materiei clasei a X-a pe module, cu tabel rezumativ (tabel care concentrează pe scurt temele și exemplele) și funcții recursive esențiale

Rezultat practic: Recapitulezi toate modulele și rezolvi programe complexe de recapitulare în C++ (Competența 6.5)

Competența 6.5 Săptămâna 29

Înainte de a începe

De ce contează? Recapitularea fixează toate funcțiile recursive din modul, iar tabelul rezumativ este instrumentul rapid cu care te verifici înaintea testului.

Ce știi deja?

Din ora 8, știi de ce un meniu folosește structura do...while? Poți enumera funcțiile recursive integrate în proiectul anterior?

Ideea-cheie: Toate funcțiile recursive urmează același tipar: caz de bază care oprește, pas recursiv care reduce problema (o aduce tot mai aproape de cazul de bază) și combinarea rezultatului.
SINTEZĂ TEORETICĂ ȘI EXEMPLE GHIDATE

Ce vei învăța astăzi?

După această lecție vei recapitula materia clasei a X-a pe module, vei consulta un tabel rezumativ cu temele și exemplele fiecărui modul și vei rezolva un program complex de recapitulare în C++.

Recapitularea materiei pe module
Tabel rezumativ Modulul 1-5
Exemple de rezolvare
Program de recapitulare C++

Recapitularea materiei pe module

În clasa a X-a am parcurs cinci module. Iată ce am învățat în fiecare dintre ele:

Modul Unde Teme Exemple
Modulul 1 Clasa X - Modul 1 Elemente de bază C++ citire, afișare, variabile
Modulul 2 Clasa X - Modul 2 Structuri de decizie și repetiție if, for, while
Modulul 3 Clasa X - Modul 3 Tabloade unidimensionale vectori, prelucrări
Modulul 4 Clasa X - Modul 4 Subprograme (funcții și proceduri) definire, apel, parametri
Modulul 5 Clasa X - Modul 5 Subprograme recursive factorial, CMMDC, Hanoi

Funcțiile recursive esențiale

Funcție Definiție recursivă Caz de bază Exemplu
factorial(n) n * factorial(n - 1) n == 0 → 1 factorial(5) = 120
suma_cifre(n) n % 10 + suma_cifre(n / 10) n == 0 → 0 suma_cifre(1234) = 10
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

Observă: toate funcțiile recursive au un caz de bază clar și un pas recursiv care reduce problema.

Program de recapitulare: numere perfecte și CMMDC

Algoritm program de recapitulare: citește n pentru fiecare divizor d al lui n (1 ≤ d ≤ n / 2) dacă n % d == 0 atunci adună d la suma divizorilor dacă suma == n atunci afișează "numar perfect" (număr egal cu suma divizorilor proprii, de exemplu 6 = 1 + 2 + 3) citește a, b afișează cmmdc(a, b) cu algoritmul lui Euclid recursiv
Program C++ - recapitulare (divizori, CMMDC, cifre)
#include <iostream>
using namespace std;

int cmmdc(int a, int b)
{
    if (b == 0)
        return a;
    return cmmdc(b, a % b);
}

bool este_prim(int n)
{
    if (n < 2)
        return false;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0)
            return false;
    return true;
}

int main()
{
    int n, a, b;
    cout << "n = ";
    cin >> n;
    if (este_prim(n))
        cout << "n este prim" << endl;
    else
        cout << "n nu este prim" << endl;

    cout << "a b = ";
    cin >> a >> b;
    cout << "cmmdc = " << cmmdc(a, b) << endl;
    return 0;
}

De reținut la examen

  • Un număr prim are exact doi divizori: 1 și el însuși
  • CMMDC se calculează elegant recursiv cu algoritmul lui Euclid
  • Verifică întotdeauna cazul de bază pentru a evita recursivitatea infinită
  • Folosește long long pentru rezultate mari

Exercițiu de completare

Completează tabelul rezumativ cu cuvintele potrivite:

În ______ am învățat elementele de bază C++: citire, afișare și variabile. În Modulul 2 am studiat structurile de ______ și repetiție. În Modulul 3 am lucrat cu ______. În Modulul 4 am definit ______, iar în Modulul 5 am studiat recursivitatea.

Bancă de cuvinte:
Modulul 1 decizie vectori subprograme

Exercițiu de completare

Completează funcțiile recursive de recapitulare:
// factorial
if (n == 0) ______;
return n * factorial(n - 1);
// suma cifrelor
if (n == 0) return 0;
return n % 10 + suma_cifre(______);
// cmmdc
if (b == 0) ______;
return cmmdc(b, a % b);
Bancă de cuvinte:
return 1 n / 10 return a

Test de înțelegere

Test rapid - recapitulare:

1. Șirul lui Fibonacci a fost studiat în:

2. CMMDC(12, 18) are valoarea:

3. Pentru ca o funcție recursivă să se termine, este obligatoriu:

Ai grijă la: confundarea cazurilor de bază între funcții - 0! = 1, dar suma cifrelor lui 0 este 0, iar fib(0) = 0; fiecare funcție are propriul caz de bază.

Aprofundare

Panorama modulelor clasei a X-a. Modulul 1 a acoperit algoritmi de bază (divizori, prime, cifre), Modulul 2 structuri repetitive și vectori, Modulul 3 prelucrarea șirurilor de caractere, Modulul 4 subprograme (funcții și proceduri), iar Modulul 5 a adus subprogramele recursive. Un program de recapitulare care combină elemente din toate modulele verifică, de fapt, înțelegerea întregului an școlar.

Recursivitate vs. iterație - decizia corectă.

  • Recursivitatea este elegantă și naturală pentru probleme definite recurent (factorial, Fibonacci, CMMDC, Hanoi, parcurgeri).
  • Iterația este mai eficientă la memorie și evită riscul depășirii stivei pentru valori mari.
  • În evaluări, ambele variante sunt acceptate dacă rezultatul este corect, dar codul recursiv trebuie să aibă obligatoriu caz de bază.

Tipuri de date în funcții recursive. Rezultatul trebuie să aibă tipul potrivit: long long pentru factorial și Fibonacci, int pentru sume și CMMDC. O funcție declarată cu tip greșit produce rezultate incorecte prin depășire, chiar dacă logica este bună.

Verificarea pe exemple mici. Înainte de a considera un program terminat, verifică-l pe 2-3 exemple cunoscute: factorial(5) = 120, fib(10) = 55, cmmdc(48, 18) = 6, suma_cifre(1234) = 10. Un tabel cu aceste valori este cel mai bun instrument de testare.

APLICARE ȘI REZOLVARE DE PROBLEME

PbInfo - Numere prime în interval

Enunț:

Cerință: Se citesc două numere naturale a și b (a ≤ b). Să se afișeze toate numerele prime din intervalul [a, b], separate prin spații. Pentru verificarea primalității se folosește o funcție (subprogram).

Date de intrare:

Programul citește de la tastatură numerele a și b.

Date de ieșire:

Programul va afișa pe ecran numerele prime din interval, separate prin spații.

Restricții și precizări:

1 ≤ a ≤ b ≤ 1.000.000.

Exemplu:

Intrare:

10 20

Ieșire:

11 13 17 19
Cum gândim soluția:
  1. Definim funcția este_prim(n) care întoarce true sau false
  2. Parcurgem intervalul [a, b]
  3. Pentru fiecare număr, dacă este prim, îl afișăm
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;

bool este_prim(int n)
{
    if (n < 2)
        return false;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0)
            return false;
    return true;
}

int main()
{
    int a, b;
    cin >> a >> b;
    for (int i = a; i <= b; i++)
        if (este_prim(i))
            cout << i << " ";
    return 0;
}

Ce învățăm: recapitulăm subprogramele din Modulul 4 și structurile repetitive din Modulul 2.

PbInfo - CMMDC a mai multor numere

Enunț:

Cerință: Se citesc n numere naturale. Să se afișeze CMMDC-ul tuturor numerelor, folosind funcția recursivă cmmdc.

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 CMMDC-ul celor n numere.

Restricții și precizări:

1 ≤ n ≤ 100, numere naturale.

Exemplu:

Intrare:

4
24 36 60 12

Ieșire:

12
Cum gândim soluția:
  1. Definim funcția recursivă cmmdc(a, b)
  2. Citim n și primul număr, îl stocăm în d
  3. Pentru fiecare număr citit, d = cmmdc(d, x)
  4. Afișăm d
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;

int cmmdc(int a, int b)
{
    if (b == 0)
        return a;
    return cmmdc(b, a % b);
}

int main()
{
    int n, d, x;
    cin >> n;
    cin >> d;
    for (int i = 2; i <= n; i++)
    {
        cin >> x;
        d = cmmdc(d, x);
    }
    cout << d;
    return 0;
}

Ce învățăm: CMMDC-ul unui șir de numere se obține prin aplicarea repetată a funcției.

EXERCIȚII PRACTICE

Exercițiul Practic: Recapitulare finală

Sarcini de lucru

Rezolvă sarcinile următoare pentru a-ți consolida materia

Sarcina 1: Suma și produsul cifrelor

Cerință: Scrie un program C++ care citește n și afișează suma și produsul cifrelor lui n, folosind funcții recursive. Pentru n = 123, suma este 6 și produsul este 6.

Soluție pentru Sarcina 1:
#include <iostream>
using namespace std;

int suma_cifre(int n)
{
    if (n == 0)
        return 0;
    return n % 10 + suma_cifre(n / 10);
}

int produs_cifre(int n)
{
    if (n == 0)
        return 1;
    return (n % 10) * produs_cifre(n / 10);
}

int main()
{
    int n;
    cin >> n;
    cout << suma_cifre(n) << " " << produs_cifre(n);
    return 0;
}
Sarcina 2: Verifică un număr palindrom

Cerință: Scrie un program C++ care verifică dacă un număr n este palindrom (se citește la fel de la stânga la dreapta și invers), folosind o funcție recursivă pentru inversarea numărului. Pentru n = 12321 răspunsul este DA.

Soluție pentru Sarcina 2:
#include <iostream>
using namespace std;

int invers(int n, int r)
{
    if (n == 0)
        return r;
    return invers(n / 10, r * 10 + n % 10);
}

int main()
{
    int n;
    cin >> n;
    if (invers(n, 0) == n)
        cout << "DA";
    else
        cout << "NU";
    return 0;
}

Verifică: pentru n = 12321, inversul este tot 12321, deci numărul este palindrom.

Scrie pe caiet

Titlul lecției

Recapitulare generală. A noua lecție din Modulul 5 îți fixează materia clasei a X-a, pe module, înaintea testului final.

Definiția lecției

Recapitularea generală adună materia clasei a X-a în cinci module: elemente de bază C++, structuri de decizie și repetiție, tabloade unidimensionale, subprograme și subprograme recursive. Toate funcțiile recursive urmează același tipar: caz de bază care oprește, pas recursiv care reduce problema și combinarea rezultatului. Tabelul rezumativ concentrează recurențele, cazurile de bază și exemplele de verificare pentru fiecare funcție. Programul de recapitulare combină divizorii, numerele prime, CMMDC și cifrele unui număr. Un număr prim are exact doi divizori: 1 și el însuși, iar un număr perfect este egal cu suma divizorilor proprii. Verifică întotdeauna cazul de bază pentru a evita recursivitatea infinită.

Definiții esențiale

Algoritmul cheie - pseudocod

Algoritm program de recapitulare: citește n calculează suma divizorilor proprii ai lui n dacă suma == n atunci afișează "numar perfect" citește a, b afișează cmmdc(a, b) cu algoritmul lui Euclid recursiv

Algoritmul cheie - cod C++

Program C++ - recapitulare (divizori, CMMDC, cifre)
#include <iostream>
using namespace std;

int cmmdc(int a, int b)
{
    if (b == 0)
        return a;
    return cmmdc(b, a % b);
}

int main()
{
    int n, a, b, suma = 0;
    cout << "n = ";
    cin >> n;
    for (int d = 1; d <= n / 2; d++)
        if (n % d == 0)
            suma += d;
    if (suma == n)
        cout << n << " este numar perfect" << endl;
    else
        cout << n << " nu este numar perfect" << endl;
    cout << "a = ";
    cin >> a;
    cout << "b = ";
    cin >> b;
    cout << "CMMDC = " << cmmdc(a, b);
    return 0;
}

Greșeli comune de evitat

Exemplu practic

Scenariu real: verifici dacă 6 este număr perfect: divizorii proprii 1, 2 și 3 au suma 6, deci este perfect. Fragmentul de program:

Program C++ - număr perfect (exemplu practic)
int n, suma = 0;
cin >> n;
for (int d = 1; d <= n / 2; d++)
    if (n % d == 0)
        suma += d;
if (suma == n)
    cout << n << " este numar perfect";

Pentru n = 6, programul afișează «6 este numar perfect».

Sfaturi practice și trucuri