Clasa X - Ora 12: Proiect integrat recursiv | Școala Româno-Britanică

SINTEZĂ TEORETICĂ ȘI EXEMPLE GHIDATE

Ce vei învăța astăzi?

După această lecție vei proiecta arhitectura unei aplicații modulare, vei scrie cinci funcții recursive complete și vei construi un meniu funcțional cu validarea intrărilor (verificarea datelor citite înainte de utilizare).

Arhitectura proiectului integrat

Cinci funcții recursive în C++

Meniu interactiv și validări

Proiect complet stil BAC

Arhitectura proiectului integrat

Definiție: Un proiect integrat este o aplicație care reunește mai multe funcții independente, fiecare cu o responsabilitate clară, coordonate de un program principal. Aplicația noastră oferă cinci prelucrări recursive: factorial, fib, cmmdc, suma_cifre și inversare_sir.

Principiul modularizării: fiecare funcție este scrisă, testată și corectată separat; integrarea lor în meniu nu modifică corpul funcțiilor, ci doar le apelează.

Analogia: o firmă cu cinci departamente

Imaginează-ți o firmă în care fiecare departament rezolvă un singur tip de sarcină: departamentul de calcul primește un număr și întoarce factorialul, altul întoarce termenul Fibonacci, și așa mai departe. Recepția (funcția main) primește cererea clientului, o trimite departamentului potrivit și afișează răspunsul. Dacă un departament funcționează greșit, îl reparăm pe el, fără să atingem celelalte.

Recepția

Este funcția main: afișează meniul și trimite opțiunea mai departe

Departamentele

Sunt funcțiile recursive, fiecare cu o singură responsabilitate

Cererea clientului

Este opțiunea citită: 1, 2, 3, 4 sau 5

Funcție	Ce calculează	Cazul de bază
`factorial(n)`	n! = n · (n − 1) · ... · 1	`n == 0 → 1`
`fib(n)`	Termenul n din șirul lui Fibonacci	`n == 0 → 0`, `n == 1 → 1`
`cmmdc(a, b)`	Cel mai mare divizor comun	`b == 0 → a`
`suma_cifre(n)`	Suma cifrelor lui n	`n == 0 → 0`
`inversare_sir(s, i, j)`	Inversează caracterele unui șir	`i ≥ j → oprire`

Aplicația completă cu cele cinci funcții recursive

Programul afișează un meniu cu cinci opțiuni numerotate și opțiunea 0 pentru ieșire. Pentru fiecare opțiune, citește datele necesare, apelează funcția recursivă potrivită și afișează rezultatul. Structura do...while asigură afișarea meniului cel puțin o dată.

Algoritm proiect integrat: repetă afișează meniul: 1 - Factorial 2 - Fibonacci 3 - CMMDC 4 - Suma cifrelor 5 - Inversare șir 0 - Ieșire citește opțiunea dacă opțiunea == 1 atunci citește n; afișează factorial(n) dacă opțiunea == 2 atunci citește n; afișează fib(n) dacă opțiunea == 3 atunci citește a, b; afișează cmmdc(a, b) dacă opțiunea == 4 atunci citește n; afișează suma_cifre(n) dacă opțiunea == 5 atunci citește s; afișează inversarea lui s cât timp opțiunea != 0

Program C++ - proiect integrat cu cinci funcții recursive

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

// Pasul 1: factorialul recursiv
long long factorial(int n)
{
    if (n == 0)
        return 1;
    return n * factorial(n - 1);
}

// Pasul 2: termenul Fibonacci recursiv
long long fib(int n)
{
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;
    return fib(n - 1) + fib(n - 2);
}

// Pasul 3: CMMDC prin algoritmul lui Euclid, recursiv
int cmmdc(int a, int b)
{
    if (b == 0)
        return a;
    return cmmdc(b, a % b);
}

// Pasul 4: suma cifrelor, recursiv
int suma_cifre(int n)
{
    if (n == 0)
        return 0;
    return n % 10 + suma_cifre(n / 10);
}

// Pasul 5: inversarea unui sir de caractere, recursiv, prin interschimbari
void inversare_sir(char s[], int i, int j)
{
    if (i >= j)
        return;
    char aux = s[i];
    s[i] = s[j];
    s[j] = aux;
    inversare_sir(s, i + 1, j - 1);
}

int main()
{
    int opt, n, a, b;
    char s[101];
    do
    {
        // Pasul 6: afisam meniul
        cout << "1. Factorial" << endl;
        cout << "2. Fibonacci" << endl;
        cout << "3. CMMDC" << endl;
        cout << "4. Suma cifrelor" << endl;
        cout << "5. Inversare sir" << endl;
        cout << "0. Iesire" << endl;
        cout << "Optiunea: ";
        cin >> opt;
        // Pasul 7: executam operatia ceruta
        if (opt == 1)
        {
            cout << "n = ";
            cin >> n;
            cout << "Factorial = " << factorial(n) << endl;
        }
        else if (opt == 2)
        {
            cout << "n = ";
            cin >> n;
            cout << "Fibonacci = " << fib(n) << endl;
        }
        else if (opt == 3)
        {
            cout << "a = ";
            cin >> a;
            cout << "b = ";
            cin >> b;
            cout << "CMMDC = " << cmmdc(a, b) << endl;
        }
        else if (opt == 4)
        {
            cout << "n = ";
            cin >> n;
            cout << "Suma cifrelor = " << suma_cifre(n) << endl;
        }
        else if (opt == 5)
        {
            cout << "sir = ";
            cin >> s;
            inversare_sir(s, 0, strlen(s) - 1);
            cout << "Inversat = " << s << endl;
        }
        else if (opt != 0)
        {
            cout << "Optiune inexistenta!" << endl;
        }
    } while (opt != 0);
    return 0;
}

Verificări rapide pentru fiecare funcție

factorial(5) = 120
fib(10) = 55
cmmdc(48, 18) = 6
suma_cifre(1234) = 10
inversare_sir("abc") = "cba"

Meniul interactiv și validarea intrărilor

Definiție: Un meniu interactiv este o structură de control care afișează opțiunile disponibile, citește alegerea utilizatorului și execută acțiunea corespunzătoare, repetând procesul până la alegerea ieșirii. Validarea verifică dacă valoarea citită este permisă înainte de a fi folosită.

De ce este importantă validarea?

Opțiunile din afara intervalului 0-5 trebuie să afișeze un mesaj, nu să termine programul cu eroare.
Un n negativ la factorial ar produce apeluri recursive infinite, deoarece n nu mai ajunge niciodată la 0.
Un n prea mare la Fibonacci ar face programul extrem de lent din cauza recalculărilor.

De reținut

Funcțiile se definesc înaintea funcției main, pentru a putea fi apelate.
Bucla do...while este potrivită pentru meniuri: corpul se execută cel puțin o dată.
Fiecare funcție are un singur scop, un caz de bază clar și un pas recursiv care reduce problema.
Un else if (opt != 0) final tratează opțiunile inexistente.

Exercițiu de completare

Completează enunțul despre proiectul integrat cu cuvintele potrivite:

Proiectul integrat reunește mai multe funcții ______, fiecare cu o singură responsabilitate. Meniul este implementat cu o structură ______, care execută corpul cel puțin o dată. Opțiunile inexistente trebuie tratate cu un mesaj, proces numit ______. Funcțiile sunt definite înaintea funcției ______.

Bancă de cuvinte:

recursive do...while validare main

Exercițiu de completare

Completează funcțiile recursive ale proiectului:

long long factorial(int n)

{

if (n == 0)

______ 1;

return n * factorial(______);

}

int cmmdc(int a, int b)

{

if (______)

return a;

return cmmdc(b, a ______);

}

Bancă de cuvinte:

return n - 1 b == 0 % b

Test de înțelegere

Test rapid - proiect integrat:

1. Structura potrivită pentru un meniu este:

for cu un număr fix de iterații do...while, care execută corpul cel puțin o dată if fără buclă

2. Cazul de bază al funcției inversare_sir este:

i == 0 j == strlen(s) i ≥ j

3. Dacă utilizatorul introduce opțiunea 9, programul corect:

se termină imediat cu eroare afișează un mesaj de validare și reafișează meniul calculează factorialul lui 9

Ai grijă la: validarea intrărilor - fără ea, un n negativ sau o opțiune inexistentă poate duce la apeluri recursive infinite sau la rezultate greșite; verifică întotdeauna domeniul.

Aprofundare

Eficiența în proiecte integrate. Într-un proiect real, funcțiile recursive costisitoare (Fibonacci naiv) pot fi optimizate cu memoizare sau variante iterative. Proiectul devine astfel nu doar corect, ci și rapid pentru valori mari de intrare, un criteriu des întâlnit în baremele de evaluare.

Funcții auxiliare și protecția intrărilor. O versiune robustă adaugă funcții precum citire_validata(), care citește valorile în buclă până când acestea respectă restricțiile (n ≥ 0, opțiune în intervalul 0-5). Astfel, funcțiile recursive nu primesc niciodată valori care le-ar duce în recursie infinită.

Extinderea proiectului. Adăugarea unei a șasea funcții (de exemplu, numărul de cifre sau turnurile din Hanoi) presupune doar trei pași: definirea funcției, afișarea noii opțiuni în meniu și o nouă ramură în structura de decizie. Această extensibilitate este dovada calității modularizării.

Reutilizarea codului. Funcțiile proiectului pot fi copiate direct în alte programe: ele nu depind de meniu, ci doar de parametrii lor. Acesta este motivul pentru care se scriu fără afișări interne, întorcând doar rezultatul.

APLICARE ȘI REZOLVARE DE PROBLEME

PbInfo - Inversarea unui șir de caractere recursiv

Enunț:

Cerință: Se citește un șir de caractere s. Să se afișeze șirul inversat, obținut prin interschimbarea caracterelor, folosind un subprogram recursiv.

Date de intrare:

Programul citește de la tastatură un șir de caractere cu cel mult 100 de caractere.

Date de ieșire:

Programul va afișa pe ecran șirul inversat.

Restricții și precizări:

Șirul conține doar litere mici ale alfabetului englez. Rezolvarea se face cu un subprogram recursiv care realizează interschimbări.

Exemplu:

Intrare:

informatica

Ieșire:

acitamrofni

Cum gândim soluția:

Definim funcția inversare_sir(s, i, j) cu indicii extremităților
Cazul de bază: dacă i ≥ j, ne oprim
Interschimbăm s[i] cu s[j]
Reapelăm cu i + 1 și j - 1

Scrie soluția în C++:

Soluție corectă:

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

void inversare_sir(char s[], int i, int j)
{
    if (i >= j)
        return;
    char aux = s[i];
    s[i] = s[j];
    s[j] = aux;
    inversare_sir(s, i + 1, j - 1);
}

int main()
{
    char s[101];
    cin >> s;
    inversare_sir(s, 0, strlen(s) - 1);
    cout << s;
    return 0;
}

Ce învățăm: interschimbarea se face înaintea apelului recursiv; indicii se apropie unul de celălalt, deci numărul de apeluri este jumătate din lungimea șirului.

PbInfo - Aplicație cu meniu și funcții recursive

Enunț:

Cerință: Se cere un program cu meniu care oferă următoarele opțiuni: 1 - factorial(n), 2 - suma cifrelor lui n, 0 - ieșire. Pentru fiecare opțiune numerică, programul citește n și afișează rezultatul, folosind funcții recursive. Meniul se reafișează până la alegerea opțiunii 0.

Date de intrare:

Programul citește opțiuni și valori de la tastatură, până la introducerea opțiunii 0.

Date de ieșire:

Programul va afișa rezultatul operației alese pentru fiecare opțiune.

Restricții și precizări:

0 ≤ n ≤ 20 pentru factorial; 0 ≤ n ≤ 2.000.000.000 pentru suma cifrelor.

Exemplu:

Intrare:

1 5
2 1234
0

Ieșire:

120
10

Cum gândim soluția:

Definim factorial(n) și suma_cifre(n) recursive
În main, folosim do...while pentru a afișa meniul și a citi opțiunea
Pentru fiecare opțiune, citim n, apelăm funcția și afișăm rezultatul
Bucla se termină când opțiunea citită este 0

Scrie soluția în C++:

Soluție corectă:

#include <iostream>
using namespace std;

long long factorial(int n)
{
    if (n == 0)
        return 1;
    return n * factorial(n - 1);
}

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

int main()
{
    int opt, n;
    do
    {
        cout << "1. Factorial" << endl;
        cout << "2. Suma cifrelor" << endl;
        cout << "0. Iesire" << endl;
        cout << "Optiunea: ";
        cin >> opt;
        if (opt == 1)
        {
            cin >> n;
            cout << factorial(n) << endl;
        }
        else if (opt == 2)
        {
            cin >> n;
            cout << suma_cifre(n) << endl;
        }
    } while (opt != 0);
    return 0;
}

Ce învățăm: meniul combină citirea opțiunii, validarea implicită (opțiunile 1 și 2) și apelul funcțiilor recursive, într-o structură do...while.

EXERCIȚII PRACTICE

Exercițiul Practic: Extinderea proiectului integrat

Sarcini de lucru

Completează sarcinile următoare pentru a-ți dezvolta propriul proiect integrat recursiv

Sarcina 1: Adaugă opțiunea „Numărul de cifre"

Cerință: Extinde proiectul integrat cu o funcție recursivă numar_cifre(n) care întoarce numărul de cifre ale lui n, și cu opțiunea 6 în meniu. Scrie doar funcția nouă și ramura if corespunzătoare. Pentru n = 12345, rezultatul este 5.

Scrie programul C++ aici:

Soluție pentru Sarcina 1:

int numar_cifre(int n)
{
    if (n < 10)
        return 1;
    return 1 + numar_cifre(n / 10);
}

// in main, in interiorul buclei do...while:
else if (opt == 6)
{
    cout << "n = ";
    cin >> n;
    cout << "Numarul de cifre = " << numar_cifre(n) << endl;
}

Verifică: pentru n = 12345, cazul de bază este n < 10, deci numărul de cifre este 5.

Sarcina 2: Scrie o funcție de afișare recursivă a cifrelor

Cerință: Scrie o funcție recursivă afiseaza_cifre(n) care afișează cifrele lui n separate prin spații, de la ultima către prima. Pentru n = 1234, se afișează 4 3 2 1. Indică și cazul de bază.

Scrie programul C++ aici:

Soluție pentru Sarcina 2:

#include <iostream>
using namespace std;

void afiseaza_cifre(int n)
{
    if (n == 0)
        return;
    cout << n % 10 << " ";
    afiseaza_cifre(n / 10);
}

int main()
{
    int n;
    cin >> n;
    afiseaza_cifre(n);
    return 0;
}

Verifică: afișarea se face înaintea apelului recursiv, deci cifrele apar la coborârea pe stivă: 4 3 2 1.

Ora 12: Proiect integrat recursiv

Înainte de a începe

Ce știi deja?

Ce vei învăța astăzi?

Arhitectura proiectului integrat

Analogia: o firmă cu cinci departamente

Aplicația completă cu cele cinci funcții recursive

Verificări rapide pentru fiecare funcție

Meniul interactiv și validarea intrărilor

De ce este importantă validarea?

De reținut

Exercițiu de completare

Completează enunțul despre proiectul integrat cu cuvintele potrivite:

Bancă de cuvinte:

Exercițiu de completare

Completează funcțiile recursive ale proiectului:

Bancă de cuvinte:

Test de înțelegere

Test rapid - proiect integrat:

Aprofundare

PbInfo - Inversarea unui șir de caractere recursiv

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 - Aplicație cu meniu și funcții recursive

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: Extinderea proiectului integrat

Sarcini de lucru

Sarcina 1: Adaugă opțiunea „Numărul de cifre"

Soluție pentru Sarcina 1:

Sarcina 2: Scrie o funcție de afișare recursivă a cifrelor

Soluție pentru Sarcina 2:

Scrie pe caiet

Titlul lecției

Definiția lecției

Definiții esențiale

Algoritmul cheie - pseudocod

Algoritmul cheie - cod C++

Greșeli comune de evitat

Exemplu practic

Sfaturi practice și trucuri