Ghid Redactare BAC

Ghidul de Redactare BAC are mai multe scopuri, printre care se numără evitarea greșelilor și creșterea șanselor unei note mari. În primul rand, daca nu respecți anumite standarde de redactare și ai norocul ca profesorul supraveghetor să observe acest lucru, lucrarea îți poate fi anulată, iar tu vei fi nevoit să o rescrii. În cazul și mai rău, dacă nu observă nimeni la momentul potrivit, poți fi eliminat din probă pe motiv de semn pe lucrare. De asemenea, munca profesorului corector ar trebui să fie cât mai simplă, acesta să înțeleagă lesne conținutul lucrării, pentru a evita eventualele dubii. Adoptând o redactare potrivită îți poți crește șansele de a obține o notă mai bună!

Informațiile din acest document se pot modifica de la sesiune la sesiune. Trebuie mereu să fii atent la instrucțiunile supraveghetorului. Nu ezita să pui întrebări dacă ai nelămuriri!


Aici este un exemplu de redactare.

Informații generale

  1. Lucrarea trebuie scrisă cu cerneală albastră.

  2. Nuanța cernelii nu ar trebui să varieze. Dacă știi că vei rămâne fără cerneală schimb-o din timp ca scrisul să nu se deschidă la culoare.

  3. Dacă trebuie să realizezi desene folosește rigla și creionul negru. La proba de informatică, acest lucru nu este necesar.

  4. Nu face semne distinctive.

Tipul Foilor de Examen

Foile de examen sunt de 2 tipuri:

  1. Foaie de Tip 1 - aceasta are prima pagină distinctivă. Totodată aici se vor completa informațiile cu privire la probă și la candidat. Fiecare parrticipant va avea în lucrarea finală o singură foaie de Tip 1.

  2. Foaie de Tip 2 - aceasta este destinată integral rezolvării subiectelor, având în componența sa și un colț cu inforațiile despre candidat. Candidații pot avea mai multe foi de Tip 2.

Prima Pagină

Prima pagină conține mai multe informații care au un caracter organizatoric. Acestea sunt folosite pentru a identifica proba la care participi, dar și pentru a te identifica ulterior, odata ce lucrarea a fost corectată, pe tine. Toate câmpurile de pe prima pagină trebuiesc completate cu majuscule.

Colțul securizat

Colțul securizat este folosit pentru identificarea candidatului. Odată ce datele personale sunt completate, iar profesorii supraveghetori și-au pus semnătura în câmpurile destinate, colțul va fi securizat de către unul dintre supraveghetori.

Câmpurile care trebuiesc completate

  1. Numele - acesta este numele tău de familie.

    Exemplu 
    POPESCU
  2. Inițiala prenumelui tatălui - aici trebuie completată inițiala tatălui tău. Dacă are mai multe, se vor pune toate, urmate de câte un punct fiecare.

    Exemplu 
    C.A.
  3. Prenumele - acesta este prenumele tău. Dacă ai mai multe trebuie să le treci pe toate, în ordinea în care apar în buletin.

    Exemplu 
    MĂDĂLIN COSTEL
  4. Școala de proveniență - liceul pe care l-ai făcut.

    Exemplu 
    COLEGIUL NAȚIONAL DE INFORMATICĂ „TUDOR VIANU”
  5. Centrul de examen - centrul la care dai examenul.

    Exemplu 
    COLEGIUL NAȚIONAL DE INFORMATICĂ „TUDOR VIANU”
  6. Localitate și județ - localitatea și județul centrului de examen.

    Exemplu 
    Loc. BUCUREȘTI   jud. SECTOR 1
  7. Nume și prenume asistent - aici vei scrie numele si prenumele profesorilor supraveghetori. Aceștia în mod normal ar trebui să își scrie numele pe tabla din sala de examen. Dacă nu sunt scrise, roagă-i să își scrie numele pentru a evita greșelile. Înainte de securizarea colțului, supraveghetorii sunt obligați să se semneze.

    Exemplu 
    GABRIEL LORENA  | *semnatură*
IONESCU TOMA    | *semnatură*

Informații utile

  1. Ai grijă să nu scrii peste eticheta cu ajutorul căreia a fost lipit colțul

  2. Ai grijă să ai suficient spațiu peste care să se lipescă colțul. Recomandăm, dacă ceri o foaie de examen de Tipul 2, colțul să îți fie lipit înaonte de a te apuca să scrii pe aceasta, ca să fii sigur că scrisul nu îți va fi acoperit de etichetă.

  3. Dacă s-a întamplat să greșești nu te panica. Mai cere o foaie.

Câmp pagini scrise

Acest câmp va fi completat la finalul probei, atunci când vei preda lucrarea. Aici vei nota împreună cu supraveghetorul numărul total de pagini pe care l-ai scris. Acesta conține doar numărul de pagini din lucrarea finală. Prima pagină se numără întotdeauna, urmată de toate celelalte pagini scrise.

De asemenea, la finalul probei, împreună cu profesorul coordonator, vei nota pe fiecare pagină numărul acesteia, așa cum îți va fi indicat.

Câmp Probă Scrisă

Acest câmp va fi completat la începutul probei. Informațiile ce vor fi completate ar trebui să fie scrise de profesorii supraveghetori pe tabla din clasă. Acestea diferă de la probă la probă și de la sesiune la sesiune.

La acest cămp contează inclusiv rândul pe care scrii. Așteaptă instrucțiunile profesorilor sau ale comisiei.

Câmpurile care trebuiesc completate

  1. Pentru *) - titlul examenului la care participi.

    Exemplu

    Pentru *) EXAMENUL NAȚIONAL
DE BACALAUREAT

  2. Disciplina - titlul disciplinei. Acesta este trecută și pe foaia cu subiectele.

    Exemplu

    Disciplina INFORMATICĂ
LIMBAJUL C/C++

  3. Sesiunea - titlul sesiunii la care participi.

    Exemplu

    Sesiunea IUNIE-IULIE 2023

Partea inferioară a primei pagini

Dacă foaia este de Tip 1, aici nu se va completa nimic. Prima pagină este destinată doar completării de informații ce nu au legătură cu rezolvarea subiectelor. Dacă foaia este de Tip 2, aici se va completa colțul securizat și se va continua rezolvarea subiectelor în mod normal.

Pagini pentru rezolvare

Acestea sunt paginile destinate rezolvării subiectelor.

Subiectul I

Numărul exercițiului va fi urmat de litera corespunzătoare răspunsului corect.

Exemplu

Subiectul I

  1. a
  2. c
  ...

Subiectul al II-lea

Numărul exercițiului va fi urmat de rezolvarea corespunzătoare.

Exemplu

Subiectul al II-lea

  1. a. 9752

     b. 975 și 987

     c. citește x (număr natural)
        p <- 1
        ...

     d. #include <iostream>
        using namespace std;

        int main() {

        }
        ...

  2. A șasea soluție generată este (mere, prune, caise).

  3. struct lalea {
        int pret;
     }
     ...

Formularea răspunsului

Nu este necesară formularea în enunț, însa, dacă cerința necesită o formulare specifică, aceasta ar trebui respectată. Este bine ca răspunsul să fie ușor de înțeles.

Pseudocod

La pseudocod este foarte importantă spațierea și respectarea modelului de pe subiect. Nu este necesară trasarea liniilor ce marchează blocurile logice, însă dacă dorești să o faci, nu hașura pătrățelul de la finalul instrucțiunii, deoarece ar putea fi considerat semn. Evită să scrii lângă colțul securizat, deoarece îți va afecta așezarea în pagină. Recomandăm să ignori spațiul de lângă colțul securizat atunci când scrii pseudocod.

Exemplu

┌ dacă c > m atunci
|    m <- c; p <- p * 10
| altfel
|    x <- [x / (p * 10)] * p + p % 10
┕▢
...

sau 

dacă c > m atunci
    m <- c; p <- p * 10 
altfel
    x <- [x / (p * 10)] * p + p % 10
...

Cod C++

La scrierea codului C++ este bine să respecți o spațiere adecvată, pentru lizibilitatea codului. Evită să scrii lângă colțul securizat, deoarece îți va afecta așezarea în pagină. Recomandăm să ignori spațiul de lângă colțul securizat atunci când scrii cod C++.

Subiectul al III-lea

Numărul exercițiului va fi urmat de rezolvarea corespunzătoare.

Exemplu

Subiectul al III-lea

  1. void abundent(int n) {

     }
     ...

  2. #include <iostream>
     using namespace std;

     int main() {

     }
     ...

  3. #include <iostream>
     using namespace std;

     int main() {

     }
     ...

Cod C++

La scrierea codului C++ este bine să respecți o spațiere adecvată, pentru lizibilitatea codului. Evită să scrii lângă colțul securizat, deoarece îți va afecta așezarea în pagină. Recomandăm să ignori spațiul de lângă colțul securizat atunci când scrii cod C++.

Informații utile

  1. Lasă cate 1-2 degete spațiu pe dreapta și pe stânga paginilor. Foile vor fi capsate la finalul probei și dacă ai scris de pe margine îți va fi acoperit scrisul.

  2. Nu scrie până jos de tot. Pe fiecare pagină va trebui să îi treci numărul, în colțul din dreapta jos. Notarea o vei face alături de profesorul coordonator când vei preda foaia.

  3. Începe rezolvarea exercițiilor de pe același rând pe care ai notat numărul exercițiului.

  4. Dacă ai greșit, taie cu o singură linie orizontală. Orice altceva este considerat semn.

  5. Nu ai voie să faci săgeți cu adăugări. Dacă ai uitat să scrii ceva în mijlocul paginii va trebui să tai sau să rescrii foaia.

  6. Este mai sigur ca atunci când scrii cod C++ sau pseudocod să lași spațiul de lângă colțul securizabil liber. Acesta va fi marcat la final cu un Z de către unul dintre supraveghetori ca fiind spațiu nefolosit.

  7. Folosește același tip de cerneală și schimb-o din timp pentru ca nuanța acesteia să nu varieze.



Aici este un exemplu de redactare.

Pseudocod

Pseudocodul apare de obicei la Subiectul al II-lea. Acesta conține structurile specifice unui limbaj de programare, dar este destinat citirii de către oameni. Acesta are mai multe concepte precum:

  • variabile și constante
  • operații
  • instrucțiuni
  • expresii

Variabile și constante

Variabilele nu sunt declarate ca in C++. Ele sunt declarate atunci când li se dă pentru prima oară o valoare. Acestea au nume formate din litere, cifre, underscore, dar nu încep cu cifră.

Pot apărea constante matematice, cum ar fi π.

Operații

Operații matematice

  • adunarea: a + b
  • scăderea: a - b
  • înmulțirea: a * b
  • împărțirea: a / b. Rezultatul se consideră număr real.
  • câtul împărțirii: [a / b]. Rezultatul este partea întreagă a împărțirii.
  • restul împărțirii: a % b

Operații logice

Acestea returnează Adevărat sau Fals.

  • egalitatea: =
  • inegalitate: ≠
  • mai mic: <
  • mai mic sau egal: ≤
  • mai mare: >
  • mai mare sau egal: ≥

Instrucțiuni

Instrucțiunile sunt componente ale algoritmului care au efect atunci când sunt executate. Acestea se scriu de regulă pe câte o linie. Cu toate acestea, există cazuri când sunt scrise mai mult pe aceeași linie, însă separate prin ;.

Citirea

Aceasta se realizează fololsind instrucțiunea citește urmată de numele variabilelor, separate prin virgulă.

Exemplu

citește a, b, c

Afișarea

Aceasta se realizează folosind instrucțiunea scrie urmată de un șir, numele variabilelor sau expresii, separate prin virgulă.

Exemplu

scrie "a - b = ", a - b

Atribuirea

Aceasta se realizează folosind instrucțiunea ← precedată de variabilă si urmată de o expresie. Variabila va lua valoarea expresiei.

Exemplu

a ← 1
sum ← a + 2
i ← i + 1

Condiția / Structura alternativă

Condiția evaluează expresia logică. Dacă aceasta este adevărată se execută instrucțiunile ce apar după atunci. Dacă este falsă, trece mai departe. Dacă există instrucțiunea altfel și condiția este falsă, se vor executa instrucțiunile ce apar dupa altfel.

Sintaxă

daca <expresie logica> atunci
    ...

sau

daca <expresie logica> atunci
    ...
altfel
    ...

Structuri repetitive

Structuri repetitive cu test inițial

  • Instrucțiunea pentru <variabila> ← <expresie initiala>, <conditie>, <pas> executa ...

    variabila pornește de la valoarea expresie initiala și se schimbă conform pas, cât timp conditie este Adevărată. Dacă conditie este Adevărată, se vor rula instrucțiunile aflate după executa, altfel programul trece mai departe de structura repetitivă. Dacă pas nu există, se va considera 1.

    Exemplu

    pentru i ← 1, i ≤ n, i ← i + 1 executa
    ...

    echivalent cu

    pentru i ← 1, i ≤ n executa
    ...

    echivalent cu

    pentru i ← 1, n executa
    ...

  • Instrucțiunea cat timp <conditie> executa ...

    Cât timp conditie este Adevărată, se vor rula instrucțiunile aflate dupa executa. Când nu mai este Adevărată, programul trece mai departe.

    Exemplu - Determinarea numărului de cifre pare dintr-un număr

    citeste n
num ← 0

cat timp n ≠ 0 executa
    daca n % 2 = 0 atunci
        num ← num + 1
    n ← [n / 10]

scrie num

Structuri repetitive cu test final

  • Instrucțiunea executa ... cat timp <conditie>

    Se execută o data instrucțiunile. Apoi, dacă conditie este Adevărată se continuă execuția. Când nu mai este Adevărată, programul trece mai departe.

    Important Instrucțiunile care se află după execută, vor fi mereu executate cel puțin o data. Condiția este verificată prima oară pentru pasul 2, de unde și numele tipului de structură.

    Sintaxă

    executa
    <instructiuni>
cat timp <conditie>

    Exemplu - Numărul de cifre al unui număr întreg

    citeste n
num ← 0

executa
    num ← num + 1
    n ← [n / 10]
cat timp n ≠ 0

scrie num

  • Instrucțiunea repeta ... pana cand <conditie>

    Se execută o data instrucțiunile. Apoi, dacă conditie este Falsă se continuă execuția. Când conditie este Adevărată, programul trece mai departe.

    Important Instrucțiunile care se află după execută, vor fi mereu executate cel puțin o data. Condiția este verificată prima oară pentru pasul 2, de unde și numele tipului de structură.

    Sintaxă

    repeta
    <instructiuni>
pana cand <conditie>

    Exemplu - Numărul de cifre al unui număr întreg

    citeste n
num ← 0

repeta
    num ← num + 1
    n ← [n / 10]
pana cand n = 0

scrie num

Divizibilitate

Divizorii unui număr

Un prim algoritm banal este verificarea tuturor numerelor până la n.

Implementare

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    for (int d = 1; d <= n; d++) {
        if(n % d == 0) {
            cout << d << " ";
        }
    }

    return 0;
}

O variantă mai eficientă este să verificăm toate numerele până la radicalul numărului n și să le grupăm pe perechi. Pentru numărul 12 vom avea următoarele cazuri:

  • 1 face pereche cu 12
  • 2 face pereche cu 6
  • 3 face pereche cu 4
  • 4 * 4 > 12, deci ne oprim

Implementare

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    for (int d = 1; d * d <= n; d++)
        if(n % d == 0) {
            cout << d << " ";

            if(d * d < n) {
                cout << n / d << " ";
            }     
        }

    return 0;
}

Se observă că am evitat folosirea funției sqrt(n), care poate fi ineficientă și inexactă, folosind condiția d * d <= n, care se poate traduce prin d <= sqrt(n).

Algoritmul lui Euclid

Algoritmul lui Euclid ne ajută să determinăm CMMDC-ul dintre 2 numere. Acesta are la bază ideea că CMMDC-ul dintre 2 numere divide și restul împărțirii acestora.

Implementare

#include <iostream>
using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;

    while(b != 0)
    {
        int r = a % b;
        a = b;
        b = r;
    }
    cout << a;

    return 0;
}

Dacă cunoastem CMMDC-ul unui număr, îi putem afla imediat și CMMMC-ul, cu ajutorul formulei (a, b) * [a, b] = a * b, unde (a, b) este CMMDC, iar [a, b] este CMMMC. Deci [a, b] = a * b / (a, b).

Numere prime

  • Un număr natural p > 1 se numște prim dacă p|ab ⇒ p|a sau p|b.
  • Un număr natural p > 1 se numește ireductibil dacă d|p ⇒ d = 1 sau d = p.
  • Un număr natural p > 1 dacă și numai dacă este ireductibil.
  • Numerele 0 și 1 nu pot fi prime.

Pentru a demonstra că un număr natural este prim, putem demonstra că acesta nu are alți divizori în afară de 1 și el însuși.

Implementare

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    bool prime = true; // presupunem inițial ca n este prim

    if (n < 2) {
        prime = false; // dacă n este mai mic de 2, nu este prim
    }

    for (int d = 2; d * d <= n; d++) {
        if (n % d == 0) {
            prime = false; // dacă am găsit un divizor, n nu este prim
        }
    }

    if (prime) {
        cout << n << " este prim";
    }
    else {
        cout << n << " nu este prim";
    }
        
    return 0;
}

Descompunerea în factori primi

Implementare

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int d = 2;
    while (n > 1) {

        int count = 0;
        while (n % d == 0) {
            n /= d;
            count++; // dacă d este divizorul lui n, creștem numărătoarea
        }

        if (count) {
            cout << d << ' ' << count << '\n';
        }

        d++;
    }

    return 0;
}

Programul de mai sus afișează descompunerea în factori primi a lui n sub formă de factor putere.

Baze de numerație

Bazele de numerație dictează scrierea unui număr cu ajutorul puterilor bazei respective. De exemplu, în baza 10, numărul 245 este scris ca 245 = 2 * 10^2 + 4 * 10^1 + 5 * 10^0, deci, cu alte cuvinte, un număr scris în baza n va putea fi format din toate resturile posibile la împărțirea cu n, adică 0, 1, 2, ..., n - 1.

Prin convenție, începând cu restul 10, numerele vor fi notate cu litere mari sau mici ale alfabetului, astfel: 10 = A, 11 = B, 12 = C, 13 = D, 14 = E, 15 = F, etc.

Transformarea din baza 10 în baza b

Numerele se pot transforma din baza 10 în oricare altă bază, b. Pentru asta, se împarte n la b și se păstrează restul, apoi se împarte câtul la b și tot așa. Apoi, resturile se scriu în ordinea inversă obținerii lor, iar numărul obținut este transformarea lui n în baza b.

Exemplu

5 : 2 = 2, rest 1
2 : 2 = 1, rest 0
1 : 2 = 0, rest 1

Deci numărul 5 din baza 10 în baza 2 este 101.

În c++, transformarea din baza 10 în baza b se poate scrie astfel.

int num[105];
int idx = 0;
int n, b;

cin >> n >> b;

while (n) {
    num[idx] = n % b;
    n /= b;
}

for (int i = idx - 1; idx >= 0; idx--) {
    cout << num[idx];
}

Transformarea din baza b în baza 10

Transformarea din baza b în baza 10 a unui număr n se realizează după formula n(k)n(k-1)...n(1)n(0) = (n(k) * b^k) + (n(k-1) * b^(k-1)) + ... + (n(0) * b^0).

Exemplu

101 = 1 * 2^2 + 0 * 2^1 + 1 * 2^0 = 5

Deci numărul 101 din baza 2 în baza 10 este 5.

În c++, transformarea din baza b în baza 10 se poate scrie astfel.

int num[];
int idx;
int b;

...

int n = 0;
int p = 1;

for (int i = 0; i <= idx; i++) {
    n += p * num[i];
    p *= b;
}

cout << n;

Transformarea din baza b în baza c

Transformarea din baza b în baza c se realizează transformând numărul n din baza b în baza 10, iar apoi din baza 10 în baza c.



Transformarea din baza 10 în baza 2

#include <iostream>
using namespace std;

int n;
int ans[100];

int main() {
    cin >> n;
    int idx = 0;

    while (n) {
        ans[idx] = n % 2;
        n /= 2;
    }

    for (int i = idx - 1; i >= 0; i--) {
        cout << ans[i];
    }

    return 0;
}

Transformarea din baza 2 în baza 10

#include <iostream>
using namespace std;

int n[100];
int num;
int ans;

int main() {
    cin >> num;
    for (int i = num - 1; i >= 0; i--) {
        cin >> n[i];
    }

    int p = 1;
    for (int i = 0; i < num; i++) {
        ans += n[i] * p;
        p *= 2;
    }

    cout << ans;

    return 0;
}

Vectori și algoritmi comuni

Citire

Există două cazuri principale în care putem să citim un vector. Atunci când se specifică numărul său de elemente, n, și atunci când nu se specifică.

Numărul de elemente este cunoscut

Atunci când numărul de elemente este cunoscut, n, vom citi n numere într-un tablou unidimensional.

Exemplu

int v[50];
int n;

int main() {
    ...

    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }

    ...
}
  • este important de știut că declarând un vector global, în afara main-ului sau a unei funcții, acesta este inițializat cu valoarea 0 pe toate pozițiile.

Numărul de elemente NU este cunoscut

Atunci când nu cunoaștem exact numărul de elemente pe care trebuie să îl citim vom avea probleme ce ne vor cere să citim dintr-un fișier. În acest caz, vom citi cât de mult putem dintr-un fișier, până atingem caracterul \EOF, sau mai simplu spus, citim atât timp cât avem ceva de citit.

Exemplu

fisier.txt

1 55 2 6 24 223 6 7
3 4

main.cpp

ifstream fin("fisier.txt");

int v[50];

int main() {
    ...

    int x;
    int idx = 0;

    while (cin >> x) {
        v[idx] = x;
        idx++;
    }

    ...
}

În v se vor reține, în această ordine, numerele 1, 55, 2, 6, 24, 223, 6, 7, 3, 4.

Vectori caracteristici / de apariție

Vectorii caracteristici au rolul de a marca dacă un element apare sau nu într-un șir dat. Aceștia sunt de obicei de tip bool, deoarece nu necesită alte informații în plus.

  • un vector caracteristic are dimensiune constantă
  • un vector caracteristic trebuie inițializat cu valoarea 0 sau fals
  • valorile posibile se află printre indicii vectorului caracteristic. Pentru un șir de numere cu valori cuprinse între 2 și 1000, vom declara un vector caracteristic de mărime cel puțin 1001, pentru a cuprinde toate valorile posibile.

Exemplu

fisier.txt

2 55 2 6 24 223 6 7 1000

main.cpp

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

ifstream fin("fisier.txt");

bool car[1005];

int main() {
    int x;

    while (fin >> x) {
        car[x] = true;
    }

    return 0;
}

În vectorul de apariții, pozițiile care au valoarea de true sunt 2, 55, 2, 6, 24, 223, 6, 7, 1000.

Vectori de frecvență

Vectorii de frecvență au rolul de a număra de câte ori apare o valoare într-un șir dat. Este similar cu vectorul caracteristic, însă acum nu vom marca apariția, ci vom incrementa valoarea de pe poziția respectivă. Acesta este de obicei de tipul int.

  • un vector caracteristic are dimensiune constantă
  • un vector caracteristic trebuie inițializat cu valoarea 0
  • valorile posibile se află printre indicii vectorului caracteristic. Pentru un șir de numere cu valori cuprinse între 2 și 1000, vom declara un vector caracteristic de mărime cel puțin 1001, pentru a cuprinde toate valorile posibile.

Exemplu

fisier.txt

2 55 2 6 6 7 6 1000

main.cpp

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

ifstream fin("fisier.txt");

bool frv[1005];

int main() {
    int x;

    while (fin >> x) {
        frv[x]++;
    }

    return 0;
}

În vectorul de frecvență, poziția 2 are valoare 2, poziția 6 are valoare 3, 7 are 1, 55 are 1 și 1000 are 1. Restul pozițiilor au valoarea 0.

Probleme cu secvențe

pbInfo

Matrici și algoritmi comuni

Citire

De obicei, atunci când trebuie să citim o matrice vom primi mai întâi ca input un n și un m, reprezentând numărul de linii, respectiv cel de coloane.

Exemplu

#include <iostream>
using namespace std;

int n, m;
int mat[505][505];

int main() {
    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> mat[i][j];
        }
    }

    return 0;
}

Parcurgerea matricilor

Unele probleme pot necesita parcurgerea matricilor în diferite forme.

Parcurgerea tuturor elementelor

Indexat de la 0

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        int x = mat[i][j];
    }
}

Parcurgerea diagonalei principale

Indexat de la 0

for (int i = 0; i < n; i++) {
    int x = mat[i][i];
}

Parcurgerea diagonalei secundare

Indexat de la 0

for (int i = 0; i < n; i++) {
    int x = mat[i][n - i - 1];
}

Parcurgerea elementelor de deasupra diagonalei principale

Indexat de la 0

for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        int x = mat[i][j];
    }
}

Parcurgerea elementelor de deasupra diagonalei secundare

Indexat de la 0

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n - i; j++) {
        int x = mat[i][j];
    }
}

Parcurgerea elementelor de sub diagonala principale

Indexat de la 0

for (int i = 0; i < n; i++) {
    for (int j = 0; j < i + 1; j++) {
        int x = mat[i][j];
    }
}

Parcurgerea elementelor de sub diagonala secundara

Indexat de la 0

for (int i = 0; i < n; i++) {
    for (int j = i; j >= 0; j--) {
        int x = mat[i][n - j - 1];
    }
}

Parcurgerea elementelor în spirala

Link util

Indexat de la 1

for (int k = 1; k <= n / 2; k++) {
    for (int j = k; j <= n - k + 1; j++) {
        int x = a[k][j];
    }
    for (int i = k + 1; i <= n - k + 1; i++) {
        int x = a[i][n - k + 1];
    }
    for (int j = n - k; j >= k; j--) {
        int x = a[n - k + 1][j];
    }
    for (int i = n - k; i > k; i--) {
        int x = a[i][k];
    }   
}

Funcții

Funcțiile sunt o colecție de tipuri de date, variabile și instrucțiuni, care îndeplinesc o anumită sarcină, atunci când sunt apelate. Acestea sunt folosite, deoarece ne oferă câteva avantaje, precum:

  • reutilizarea codului - putem apela funcția de oricâte ori este nevoie
  • modularizare - putem împărții o problemă în mai multe probleme, dar mai simple
  • reducerea și depistarea erorilor

Anatomia funcțiilor

Funțiile au nevoie să fie declarate înainte de a putea fi folosite, ca orice alt lucru în C++. Acestea sunt formate din mai multe componente, precum:

Antetul funcției

int Sum(int a, int b)
  • funcția returnează o valoare de tip int
  • funcția se numește Sum
  • funcția ia ca parametrii 2 valori, a și b de tip int

Funcțiile pot returna mai multe tipuri de date, precum int, float, char, etc. și un tip special, numit void, care spune că funcția nu va returna nimic. Tipul de date returnat este specificat chiar la începutul funției, ca în exemplul dat.

Corpul funcției

{
    int val = a + b;
    return val;
}
  • funția are 2 instrucțiuni, una care face suma parametrilor a și b și alta care returnează valoarea lui val

Este necesar ca funcțiile care au un tip de date diferit de void să conțină instrucțiunea return, care să returneze tipul de date specificat în antet

Apelul funcției

Sum(10, 2);
  • apelul se realizează în funția main sau orice altă funcție
  • se vor transmite funcției apelate valorile necesare pentru parametrii ceruți de aceasta

Este necesar ca ordinea parametrilor să fie respectată, iar apelul să se realizeze corespunzător. 


#include <iostream>
using namespace std;

int Sum(int a, int b) {
    int val = a + b;

    return val;
}

int main() {
    cout << Sum(10, 2);

    return 0;
}

Programul va afișa pe ecran valoarea 12.

Returnarea valorilor

Așa cum am discutat mai sus, funțiile sunt folositoare mai ales deoarece pot să returneze valori. Tipul de date returnat este scris primul, înaintea funcției și poate fi void, int, double, etc. Cu toate acestea, funcția poate returna valori și prin parametrii, folosind o referință. În acest caz, tipul de date returnat este void, iar la final nu vom mai avea instrucțiunea return.

Exemplu

#include <iostream>
using namespace std;

void Sum(int a, int b, int& val) {
    val = a + b;
}

int main() {
    int sum;

    Sum(10, 2, sum);
    cout << sum;

    return 0;
}

În exemplul dat, funcția ia ca parametrii 2 valori de tip int și o valoare de tip int&, unde & ne spune că acel parametru este de fapt o referință. Acest lucru înseamnă că dacă îl vom modifica în funcție, acesta va fi modificat și în afara ei, acolo unde a fost declarat. Așadar, programul nostru face suma a 2 numere, însă aceasta este trimisă, prin referință, variabilei sum, declarată în main.

Exemplu

#include <iostream>
using namespace std;

void MaxVal(int v[], int n, int& maxVal) {
    maxVal = -1;

    for (int i = 0; i < 5; i++) {
        if (v[i] > maxVal) {
            maxVal = v[i];
        }
    }
}

int main() {
    int v[5] = {0, 4, 100, 99, 3};
    int maxVal;

    MaxVal(v, 5, maxVal);
    cout << maxVal;

    return 0;
}

În acest exemplu, funcția va returna, prin referință, valoarea maximă din vectorul v.

Exemplu

#include <iostream>
using namespace std;

int MaxVal(int v[], int n) {
    int maxVal = -1;

    for (int i = 0; i < 5; i++) {
        if (v[i] > maxVal) {
            maxVal = v[i];
        }
    }

    return maxVal;
}

int main() {
    int v[5] = {0, 4, 100, 99, 3};

    cout << MaxVal(v, 5);

    return 0;
}

În acest exemplu, funcția va returna valoarea maximă din vectorul v.

Șiruri de caractere

Pentru a face operații cu șiruri de caractere ne putem folosi de librăria cstring. Aceasta are mai multe funcții care ne ajută să manipulăm șirurile de caractere. Pentru a folosi cstring trebuie să îl includem folosind #include <cstring> la începutul programului.

Citire

Atunci când trebuie să citim caractere avem mai multe opțiuni.

  1. Citim câte un cuvânt până la spațiu. ```cpp char s1[55]; cin >> s1;
char s2[55];
cin >> s2;

// Dacă inputul este: "abc def", s1 va avea valoarea "abc", iar s2 ca avea valoarea "def"
```

  1. Le citim pe rând și le memorăm într-un vector.

    char s[55];

for (int i = 0; i < 50; i++) {
    cin >> s[i];
}
s[50] = '\0';

  2. Le citim într-un vector de caractere folosind funcția cin.get().

    char s[55];
cin.get(s, 50); // Citește până ajunge la \0 (și reține `\n`) sau citește 50 de caractere

  3. Citim câte un singur rând folosind funcția cin.getline().

    char s[55];
cin.getline(s, 50); // Citește până ajunge la \n (și nu îl reține) sau citește 50 de caractere

Afișare

Atunci când afișăm un șir de caractere avem mai multe opțiuni.

  1. Afișăm caracterele pe rând. 
    char s[55] = "abcde";
s[5] = '\0';

for (int i = 0; i < strlen(s); i++) {
    cout << s[i];
} 
// Se afișează abcde
  2. Afișăm șirul folosind cout. Acesta se va afișa până întâlnește caracterul \0. 
    char s[55] = "abcde";
s[5] = '\0';

cout << s;
// Se afișează abcde

Funcții

strcpy | strncpy | strcat | strncat | strcmp | strncmp | strchr | strrchr | strstr | strtok | strlen

  • strcpy

    char * strcpy (char * destination, const char * source);

    Îl copiază pe source în destination.

    Exemplu

    char destination[55];
char source[55] = "bac 2024";
strcpy(destination, source); // destination = "bac 2024"

  • strncpy

    char * strncpy (char * destination, const char * source, int count);

    Copiază primele n caractere din source în destination.

    • Dacă count este mai mare decât source se va insera \0 până la count.
    • Dacă source este mai mare decât count nu se va insera \0 la final.

    Exemplu

    char destination[55];
char source[55] = "bac 2024";
int count = 3;
strncpy(destination, source, count); // destination = "bac"

  • strcat

    char * strcat (char * destination, const char * source);

    Îl concatenează în destination pe source începând de la primul \0.

    Exemplu

    char destination[55] = "bac ";
char source[55] = "2024";
strcat(destination, source); // destination = "bac 2024"

  • strncat

    char * strncat (char * destination, const char * source, int count);

    Concatenează primele n caractere din source în destination începând de la \0.

    • Dacă count este mai mare decât source se va copia până la \0.

    Exemplu

    char destination[55] = "bac";
char source[55] = " 2024567";
int count = 5;
strncat(destination, source, count); // destination = "bac 2024"

  • strcmp

    int strcmp (char * str1, const char * str2);

    Compară str1 cu str2. Continuă până când gasește un caracter diferit sau dă de \0.

    • Dacă primul caracter care nu se potrivește are o valoare mai mică în str1 decât în str2 returnează o valoare < 0.
    • Dacă cele două șiruri sunt egale returnează 0.
    • Dacă primul caracter care nu se potrivește are o valoare mai mare în str1 decât în str2 returnează o valoare > 0.

    Exemplu

    char str1[55] = "abbeb ca";
char str2[55] = "bbc";
strcmp(str1, str2); // ('e' - 'c') = 2

  • strncmp

    int strncmp (char * str1, const char * str2, int count);

    Compară până la n caractere din str1 cu cele din str2. Continuă până când gasește un caracter diferit, ajunge la count sau dă de \0.

    • Dacă primul caracter care nu se potrivește are o valoare mai mică în str1 decât în str2 returnează o valoare < 0.
    • Dacă cele două șiruri sunt egale returnează 0.
    • Dacă primul caracter care nu se potrivește are o valoare mai mare în str1 decât în str2 returnează o valoare > 0.

    Exemplu

    char str1[55] = "abbeb ca";
char str2[55] = "bbxx";
int count = 2;
strncmp(str1, str2, count); // 0

  • strchr

    char * strchr (char * str, char c);

    Returnează un pointer către prima apariție a lui c în str.

    • Dacă c nu este găsit, returnează NULL.

    Exemplu

    char str[55] = "bac scoala 2024";
char c = 'a';
strchr(str, c); // "ac scoala 2024"

  • strrchr

    char * strrchr (char * str, char c);

    Returnează un pointer către ultima apariție a lui c în str.

    • Dacă c nu este găsit, returnează NULL.

    Exemplu

    char str[55] = "bac scoala 2024";
char c = 'a';
strrchr(str, c); // "a 2024"

  • strstr

    char * strstr (char * str1, char * str2);

    Returnează un pointer către prima apariție a lui str2 în str1.

    • Dacă str2 nu este găsit, returnează NULL.
    • Dacă dă de \0 se oprește.

    Exemplu

    char str1[55] = "bac scoala 2024";
char str2[55] = "20";
strstr(str1, str2); // "2024"

  • strtok

    char * strtok (char * str, char * delim);

    Caută prima secvență care începe cu un char c care nu este din delim și se termină cu un char c din delim.

    • Dacă str este NULL, continuă de unde a rămas din invocarea anterioară.
    • Dacă nu mai găsește, returnează NULL.

    Exemplu

    char str[50] = " Da. Probabil? De_bună_seamă!:)";
char delim[10] = "!?.,-;() ";
strtok(str, delim);  // "Da"
strtok(NULL, delim); // "Probabil"
strtok(NULL, delim); // "De_bună_seamă"
strtok(NULL, delim); // "NULL"

  • strlen

    int strlen (const char * str);

    Returnează lungimea lui str, adică atunci când întâlnește caracterul \0.
    Exemplu

    char s[55] = "Bac2024";
strlen(s); // 7

Pointeri și șiruri

Atunci când apelăm o funție precum strchr sau strstr, aceasta va returna un pointer la caracterul, respectiv începutul șirului pe care îl găsește. Acesta este un lucru foarte important, deoarece putem afla exact pe ce poziție se află caracterul sau udne începe șirul găsit. Pentru a obține o valoare întreagă dintr-un pointer, trebuie să îl scadem din alt pointer. Acest lucru funcționează, deoarece memoria este continuă. Spre exemplu, prima poziție a unui șir se poate afla la pointerul 0x000010. Asta înseamnă că un caracter de la poziția 2 a șirului (sau al 3-lea caracter al șirului) se află la pointerul 0x000012.

Exemplu

char s[55] = "Bac2024";
int pos = strchr(s, 'a') - s;
cout << pos; // 1

Recursivitate

Recursivitatea reprezintă proprietatea unor noțiuni de a se defini prin ele însele. Câteva exemple pot fi:

  • șirul lui Fibonacci: Fn = Fn−1 + Fn-2
  • factorialul unui număr: n! = n ⋅ (n - 1)!
  • progresiile aritmetice: An! = An-1 + r

În C++, recursivitatea se poate realiza apelând funcții care se pot autoapela. Primul apel realizat, se numește apel principal.

Cum funcționează

Variabilele locale, precum și valorile parametrilor se memorează la fiecare apel și sunt specifice instanței respective a apelului funcției. Acestea sunt memorate în memoria de tip stivă.

Pentru fiecare apel al funcției, se va adăuga în stivă o zonă de memorie dedicată apelului respectiv, în care sunt stocate toate variabilele locale și parametrii cu care a fost făcut apelul. Această zonă va persista până când funția va fi fost încheiată, moment în care memoria dedicată apelului se va elibera. Dacă din apelul curent se efectuează alt apel, pe stivă se va adăuga o nouă zonă de memorie, iar procesul se repetă. Accesibilă va fi doar acea bucată de memorie care se află vârful stivei, aceasta reprezentând chiar ultimul apel al funcției.

Apelul se va termina atunci când return este atins sau când funția ajunge la final. După aceea, se va continua rularea apelului anterior, de unde a fost lăsat. Valorile variabilelor vor fi în continuare cele specifice numai acestui apel.

Anatomia unei funcții recursive

Pentru a putea utiliza o funcție recursiva avem nevoie de mai multe elemente. Acestea sunt definiția funției, la care se adaugă condiția de oprire, alte operații și autoapelarea și apelarea principală.

Sintaxă

int FunctieRecursiva(int n) {
    if (conditie_de_oprire) {
        return valoare_default;
    }

    alte_operatii();

    FunctieRecursiva(NoulN(n));
}

int main() {
    ...

    FunctieRecursiva(valoare);

    ...
}

Factorialul unui număr

De exemplu, factorialul unui număr se poate calcula așa:

Varianta iterativă

int Factorial(int n){
    int p = 1;
    for(int i = 1 ; i <= n ; i ++) {
        p = p * i;
    }

    return p;
}

Varianta recursivă

int Factorial(int n){
    if(n == 0) {
        return 1;
    }

    return n * Factorial(n - 1);
}

Se poate observa clar condiția de oprire a funcției recursive, anume daca n este 0, returnează 1. Aceasta se datorează definiției matematice a funcției recursive, care spune că 0! = 1.

Șirul lui Fibonacci

Un alt exemplu este șirul lui Fibonacci.

Varianta recursivă

int Fibonacci(int n){
    if(n == 0) {
        return 0;
    }
    else if (n == 1) {
        return 1;
    }
    
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Rezolvarea problemelor

Pentru a putea rezolva probleme utilizând metode recursive, se pot scrie toți pașii, în ordinea în care îi rulează programul, tinând cont si actualizând valorile variabilelor și ce returnează fiecare apel în parte. Cu timpul, exersând, vă veți obișnui cu recursivitatea și vă va fi mult mai ușor.

Acestea sunt câteva formule simple de recursivitate:

  • factorialul unui număr: 1, daca n = 0 SAU n! = n * (n - 1)!, altfel
  • calculul combinărilor: (n, k) = 1, daca n = k sau k = 0 SAU (n - 1, k - 1) + (n - 1, k), altfel, unde (n, k) reprezintă combinări de n luate câte k.

Generarea submulțimilor

Se dă un număr natural n. Să se genereze toate submulțimile mulțimii {1,2,3,...,n}.

#include <iostream>
using namespace std;

int x[15];
int n;

void Print(int k){
    for(int i = 1 ; i <= k ; i++) {
        cout << x[i] << " ";
    } 
    cout << '\n';
}

void BKT(int k){
    for(int i = x[k - 1] + 1; i <= n; i++) {
        x[k] = i;
        Print(k);

        BKT(k + 1);
    }
}

int main() {
    cin >> n;
    BKT(1);

    return 0;
}



Generarea permutărilor

Fie un număr natural n. Să se afișeze, în ordine lexicografică, permutările mulțimii {1,2,⋯,n}.

#include <iostream>
using namespace std;

int x[15];
int n;

void Print() {
    for (int i = 1; i <= n; i++) {
        cout << x[i] << " ";
    }
    cout << '\n';
}

// Checks if elements are repeating
bool IsValid(int k) {
    for(int i = 1; i < k; i++) {
        if(x[k] == x[i]) {
            return false;
        }
    }

    return true;
}

void BKT(int k) {
    for(int i = 1; i <= n ; i++) {
        x[k] = i;

        if(IsValid(k)) {
            if(k == n) {
                Print();
            }
            else {
                BKT(k + 1);
            }
        }    
    }
}

int main() {
    cin >> n;
    BKT(1);

    return 0;
}



Probleme

Submultimi | SubmDiv | Permutari | Combinari | cifre_c | Aranjamente | numere124 | FiboRec | DivImpRec | FactorialRec | FactorialRec1 | VectorMaxMinSumRec

Grafuri Neorientate

Un graf este o mulțime de obiecte, numite noduri, care sunt legate între ele printr-o mulțime de muchii, cărora li see pot atribui și direcții. Nodurile se notează, tradițional, cu numere de la 1 la n, unde n este numărul total de noduri.

Un graf este neorientat, dacă este graf, iar muchiile sale nu au o direcție.

Gradele unui varf

Gradul unui vărf este dat de numărul de muchii care se intersectează cu acesta.

  • un vărf cu gradul 0 se numește izolat
  • un vârf cu gradul 1 se numește terminal

Reprezentare

Matricea de adiacență

Matricea de adiacență stabilește că între nodul i (rândul) și nodul j (coloana) există o muchie.

  • matricea de adiacență a unui graf neorientat este întotdeauna simetrică față de diagonala principală
  • elementele de pe diagonala principală sunt 0

Lista de adiacență

Voi menționa lista de adiacență doar ca un concept important, deoarece aceasta nu intră în materia de bac. Aceasta presupune memorarea tuturor vecinilor unui nod, pentru fiecare nod în parte. Dacă am avea un șir de n vectori din STL, pentru fiecare i de la 1 la n, vom avea un vector de noduri, care vor reprezenta vecinii nodului i. Deci, de la i la j există o muchie.

Conexitate

Lanț

Un lanț este o succesiune de vârfuri L = [x1, x2, ..., xk] cu propritatea că oricare 2 vârfuri consecutive sunt adiacente.

  • vârfurile x1 și xk se numesc extremitățile lanțului
  • lungimea unui lanț este dată de numărul de muchii din care este format

Se numește lanț elementar, lanțul care conține numai vârfuri distince două câte două.

Se numește lanț simplu, lanțul care conține numai muchii distincte.

Ciclu

Un ciclu este un lanț simplu în care primul vârf este identic cu ultimul

  • lungimea unui ciclu este dată de numărul de muchii din care este format
  • lungimea minimă a unui ciclu este 3

Se numește ciclu elementar, ciclul care are toate vârfurile distince, mai puțin primul și ultimul.

Se numește ciclu hamiltonian, un ciclu elementar care conține toate vârfurile grafului, o singură dată.

Se numește ciclu eulerian, un ciclu care conține toate muchiile grafului, o singură dată.

Un graf neorientat care nu conține niciun ciclu se numește aciclic.

Graf conex

Un graf conex este un graf care pentru oricare 2 vârfuri ale sale există un lanț care să le lege. Cu alte cuvinte, un graf este conex dacă toate nodurile sale sunt conectate.

Componente conexe

Se numește componentă conexă a unui graf G = (X, U), un subgraf conex H = (Y, V), care are proprietatea că nu există niciun lanț în G care să lege un vârf din Y cu un vârf din X - Y.

  • un graf este conex dacă admite o singură componentă conexă
  • un graf poate admite de la 1 la n componente conexe

Tipuri de grafuri neorientate

Graf nul

Un graf este graf nul, dacă nu are nicio muchie.

Graf complet

Un graf este graf complet, dacă oricare două vârfuri distince ale sale sunt adiacente. Cu alte cuvinte dacă are numărul maxim de muchii.

  • numărul de muchii ale unui graf complet cu n noduri este m = n * (n - 1) / 2

Graf parțial

Un graf este graf parțial al grafului G, dacă se poate obține din graful G prin eliminarea unor muchii.

Subgraf

Un graf este subgraf al grafului G, dacă se poate obține din graful G prin eliminarea unor noduri și muchiilor adiacente acestora.

Graf complementar

Un graf este complementar al grafului G cu n noduri, dacă se poate obține dintr-un graf complet cu n noduri, căruia i s-au eliminat muchiile din G.

Graf hamiltonian

Un graf hamiltonian este un graf care conține un ciclu hamiltonian.

  • un graf cu n noduri este hamiltonian, dacă n ≥ 3, iar gradul oricărui vârf verifică inegalitatea d(x) ≥ n / 2

Graf eulerian

Un graf eulerian este un graf care conține un ciclu eulerian.

  • un graf este eulerian dacă și numai dacă este conex și gradele tuturor vârfurilor sale sunt pare

Grafuri Orientate

Un graf este orientat, dacă este graf, iar muchiile sale au o orientare.

Gradele unui vârf

Nodurile unui graf orientat au două tipuri de grade, exterior și interior.

  • se numește grad exterior numărul arcelor care ies din nod
  • se numește grad interior numărul arcelor care intră în nod

Reprezentare

Matricea de adiacență

Matricea de adiacență stabilește că între nodul i (rândul) și nodul j (coloana) există o muchie orientată de la i la j.

  • elementele de pe diagonala principală sunt 0

Lista de adiacență

Voi menționa lista de adiacență doar ca un concept important, deoarece aceasta nu intră în materia de bac. Aceasta presupune memorarea tuturor vecinilor unui nod, pentru fiecare nod în parte. Dacă am avea un șir de n vectori din STL, pentru fiecare i de la 1 la n, vom avea un vector de noduri, care vor reprezenta nodurile unite de nodul i, cu direcția de la i la j.

Conexitate

Lanț

Un lanț (drum) este o succesiune de vârfuri L = [x1, x2, ..., xk] cu propritatea că oricare 2 vârfuri i și j, consecutive, sunt adiacente și au o muchie orientată de la i la j.

  • vârfurile x1 și xk se numesc extremitățile lanțului
  • lungimea unui lanț este dată de numărul de arce din care este format

Se numește lanț elementar, lanțul care conține numai vârfuri distince două câte două.

Se numește lanț simplu, lanțul care conține numai arce distincte.

Circuit

Un circuit este un lanț simplu în care primul vârf este identic cu ultimul

  • lungimea unui circuit este dată de numărul de arce din care este format
  • lungimea minimă a unui circuit este 3

Se numește circuit elementar, circuit care are toate vârfurile distince, mai puțin primul și ultimul.

Se numește circuit hamiltonian, un circuit elementar care conține toate vârfurile grafului.

Se numește circuit eulerian, un circuit care conține toate muchiile grafului.

Graf tare conex

Un graf tare conex este un graf care pentru oricare 2 vârfuri distincte ale sale există cel puțin un drum care să le lege. Cu alte cuvinte, putem ajunge din orice nod în orice alt nod.

Componente tare conexe

Se numește componentă tare conexă a unui graf, un subgraf tare conex căruia dacă i-am mai adăuga un nod, n-ar mai fi tare conex.

  • un graf este tare conex dacă admite o singură componentă tare conexă

Tipuri de grafuri orientate

Graf parțial

Un graf este graf parțial al grafului G, dacă se poate obține din graful G prin eliminarea unor arce.

Subgraf

Un graf este subgraf al grafului G, dacă se poate obține din graful G prin eliminarea unor noduri și arcelor adiacente acestora.

Graf complet

Un graf este graf complet, dacă oricare două vârfuri distince ale sale sunt adiacente.

  • numărul de grafuri orientate cu n noduri este 3 ^ (n * (n - 1) / 2))

Graf turneu

Un graf este graf turneu, dacă între oricare două vârfuri distincte, i și j, există un singur arc, (i, j) sau (j, i).

Graf hamiltonian

Un graf hamiltonian este un graf care conține un circuit hamiltonian.

Graf eulerian

Un graf eulerian este un graf care conține un circuit eulerian.

Arbori

Un arbore este un graf neorientat conex și aciclic.

  • un arbore cu n vârfuri are n - 1 muchii
  • între oricare două vârfuri ale unui arbore există un lanț elementar unic
  • un arbore este un graf aciclic și maximal are proprietatea că dacă s-ar mai adăuga o muchie, s-ar obține un ciclu

Arborilor li se poate alege o rădăcină, de care putem spune că „agățăm” arborele, iar restul nodurilor „cad”.

Terminologie

  • două noduri care au același tată se numesc frați
  • lungimea unui lanț de la rădăcina arborelui la un nod x, se numește adâncimea sau nivelul nodului x
  • nivelul maxim se numește înălțimea arborelui
  • un nod al arborelui împreună cu toți copiii săi formează un subarbore
  • frunzele sunt nodurile care nu sunt tați

Reprezentare

Vectori de tați

O modalitate comună de a reprezenta un arbore este utilizând un vector de tați, în care fiecare poziție păstrează informații despre descendentul direct.

  • tati[r] = 0, unde r este rădăcina arborelui
  • tati[i] = tatăl nodului i

Arbori binari

Un arbore este binar dacă fiecare nod are cel mult 2 descendenți direcți, numiți și descendentul stâng și descendentul drept.

Arbori binari plini

Un arbore binar este plin, dacă pe fiecare nivel k de la 0 la h, unde h este înălțimea arborelui, are 2 ^ k noduri. Cu alte cuvinte, dacă are numărul maxim de noduri, pentru un h dat sau dacă toate frunzele sunt maximale și pe ultimul strat.

  • un arbore binar plin cu înălțimea h are (2 ^ h) - 1 noduri

Arbori binari compleți

Un arbore binar este complet, dacă pe fiecare nivel k de la 0 la h - 1, unde h este înălțimea arborelui, conține 2 ^ k noduri, iar nivelul k conține 2 ^ h sau mai puține noduri, acestea fiind de regulă grupate în partea stângă.

  • un arbore binar plin este și arbore binar complet

Operații pe biți

În memorie, datele sunt reprezentate prin biți. Din această cauză, uneori poate fi necesară sau mai facilă utilizarea unor operații care să impacteze direct biții unei valori.

O variabilă de tip int este stocată pe 32 de biți, primul bit fiind bitul de semn. Un exemplu este numărul 133, a cărui reprezentare este 0000000010000101, cu primul bit 0, adică numărul este pozitiv. O variabilă de tip long long este stocată pe 64 de biți după aceeași regulă.

Operatori

Operatorul de shiftare spre stânga <<

Operatorul de shiftare spre stânga mută toți biții numărului spre stânga cu numărul de poziții specificate, inserând 0. Exemplu

1 << 3 == 8 // 1 -> 1000
1 << 6 == 64 // 1 -> 1000000

Pentru a calcula 2^n putem folosi operația 1 << n.

Operatorul de shiftare spre dreapta >>

Operatorul de shiftare spre dreapta mută toți biții numărului spre dreapta cu numărul de poziții specificate, inserând 0. Exemplu

8 >> 3 == 8 // 1000 -> 1
5 >> 2 == 1 // 101 -> 1

Operatorul de negație ~

Operatorul de negație dă flip la toate valorile biților. Exemplu

~ 133 == -134 // 133 este 0000000010000101, iar -134 este 1111111101111010

Operatorul de conjucție &

Operatorul de conjuncție, sau după denumirea logică AND, evaluează fiecare pereche de biți în parte dupa următorul tabel de adevăr.

0 & 0 == 0
0 & 1 == 0
1 & 0 == 0
1 & 1 == 1

Exemplu

5 & 0 == 4
(133 & (1 << 7)) >> 7 == 1 // 133 este 0000000010000101, iar (1 << 7) este 10000000

Operatorul de disjucție |

Operatorul de disjuncție, sau după denumirea logică OR, evaluează fiecare pereche de biți în parte dupa următorul tabel de adevăr.

0 | 0 == 0
0 | 1 == 1
1 | 0 == 1
1 | 1 == 1

Exemplu

5 | 2 == 7 // 5 este 101, 2 este 10, iar 7 este 111

Operatorul de disjucție exclusivă ^

Operatorul de disjucție exclusivă, sau după denumirea logică XOR, evaluează fiecare pereche de biți în parte dupa următorul tabel de adevăr.

0 ^ 0 == 0
0 ^ 1 == 1
1 ^ 0 == 1
1 ^ 1 == 0

Exemplu

5 ^ 2 == 7 // 5 este 101, 2 este 10, iar 7 este 111
5 ^ 3 == 6 // 5 este 101, 2 este 11, iar 7 este 110

Combinatorică

Combinatorica este un domeniu al matematicii care studiază modalitățile de numărare, aranjare și alegere ale elementelor mulțimilor finite.

Produsul cartezian

Dacă mulțimile A1, A2, …, An au cardinalele k1, k2, …, kn atunci numărul de elemente al produsului cartezian A1×A2×…×An este k1⋅k2⋅…⋅kn.

Submulțimile unei mulțimi

Dacă o mulțime are n elemente, atunci aceasta are 2^n submulțimi.

Permutări

O permutare este o aranjare a elementelor unei mulțimi într-o anumită ordine.

{1, 4, 2, 3} este permutare a mulțimii {1, 2, 3, 4}

Numărul de permutări al unei mulțimi cu n elemente este n! = 1 ⋅ 2⋅ ⋅ … ⋅ n.

Aranjamente

Dacă A este o mulțime cu n elemente, submulțimile ordonate cu k elemente ale lui A se numesc aranjamente a n elemente luate câte k.

Probleme

  1. Numărul de grafuri neorientate de 5 noduri.

  2. Numărul de grafuri orientate de 5 noduri.

  3. Numărul de grafuri neorientate de 5 noduri, cu nodul 2 legat de nodul 1.

  4. Numărul de grafuri de 5 noduri cu cel putin o muchie.

  5. Numărul de grafuri neorientate în care nodul 2 are gradul 2, cu 7 noduri.

  6. Numărul de grafuri neorientate cu 2 componente conexe și 5 noduri.

  7. Numărul de grafuri orientate complete cu n noduri.

  8. Numărul de grafuri neorientate în care nodul 2 are gradul 3 și nodul 1 poate fi legat doar de nodurile 2 sau 5.

  9. Numărul de numere de 5 cifre distincte.

  10. Numărul de numere de 3 cifre, ordonate strict crescător, impare.

  11. Numărul de cicluri hamiltoniene în graf complet cu n noduri.

  12. Numărul de anagrame ale unui cuvânt.

Răspunsuri

  1. 2^(5 * 4 / 2) = 2^10

  2. 4^(5 * 4 / 2) = 2^20

  3. 2^(5 * 4 / 2 - 1) = 2^9

  4. 3 * 4^9

  5. (C de 6 luate câte 2) * 2^15

  6. Indiciu: împărțirea problemei în posibilitățile de configurare a grafului
    230

  7. 3^(n(n - 1) / 2) (sunt 3 stări ale muchiilor)

  8. 2^((n-3) * (n - 2) / 2) * 2 * ((C de (n - 2) luate câte 2) - (C de (n - 2) luate câte 3))

  9. 8 * 8 * 7 * 6 * 5

  10. (C de 4 luate câte 4) + (C de 6 luate câte 4) + (C de 8 luate câte 4)

  11. (n - 1)! / 2 (împărțirea la 2 ne scapă de oglindite)

Programare Dinamică

Programarea dinamică este vast utilizată în competițiile de algoritmică. Aceasta însă poate să apară într-o formă simplă și la subiectele de admitere. Voi prezenta programarea dinamică așa cum am înțeles-o eu și așa cum consider că este util să fie înțeleasă pentru evitarea confuziilor.

Programarea dinamică se bazează pe reutilizarea unui rezultat deja calculat pentru a ajunge la următorul. Un exemplu foarte bun poate fi problema treptelor care ne spune ca: Se dă o scară cu n trepte. Pornind de la bază, în câte moduri putem urca aceste trepte știind că putem sări fie pe treapta imediat următoare în sus, fie 2 trepte, în sus.

Pe prima treaptă vom putea ajunge mereu într-un sigur mod. Pe a 2-a treaptă putem ajunge fie de pe prima, fie de la bază. Pe a 3-a putem ajunge fie de pe prima fie de pe a 2-a. Ce ne spune această observație? Că pe treapta 3 putem ajunge însumând numărul de posibilități de a ajunge pe treapta 2 și numărul de posibilități de a ajunge pe treapta 1. Aceasta este o formulă general valabilă: modalitati(n) = modalitati(n - 1) + modalitati(n - 2)

De cele mai multe ori, când încercăm să scoatem formula unei dinamici, trebuie să ne gândim ce ce informații avem nevoie. În acest caz avem nevoie de numărul treptei și de numărul de modalități. Pentru asta putem construi un vector:

const int NMAX = 1005;

int dp[NMAX]; // dp[i] = dp[i - 1] + dp[i - 2], unde dp[i] este numarul de 
              // modalitati, iar i este numarul treptei

Practic valoarea din vector ne memorează infomația ce ne spune rezultatul, iar dimensiunea acesteia, i, ne spune pentru a câta treapta se întâmplă. Totul se reduce la găsirea informațiilor de care avem nevoie și păstrarea lor într-o structură de date cu una, două sau mai multe dimensiuni, în care valoarea stocată reprezintă de obicei răspunsul, iar dimensiunile niște variabile de care trebuie să ținem cont.

Ca principiu, atunci când gandim o dinamică, vrem să găsim o formulă generală, care să meargă pentru orice iterație, care pornește de la prima poziție.

  1. Încercăm să găsim o formulă pentru dp[i] sau dp[i][j], etc. Depinde de ce avem nevoie.
  2. Spunem cine este dp[i] sau dp[i][j], etc.
  3. Spunem cine sunt i, j, etc.

Pentru problema treptelor avem:

...

dp[0] = 0;
dp[1] = 1;

for (int i = 1; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
}

cout << dp[n] << '\n';

...

Problemă

Acum încercați să găsiți singuri dp-ul pentru termenul n al șirului lui Fibonacci. Soluția se află mai jos.




Solutie

  1. Știm că un termen din Fibonacci se obține mereu din suma ultimilor 2.

  2. Deci putem determina un dp[i] = dp[i - 1] + dp[i - 2], unde valorile de început sunt dp[0] = 1 și dp[1] = 1.
...

dp[0] = 1;
dp[1] = 1;

for (int i = 0; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
}

cout << dp[n] << '\n';

...

Problemă

O altă problemă este Cladire de pe pbInfo. Încercați mai întâi voi să scoateți dinamica. Acest tip de probleme se învață cel mai bine prin a gandi bine problema.




Solutie

  1. Observăm din cerință ca dinamica noastră este deja scrisă într-o formă: se poate ajunge numai în camerele (i+1,j) sau (i,j+1).

  2. Deci dinamica noastră ar arăta cam așa: dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + dp[i][j]. În cerință ni se spunea care va fi căsuța viitoare, iar noi am schimbat-o și am spus pentru căsuța curentă, care au fost căsuțele tyrecute din care am fi putut veni.
  3. Se spune că pornim din căsuța (1, 1), deci dp[1][1] = 1, iar resul valorilor sunt inițial 0.
...

dp[1][1] = 1;

for (int i = 1; i <= n; i++)
{
    for (int j = 1; j <= m; j++)
    {
        dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] + dp[i][j]);
    }
}

...

Nu copiați sursa pur și simplu! Problema mai cere ceva!