Cum Gândește Calculatorul? Partea a 9-a: Subprograme Complexe în C/C++

Salut! Acum ajungem la cea mai practică parte: scrierea de subprograme (funcții) complete. Acestea sunt probleme tipice de la Bacalaureat care valorează multe puncte. Hai să le abordăm sistematic!

🎯 Strategia pentru Scrierea Subprogramelor

1. Înțelege cerința – Citește de 2-3 ori până înțelegi ce trebuie să facă funcția
2. Analizează exemplul – Exemplele arată exact ce se așteaptă
3. Gândește algoritmul – Pe hârtie, în pași simpli
4. Scrie codul – Pas cu pas, cu variabile clare
5. Testează mental – Rulează cu datele din exemplu

---

📚 Rezolvări Complete pentru Fiecare Problemă

Problema 1: Subprogramul Plus – Înlocuirea 25 cu 26

Cerința: Înlocuiește fiecare secvență “25” cu “26” în număr.

Exemplu: 202535250 → 202635260

Soluție:

void Plus(int &n) {
    int rezultat = 0, putere = 1, cifra;

    while(n > 0) {
        cifra = n % 10;  // ultima cifră
        n = n / 10;      // elimină ultima cifră

        // Verificăm dacă avem secvența 25 (cifrele 5 și 2 consecutive)
        if(cifra == 5 && n % 10 == 2) {
            // Am găsit 25, îl înlocuim cu 26
            rezultat = 6 * putere + rezultat;  // punem 6 în loc de 5
            putere = putere * 10;
            rezultat = 2 * putere + rezultat;  // 2 rămâne
            n = n / 10;  // eliminăm și pe 2 din n
        } else {
            // Păstrăm cifra originală
            rezultat = cifra * putere + rezultat;
        }
        putere = putere * 10;
    }

    n = rezultat;
}

Explicație:

• Parcurgem numărul de la coadă la cap (de la unități la zeci, sute, etc.)
• Când găsim cifra 5 urmată de 2, înlocuim 5 cu 6
• Reconstruim numărul în variabila rezultat

---

Problema 2: Subprogramul teren – Împărțirea Terenului

Cerința: Găsește toate împărțirile unui teren dreptunghiular în parcele egale care respectă condițiile.

Condiții:

1. Număr parcele = par
2. Număr parcele < Aria unei parcele
3. Ambele valori sunt naturale

Soluție:

void teren(int x, int y) {
    int ariaTotala = x * y;
    int existaSolutii = 0;

    // Parcurgem toți divizorii ariei totale
    for(int nrParcele = 2; nrParcele <= ariaTotala; nrParcele += 2) {  // doar numere pare
        if(ariaTotala % nrParcele == 0) {
            int ariaParcele = ariaTotala / nrParcele;

            // Verificăm condiția: nrParcele < ariaParcele
            if(nrParcele < ariaParcele) {
                cout << nrParcele << " parcele de arie " << ariaParcele << endl;
                existaSolutii = 1;
            }
        }
    }

    if(!existaSolutii) {
        cout << "nu exista" << endl;
    }
}

Test pentru x=6, y=8:

• Aria totală = 48
• Parcurgem numere pare: 2, 4, 6, 8…
• 2 parcele × 24 m² → 2 < 24 ✓
• 4 parcele × 12 m² → 4 < 12 ✓
• 6 parcele × 8 m² → 6 < 8 ✓
• 8 parcele × 6 m² → 8 < 6 ✗

---

Problema 3: Subprogramul diviz – Cel mai mare divizor pătrat perfect

Cerința: Găsește cel mai mare divizor al lui n care este pătrat perfect.

Soluție:

int diviz(int n) {
    int maxDivizor = 1;  // 1 este pătrat perfect

    // Parcurgem de la n la 1 și căutăm pătrate perfecte
    for(int i = n; i >= 1; i--) {
        if(n % i == 0) {  // i este divizor al lui n
            // Verificăm dacă i este pătrat perfect
            int radacina = sqrt(i);
            if(radacina * radacina == i) {
                maxDivizor = i;
                break;  // am găsit cel mai mare (căutăm de sus în jos)
            }
        }
    }

    return maxDivizor;
}

Alternativă mai eficientă:

int diviz(int n) {
    int rezultat = 1;

    // Descompunem n în factori primi
    for(int d = 2; d * d <= n; d++) {
        int putere = 0;
        while(n % d == 0) {
            putere++;
            n = n / d;
        }
        // Luăm doar factorii la putere pară pentru pătrat perfect
        if(putere >= 2) {
            rezultat = rezultat * pow(d, putere - putere % 2);
        }
    }
    // Dacă n a rămas pătrat perfect după descompunere
    int rad = sqrt(n);
    if(rad * rad == n && n > 1) {
        rezultat = rezultat * n;
    }

    return rezultat;
}

---

Problema 4: Subprogramul moderat – Numere Moderate

Cerința: Un număr este “moderat” dacă este produsul a două numere prime consecutive.

Exemplu: 35 = 5 × 7 (5 și 7 sunt prime consecutive)

Soluție:

int prim(int numar) {
    if(numar < 2) return 0;
    if(numar == 2) return 1;
    if(numar % 2 == 0) return 0;

    for(int d = 3; d * d <= numar; d += 2) {
        if(numar % d == 0) return 0;
    }
    return 1;
}

int moderate(int n) {
    // Verificăm toate perechile de numere prime consecutive
    for(int p = 2; p * p <= n; p++) {
        if(prim(p)) {
            // Găsim următorul număr prim după p
            int q = p + 1;
            while(!prim(q) && q <= n) q++;

            if(prim(q) && p * q == n) {
                return 1;  // am găsit perechea
            }
        }
    }
    return 0;
}

Optimizare: Putem genera direct perechile de prime consecutive:

int moderate(int n) {
    int prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};

    for(int i = 0; i < 15; i++) {  // 15 perechi (0-14, 1-15)
        if(prime[i] * prime[i+1] == n) {
            return 1;
        }
        if(prime[i] * prime[i+1] > n) {
            break;  // am depășit n
        }
    }
    return 0;
}

---

Problema 5: Subprogramul DNPT – Divizori Neprimi Pozitivi Impari

Cerința: Afișează toți divizorii impari ai lui n care NU sunt numere prime.

Soluție:

int estePrim(int numar) {
    if(numar < 2) return 0;
    if(numar == 2) return 1;
    if(numar % 2 == 0) return 0;

    for(int d = 3; d * d <= numar; d += 2) {
        if(numar % d == 0) return 0;
    }
    return 1;
}

void DNPT(int n) {
    // Parcurgem toți divizorii impari
    for(int d = 1; d <= n; d += 2) {  // d += 2 pentru numere impare
        if(n % d == 0) {  // d este divizor
            if(!estePrim(d)) {  // d NU este prim
                cout << d << " ";
            }
        }
    }
}

Pentru n=90: Divizorii impari: 1, 3, 5, 9, 15, 45

• 1: nu e prim ✓
• 3: e prim ✗
• 5: e prim ✗
• 9: nu e prim ✓
• 15: nu e prim ✓
• 45: nu e prim ✓
  → Afișează: 1 9 15 45

---

Problema 6: Subprogramul schimb – Înlocuirea unei cifre

Cerința: Înlocuiește cifra de pe poziția p cu cifra x.

Soluție:

void schimb(int &n, int x, int p) {
    int putere = 1;

    // Ridică 10 la puterea p
    for(int i = 0; i < p; i++) {
        putere = putere * 10;
    }

    // Separăm numărul în trei părți:
    // partea din stânga cifrei + cifra nouă + partea din dreapta
    int parteaDreapta = n % putere;
    int cifraVeche = (n / putere) % 10;
    int parteaStanga = n / (putere * 10);

    // Reconstruim numărul cu cifra nouă
    n = parteaStanga * putere * 10 + x * putere + parteaDreapta;
}

Alternativă mai clară:

void schimb(int &n, int x, int p) {
    char sir[12];
    sprintf(sir, "%d", n);  // transformă numărul în șir

    int lungime = strlen(sir);
    if(p < lungime) {
        // Poziția p în șir este de la stânga, dar în problemă e de la dreapta
        // Deci: poziția în șir = lungime - 1 - p
        sir[lungime - 1 - p] = '0' + x;  // transformă cifra în caracter
        n = atoi(sir);  // transformă înapoi în număr
    }
}

---

Problema 7: Subprogramul harsad – Numere Harsad/Niven

Cerința: Găsește cel mai mare număr ≤ k care este divizibil cu suma cifrelor sale.

Soluție:

int sumaCifre(int numar) {
    int suma = 0;
    while(numar > 0) {
        suma = suma + numar % 10;
        numar = numar / 10;
    }
    return suma;
}

void harsad(int k, int &n) {
    n = k;  // începem de la k și coborâm

    while(n > 0) {
        int suma = sumaCifre(n);
        if(suma > 0 && n % suma == 0) {
            return;  // am găsit număr harsad
        }
        n--;  // încercăm următorul număr mai mic
    }

    n = 1;  // dacă nu găsim nimic, 1 este harsad (1 % 1 = 0)
}

---

Problema 8: Subprogramul fulg – Aglomerări de Fulgi

Cerința: Verifică dacă un număr reprezintă o aglomerare validă de fulgi.

Condiții din text:

1. Are 9 cifre
2. Conține doar cifrele 1,2,3,4
3. Conține cel puțin o dată fiecare cifră 1,2,3,4

Soluție:

int fulg(long long n) {
    if(n < 111111111 || n > 444444444) return 0;  // are 9 cifre, între 1..4

    int frecventa[10] = {0};  // frecvența cifrelor 0-9
    int nrCifre = 0;

    while(n > 0) {
        int cifra = n % 10;
        if(cifra < 1 || cifra > 4) return 0;  // cifră invalidă
        frecventa[cifra]++;
        nrCifre++;
        n = n / 10;
    }

    if(nrCifre != 9) return 0;  // nu are exact 9 cifre

    // Verificăm dacă avem cel puțin o dată fiecare cifră 1,2,3,4
    if(frecventa[1] > 0 && frecventa[2] > 0 && 
       frecventa[3] > 0 && frecventa[4] > 0) {
        return 1;
    }

    return 0;
}

---

Problema 9: Subprogramul NrTmp – Numere cu 3 Divizori Impari

Cerința: Numără câte numere din [x,y] au exact 3 divizori pozitivi impari.

Observație: Un număr are 3 divizori impari dacă este de forma p² unde p este prim impar.

Soluție:

int prim(int numar) {
    if(numar < 2) return 0;
    if(numar == 2) return 1;
    if(numar % 2 == 0) return 0;

    for(int d = 3; d * d <= numar; d += 2) {
        if(numar % d == 0) return 0;
    }
    return 1;
}

void NrTmp(int x, int y, int &nr) {
    nr = 0;

    // Parcurgem pătratele numerelor prime impare
    for(int p = 3; p * p <= y; p += 2) {
        if(prim(p)) {
            int patrat = p * p;
            if(patrat >= x && patrat <= y) {
                nr++;
            }
        }
    }

    // Verificăm și pătratele de 2 (adică 4) dacă e în interval
    if(x <= 4 && 4 <= y) {
        nr++;  // 4 are divizorii impari: 1, (nu are alții) - ATENȚIE! 4 are doar 1 divizor impar!
        // Corect: 4 are divizorii: 1, 2, 4 → doar 1 este impar → deci nu se numără!
    }
}

Corectare: Problema spune “cu trei divizori pozitivi impari”. Pătratul unui prim impar p² are divizorii: 1, p, p² → toți 3 sunt impari dacă p este impar.

---

🎯 Sfaturi Pentru Subprograme la Bacalaureat

1. Numele subprogramului trebuie să fie exact cum e în cerință
2. Parametrii trebuie să aibă exact tipul și modul de transmitere specificat

• int &n = transmitere prin referință (se modifică)
• int n = transmitere prin valoare (nu se modifică)

1. Folosește funcții auxiliare dacă e nevoie (ex: prim(), sumaCifre())
2. Comentează dacă algoritmul e complex
3. Testează cu datele din exemplu

💪 Exercițiu de Practică

Încearcă să scrii singur următorul subprogram:

Cerință: Scrie subprogramul oglindit care primește un număr n și returnează oglinditul său.
Exemplu: pentru n=1234, returnează 4321.

Soluție:

int oglindit(int n) {
    int ogl = 0;
    while(n > 0) {
        ogl = ogl * 10 + n % 10;
        n = n / 10;
    }
    return ogl;
}

✨ Motivare Finală

Uite cât de multe subprograme ai învățat să scrii! Fiecare problemă rezolvată este o unealtă nouă în “cutia ta de instrumente” de programator.

La examen, ai timp suficient să scrii cod corect și elegant. Important este să:

1. Înțelegi cerința
2. Gândești algoritmul
3. Scrii pas cu pas
4. Verifici cu exemplul

Ești gata să iei 10 pe 10 la subprograme! 🚀