SISergiu Ilincameditații informatică
Meniu

clasa a XI-a · Recapitulare · lecția 14

Recapitulare Bac: subprograme, recursivitate, backtracking, grafuri, arbori

60 minmate-info (Bac)

Înainte de lecția asta: XI.2 Subprograme (2): parametri prin referință și subprograme cu tablouri, XI.4 Recursivitate (2): pe vectori, pe șiruri și algoritmul de umplere (fill), XI.8 Backtracking (3): partiții, plata unei sume, paranteze și backtracking în plan, XI.13 Arbori: definiție, arbori cu rădăcină, vectorul de tați

Ce vei ști după lecție

  • Rezolvi grile de Subiectul I pe toată materia clasei a XI-a.
  • Scrii corect, din prima, un subprogram de tip III.1.
  • Ai o fișă de formule pentru grafuri și arbori.

Lecția are și o fișă de lucru, de rezolvat după ce o citești. Mergi la fișă ↓

Clasa a XI-aLecția 14 din 21 · mai sunt 7Urmează: XI.15 · Metoda GreedyVezi toate lecțiile
Cuprins

Fișiere PDF și de lucru

1. Harta clasei a XI-a

Harta

Temă Ce trebuie să știi pe de rost
subprograme antet, parametri valoare vs referință (&), valoare returnată vs void
recursivitate caz de bază + pas; ordinea afișării (înainte/după apel); trace pe stivă
divide et impera împărțire în jumătăți, T(n) = 2T(n/2) + O(n), Hanoi: 2ⁿ − 1 mutări
backtracking x[k], valid(k), soluție la k == n; permutări n!, aranjamente, combinări, produs cartezian
grafuri neorientate Σ grade = 2m; n(n−1)/2; conex ≥ n − 1; (n−1)(n−2)/2 pentru neconex; eulerian = conex + grade pare
grafuri orientate Σ d⁺ = Σ d⁻ = m; ≤ n(n−1) arce; tare conex ≥ n arce
arbori n − 1 muchii; vector de tați (rădăcina = 0); nivel, înălțime; frunză = nu apare în t

2. Fișa de formule

Noțiune Formulă / proprietate
graf neorientat, n vârfuri max n(n−1)/2 muchii; Σ grade = 2m
grafuri neorientate distincte cu n vârfuri 2^(n(n−1)/2)
graf conex ≥ n − 1 muchii
p componente conexe ≥ n − p muchii; p − 1 muchii de adăugat pentru conexitate
neconex, număr maxim de muchii (n−1)(n−2)/2
graf complet Kₙ n(n−1)/2 muchii; fiecare vârf are gradul n − 1
graf parțial 2ᵐ grafuri parțiale (inclusiv el însuși)
eulerian conex + toate gradele pare
hamiltonian ciclu prin toate vârfurile; Kₙ este hamiltonian
bipartit fără cicluri impare; Kₚ,q are p · q muchii
graf orientat max n(n−1) arce; Σ d⁺ = Σ d⁻ = m
arbore n − 1 muchii; ≥ 2 frunze; f = 2 + Σ(d − 2) pe vârfurile cu d ≥ 3
combinatorică nᵏ (produs cartezian), Aₙᵏ = n!/(n−k)!, Cₙᵏ = n!/(k!(n−k)!), 2ⁿ submulțimi
Hanoi 2ⁿ − 1 mutări

3. Cum rezolvi o grilă de cod recursiv

Pentru orice grilă cu f(n) recursiv: nu încerca să „vezi” rezultatul. Scrie un tabel de apeluri:

void p(int n)
{
    if (n > 0) { p(n - 1); cout << n; p(n - 2); }
}

Pentru p(3): apelul p(3) face în ordine p(2), afișează 3, p(1).

Apel Ce face în ordine
p(3) p(2) → 3 → p(1)
p(2) p(1) → 2 → p(0)
p(1) p(0) → 1 → p(-1)
p(0), p(-1) nu fac nimic

Rezultat: p(2) dă 1 2, deci p(3) dă 1 2 3 1. Pentru p(4): p(3) + 4 + p(2) = 1 2 3 1 4 1 2 → 1231412.

4. Grile de antrenament (10 din prima parte)

Fă-le pe hârtie, cronometrează-te (cca. 90 de secunde pe grilă). Răspunsurile cu explicații sunt la final.

G1. Se consideră subprogramul:

int f(int n) { if (n < 10) return n; return f(n / 10) + n % 10; }

Valoarea lui f(2025) este: a) 9 b) 2025 c) 5 d) 7

G2. Ce se afișează la apelul p(4) din secțiunea 3? a) 1231412 b) 1213412 c) 12314121 d) 1234123

G3. Utilizând metoda backtracking se generează toate submulțimile cu 3 elemente ale mulțimii {1, 2, 3, 4, 5}, în ordine lexicografică. A cincea soluție generată este: a) {1,3,5} b) {1,4,5} c) {1,3,4} d) {2,3,4}

G4. Un graf neorientat are 8 vârfuri și 4 componente conexe. Numărul maxim de muchii este: a) 10 b) 6 c) 4 d) 12

G5. Un arbore cu rădăcină are vectorul de tați (4, 4, 0, 3, 3, 1, 1). Numărul de frunze este: a) 3 b) 4 c) 2 d) 5

G6. Un graf orientat are 6 vârfuri. Numărul maxim de arce (fără bucle) este: a) 15 b) 30 c) 36 d) 12

G7. Câte cicluri elementare distincte de lungime 3 are graful complet K₄? a) 4 b) 3 c) 12 d) 24

G8. Se consideră:

int g(int x) { if (x == 0) return 0; return x % 2 + g(x / 2); }

Valoarea lui g(37) este: a) 2 b) 3 c) 4 d) 5

G9. Se generează toate numerele cu 3 cifre distincte formate din cifrele 2, 4, 6, în ordine crescătoare. Al patrulea număr generat este: a) 426 b) 462 c) 264 d) 624

G10. Un graf neorientat are 7 vârfuri și muchiile [1,2], [2,3], [4,5], [5,6], [6,7]. Numărul minim de muchii de adăugat pentru a deveni conex este: a) 1 b) 2 c) 0 d) 3

5. Grile de antrenament (10 din partea a doua)

G11. Un graf conex are 10 vârfuri și 14 muchii. Câte muchii trebuie eliminate, cel puțin, pentru a obține un arbore? a) 4 b) 5 c) 6 d) 9

G12. Care este numărul de mutări necesare pentru problema turnurilor din Hanoi cu 6 discuri? a) 31 b) 36 c) 63 d) 64

G13. Arborele cu vectorul de tați (0, 1, 1, 2, 3, 3, 5) are înălțimea: a) 2 b) 3 c) 4 d) 7

G14. Se consideră:

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

Valoarea lui h(48, 18) este: a) 3 b) 6 c) 12 d) 18

G15. Ce afișează q(1203) dacă subprogramul este:

void q(int n) { if (n > 0) { cout << n % 10; q(n / 10); } }

a) 1203 b) 3021 c) 3012 d) 321

G16. Pe câte moduri se pot așeza 5 elevi pe 3 locuri, ținând cont de ordine? a) 10 b) 15 c) 60 d) 125

G17. Câte șiruri de lungime 4 din literele {a, b, c} nu au două litere consecutive egale? a) 12 b) 24 c) 36 d) 81

G18. Care dintre grafurile următoare este bipartit? a) C₅ (ciclu cu 5 vârfuri) b) C₆ (ciclu cu 6 vârfuri) c) K₃ d) K₄

G19. Un graf neorientat conex are gradele 3, 3, 2, 2, 2, 2. Care afirmație este adevărată? a) este eulerian b) are lanț eulerian, dar nu are ciclu eulerian c) nu are lanț eulerian d) nu există un astfel de graf

G20. Un graf orientat cu 5 vârfuri are 8 arce. Suma gradelor interioare plus suma gradelor exterioare este: a) 8 b) 16 c) 40 d) 20

6. Două subiecte model (III.1 și arbori)

III.1: subprogram

Scrieți definiția completă a subprogramului cmax care primește prin parametrul n un număr natural (cu cel mult 9 cifre) și returnează cea mai mare cifră pară a lui n, sau valoarea −1 dacă n nu are cifre pare.

Gândește-te: parcurgi cifrele cu % 10 și / 10, reții maximul (inițial −1), tratezi doar cifrele pare.

#include <iostream>
using namespace std;

int cmax(int n)
{
    int mx = -1;
    do
    {
        int c = n % 10;
        if (c % 2 == 0 && c > mx) mx = c;
        n /= 10;
    } while (n > 0);              // do-while: 0 are o cifră (par)
    return mx;
}

int main()
{
    int n;
    cin >> n;
    cout << cmax(n);
    return 0;
}

De ce așa?

De ce do … while și nu while (n > 0)? Pentru n = 0, while nu ar intra deloc și am întoarce −1, deși 0 este cifră pară. do-while execută măcar o dată. De ce mx = −1 la început? Este exact valoarea cerută dacă nu găsim nicio cifră pară; orice cifră pară (≥ 0) o va depăși.

Arbori: nodurile de pe ultimul nivel

Se citește un arbore cu rădăcină prin vectorul de tați. Afișați nodurile aflate pe nivelul cel mai mare (cel mai departe de rădăcină), în ordine crescătoare.

#include <iostream>
using namespace std;

int t[101], niv[101], n;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> t[i];
    int mx = 0;
    for (int i = 1; i <= n; i++)
    {
        int y = i;
        while (t[y] != 0) { y = t[y]; niv[i]++; }
        if (niv[i] > mx) mx = niv[i];
    }
    for (int i = 1; i <= n; i++)
        if (niv[i] == mx) cout << i << ' ';
    return 0;
}

De ce așa?

De ce două parcurgeri? Mai întâi aflăm nivelul maxim (nu-l știm înainte), apoi afișăm toate nodurile care îl ating. Într-o singură trecere nu am ști ce să afișăm.

7. Greșeli frecvente

Atenție — greșeli frecvente

  • Recursivitate fără caz de bază sau cu caz de bază greșit (n == 0 vs. n < 10).
  • Confuzia „graf parțial” (scot muchii) vs. „subgraf” (scot vârfuri).
  • Confuzia „hamiltonian” (toate vârfurile) vs. „eulerian” (toate muchiile).
  • La backtracking: soluțiile sunt generate în ordine lexicografică (în ordinea în care bucla încearcă valorile).
  • La vectorul de tați: rădăcina este vârful cu valoarea 0, nu vârful 1.
  • La parametri: fără &, modificarea nu se vede în funcția apelantă.

8. Checklist pentru III.1 (subprogram)

  • antetul exact: nume, tip returnat, parametri în ordinea din enunț;
  • parametrii de ieșire prin referință (&), dacă rezultatul „se furnizează prin parametru”;
  • nu citesc și nu afișez nimic în subprogram (dacă nu se cere);
  • variabilele locale sunt inițializate;
  • am tratat cazurile speciale din enunț (de exemplu „dacă nu există, se returnează −1”);
  • am verificat pe exemplul din enunț, de mână, inclusiv pe n = 0 și pe un caz limită.

9. La BAC

La BAC

Subiectul I (30 de puncte) are 6 grile, de obicei: 1 de logică/pseudocod, 1 de subprograme/recursivitate, 1 de backtracking, 2 de grafuri/arbori, 1 de vector de tați sau numărare. Subiectul II are 3 cerințe (o problemă de matrice/șiruri și două pe structuri); Subiectul III: un subprogram (III.1) și un program (III.2), de obicei pe șiruri, matrice sau fișiere. Strategia: începi cu grilele sigure, sari peste cele cu desen mare, revii la final.

10. Exersează pe hârtie

1. Fă un plan de recapitulare: scrie pentru fiecare temă din secțiunea 1 un exemplu mic (cinci rânduri) pe care îl poți rezolva fără carte.

2. Alege două subiecte oficiale de Bac din ultimii ani și rezolvă doar Subiectul I, cronometrat (maxim 30 de minute).

3. Scrie, pe fișa de formule, câte o grilă „tip” pentru fiecare formulă din secțiunea 2 (ex.: „graf cu 8 vârfuri și 5 componente, număr maxim de muchii”).

4. Scrie un program care citește un arbore prin muchii și rădăcină și afișează frunzele (lecția XI.13).

5. Scrie un program care citește un graf și afișează componentele conexe, fiecare pe un rând (lecția XI.11).

Rezumat

  • Harta temelor: subprograme, recursivitate, D&I, backtracking, grafuri, arbori.
  • Metoda pentru grile de cod: tabel de apeluri sau trace; nu „ghici” rezultatul.
  • Formulele de grafuri și arbori se memorează cu exemple mici (n = 4, 5).
  • Subprogramele: antet exact, cazuri limită (n = 0), do-while când 0 contează.

Fișa de lucru

Ai citit lecția? Printează fișa sau deschide-o pe ecran și rezolvă exercițiile în ordine.

Fișă de lucru · 6 pagini · 120 min

Recapitulare BAC de clasa a XI-a

  • Urmărești pe hârtie, fără greșeli, subprograme cu parametri prin referință, recursivitate și backtracking.
  • Rezolvi itemii de grafuri și arbori din Subiectul I cu formule și cu un desen mic.
  • Legi temele între ele: backtracking pe grafuri, recursivitate pe arbori, subprograme de tip III.1.

Te-ai blocat la un exercițiu?

Probleme de lucru

Începe cu acestea, în ordine. Problemele se deschid pe pbinfo.ro, unde trimiți soluția și primești punctajul.

  • nrprime2#2838

    III.1 de Bac.

    ușoară
  • triplete#2811

    III.1 de Bac.

    medie
  • gradk#4060

    ușoară

Temă

Rezolvă-le singur și bifează ce ai terminat. Bifele rămân salvate în acest browser.

  • divimpar#2830

    ușoară
  • fiboimpar#2836

    ușoară
  • b-egal#3104

    ușoară
  • plus1#4881

    ușoară
  • identice4#2817

    medie
  • ciclul#4071

    ușoară

Grile din subiectele de BAC

Exerciții de tip grilă din variantele de Bacalaureat. Se rezolvă pe pbinfo.ro, care îți verifică imediat răspunsul.

Citește și exersează în plus

Te-ai blocat la lecția asta?

Scrie-mi ce nu iese și vedem împreună de unde se blochează.

Răspunsuri

Grilele de antrenament

G1. a (9): 2 + 0 + 2 + 5 = 9.

G2. a (1231412): vezi tabelul din secțiunea 3.

G3. a, {1,3,5}: 123, 124, 125, 134, 135.

G4. a (10): fie trei vârfuri izolate și o componentă completă cu 5 vârfuri: 5·4/2 = 10.

G5. b (4): apar ca tați 4, 3, 1; frunze: 2, 5, 6, 7.

G6. b (30): 6 · 5.

G7. a (4): triunghiurile determinate de câte 3 vârfuri: C(4,3) = 4.

G8. b (3): 37 = 100101₂ are trei cifre 1.

G9. b (462): 246, 264, 426, 462, 624, 642.

G10. a (1): componentele sunt {1,2,3} și {4,5,6,7}; pentru două componente este suficientă o muchie.

G11. b (5): un arbore are 9 muchii, 14 − 9 = 5.

G12. c (63): 2⁶ − 1.

G13. b (3): 7 → 5 → 3 → 1; înălțimea este 3.

G14. b (6): h(48,18) = h(18,12) = h(12,6) = h(6,0) = 6.

G15. b (3021): afișează ultima cifră a lui 1203, apoi pe a lui 120, 12, 1 (de la coadă spre cap).

G16. c (60): A(5,3) = 5·4·3.

G17. b (24): 3 alegeri pentru prima literă, apoi câte 2 pentru fiecare următoare: 3·2·2·2 = 24.

G18. b (C₆): ciclurile de lungime pară se pot colora cu 2 culori; C₅ și K₃, K₄ au cicluri impare.

G19. b: suma gradelor 14 este pară, deci graful există; exact două vârfuri au grad impar, deci are lanț eulerian (între cele două vârfuri de grad 3), dar nu ciclu.

G20. b (16): Σ d⁺ = Σ d⁻ = 8, deci 8 + 8 = 16.

Subiectele model

Rezolvările sunt în codurile din secțiunea 6 (au fost verificate pe teste, inclusiv n = 0).

Exersează pe hârtie

1–3. Răspuns personal; verifică-te cu fișa de formule și cu lecțiile XI.1–XI.13.

4. Folosește DFS din rădăcină pentru a construi t[], apoi afișează vârfurile care nu apar ca valori în t (XI.13, secțiunea 4).

5. O parcurgere (DFS) din fiecare vârf nevizitat; afișezi vârfurile găsite, apoi '\n' (XI.11, secțiunea 5).