Arbori C++

Arborii sunt un caz particular al grafurilor. Acestia sunt compusi dintr-o serie de noduri interconectate in care se gasesc informatii.

Definitie: Arborele este un graf neorientat conex fără cicluri în care unul din noduri este desemnat ca rădăcină. Nodurile pot fi aşezate pe niveluri începând cu rădăcina care este plasată pe nivelul 1.

Radacina unui arbore este un nod special care ajuta la delimitarea arborelui pe nivele. Acest nod se afla pe cel mai inalt nivel din arbore.

Astfel, arborele devine mai usor de parcurs, deoarece plasarea nodurilor pe nivele duce la o structurare mai eficienta a informatiilor. De asemenea, algoritmii ce folosesc arbori sunt foarte usor de implementat recursiv, caci la fiecare pas, putem separa arborele in mai multi arbori mai mici.

Exemplu de arbore:

Arborele de mai sus are ca radacina nodul F.

In arborele de mai sus, putem privi nodul B ca radacina, a unui nou arbore, mai mic (sub-arbore).

In continuare vom prezenta cateva notiuni utile in intelegerea arborilor. Vom folosi ca exemplu arborele de mai sus cu radacina F.

Arborele poate fi impartit in nivele astfel :

  • F(nodul radacina) – Nivelul 1
  • B si G – Nivelul 2
  • A, D si I – Nivelul 3
  • C, E si H – Nivelul 4

Un nod A este descendent al unui alt nod B, daca este situat pe un nivel mai mare decât B şi există un lanţ care le uneşte şi nu trece prin rădăcină.Mai multe despre lanturi gasiti aici.

Exemplu: In arborele de mai sus E este descendentul lui B, si al lui A.

Un nod A este fiu/descendent direct al unui alt nod B, daca este situat pe nivelul imediat urmator nodului B si exista muchie intre A si B.

Exemplu: In arborele de mai sus B si G sunt fii lui F(nodul radacina), A e fiul lui B, H e fiul lui I etc.

Un nod A este ascendent al unui alt nod B, daca este situat pe un nivel mai mic decat B si exista lant care le uneste si nu trece prin radacina.

Exemplu : In arborele de mai sus G este ascendentul lui H,B este ascendentul lui C.

Un nod A este parinte al unui alt nod B, daca este situat pe nivelui imediat superior nodului B si exista muchie intre A si B.

Exemplu: In arborele de mai sus F este parintele lui B,D este parintele lui E, I este parintele lui H etc.

Doua noduri sunt frati daca au acelasi parinte.

Exemplu : B si G sunt frati, A si D sunt frati.

Un nod este frunza daca nu are niciun fiu, adica se afla pe ultimul nivel.

Exemplu : In arborele nostru frunzele sunt C,E si H.

Spor la lucru! Daca aveti intrebari nu ezitati sa le lasati in comentarii, va vom raspunde cat de repede putem 🙂

Probleme siruri de caractere C++

Mai jos puteti gasi probleme ce se intalenesc adesea la clasa sau la exemenul de bacalaureat.

Palindrom
Frecventa unui caracter intr-un text
Verificare daca doua cuvinte sunt anagrame
Cuvantul cel mai lung
Numarul de vocale dintr-un sir
Numarul de aparitii a unui cuvant intr-un text
Conversia unui sir intr-un sir cu litere mici
Inlocuirea unui cuvant dintr-un text cu un cuvant dat

Spor la lucru! Daca aveti intrebari nu ezitati sa le lasati in comentarii, va vom raspunde cat de repede putem 🙂

Probleme vectori C++

Mai jos puteti gasi probleme ce se intalnesc adesea la clasa sau la examenul de bacalaureat.

Sortarea unui vector prin interschimbare
Sortarea unui vector prin bubble sort
Maximul si minimul unui vector
Inserarea unui element intr-un vector
Eliminarea unui element dintr-un vector
Cel mai mare divizor comun (cmmdc) al unui vector
Cel mai mic multiplu comun (cmmmc) al unui vector
Afisarea elementelor pare ale unui vector
Afisarea elementelor impare ale unui vector
Afisarea elementelor de pe pozitii pare si impare dintr-un vector
Vectorul frecventa

Spor la lucru! Daca aveti intrebari nu ezitati sa le lasati in comentarii, va vom raspunde cat de repede putem 🙂

Citirea si afisarea cu ajutorul fisierelor C++

Citirea normala, cu ajutorul functiei cin, necesita ca datele de intrare sa fie introduse prin intermediul tastaturii, la rularea programului. Unele probleme, insa, doresc implementarea citirii cu ajutorul unui fisier extern. Pentru a realiza acest lucru trebuie folosita o variabila care va functiona similar cu functia cin, pe parcursul programului. Astfel, inainte de inceperea citirii trebuie deschis fisierul din care vrem sa citim si atribuit unei variabile de citire. Acest lucru se realizeaza cu structura ifstream.

Observatie!! Pentru a citi/afisa cu ajutorul fisierelor la inceputul programului trebuie inclusa biblioteca fstream. (#include <fstream>).

Structura operatiei de deschidere: ifstream numeVariabilaCitire(“numeFisier”);

Deschidere fisier de citire:

Dupa ce a fost deschis fisierul, putem folosi variabila prin care l-am deschis pentru a citi din acesta.

Structura operatie de citire : numeVariabilaCitire>> (similara functiei cin)

Exemplu de citire din fisier:

Afisarea intr-un fisier se face in mod asemanator functiei cout printr-o variabila de afisare. Inainte de efectuarea afisarii, trebuie mai intai deschis fisierul in care vrem sa afisam si atribuit unei variabile de afisare. Acest lucru se realizeaza cu structura ofstream.

Structura operatiei de afisare : ofstream numeVariabilaAfisare(“numeFisier”);

Deschidere fisier de afisare:

Dupa ce a fost deschis fisierul, putem folosi variabila prin care l-am deschis pentru a afisa in acesta.

Structura operatiei de afisare:  numeVariabilaAfisare<< (similara functiei cout)

Exemplu afisare in fisier:

Intr-un program se pot combina cele doua procese si putem citi dintr-un fisier si sa afisam in altul.

Exemplu de problema in care folosim citirea si afisarea din fisiere:

Sa se afiseze in fiserul ‘paritate.txt’, toate numerele pare din fisierul ‘input.txt’.Fisierul ‘input.txt’ contine numere intregi separate prin spatiu. Numerele trebuie afisate pe linii diferite.

Am deschis cele doua fisiere externe necesare(ifstream si ofstream). Dupa care, am citit din fisier (f>>a) numere, pana cand am ajuns la sfarsitul acestuia (while (f>>a) se opreste cand ajungem la sfarsitul fiserului retinut in f).Daca numarul citit este par il afisam in fisierul retinut in g (g<<a).

Spor la lucru! Daca aveti intrebari nu ezitati sa le lasati in comentarii, va vom raspunde cat de repede putem 🙂

Teorie subprograme C++

Subprogramele reprezinta functii definite de catre utilizator. Ele sunt identificate prin nume si pot fi apelate in interoriul unui program.

Un subprogram (o functie) are forma urmatoare:

Subprogramele se scriu inainte de functia “int main()”.

Spre exemplu, in problema de mai jos, (pe care o puteti gasi si aici), avem un subprogram cu numele “cifreImpare” (intre liniile 4 si 19). Acesta are doar un parametru formal – n, de tipul int.

Antetul acestui subprogram este “int cifreImpare(int n)”.

Putem observa de asemenea cum acesta este apelat in interiorul functiei int main() (linia 24). Astfel, variabila n citita la linia 23, este prelucrata de catre subprogramul cifreImpare.

In cazul subprogramelor trebuie sa facem distinctie intre variabilele locale si variabilele globale din programul pe care il cream.

Variabilele globale sunt variabile ce pot fi utilizate in interiorul oricarei functii din program. Variabilele globale se declara la inceputul programului inainte de declararea oricarei functii. Concret, in cazul nostru, variabila globala n declarata la linia 3, poate fi utilizata si in functia cifreImpare precum si in functia main.

Variabilele locale sunt variabile ce pot fi utilizate doar in interiorul unei anumite functii. Variabilele locale se declare in interiorul unei functii. Concret, in cazul nostru, regasim variabilele locale la linia 6, ele putand fi utilizate doar in functia cifreImpare. 

Ar fi ineficient din punct de vedere al memoriei folosite de catre program daca variabilele locale folosite doar in functia cifreImpare ar fi declarate ca variabile globale.

Exista 2 tipuri de apel al subprogramelor:

1. Apel prin valoare = se transmite o copie a parametrului. Astfel, in urma parcurgerii intructiunilor din subprogram valoarea parametrului nu a fost schimbata intrucat se prelucreaza o copie a sa.

2. Apel prin referinta = se transmite adresa parametrului. Astfel, in urma parcurgerii instructiunilor din subprogram, valoarea parametrului se schimba intrucat se efectueaza prelucrari direct asupra sa.

Spor la lucru! Daca aveti intrebari nu ezitati sa le lasati in comentarii, va vom raspunde cat de repede putem 🙂