INFORMATICA pentru BAC (varianta C)
Cursul parcurge toată tematica examenului de bacalaureat la discipline INFORAMATICA, varianta de limbaj C
Cursul parcurge toată tematica examenului de bacalaureat la discipline INFORAMATICA, varianta de limbaj C
1.1. Noţiunea de algoritm, caracteristici
1.2. Date, variabile, expresii, operaţii
1.3. Structuri de bază (liniară, alternativă şi repetitivă)
1.4. Descrierea algoritmilor (programe pseudocod)
2.1. Vocabularul limbajului C. Identificatori în C
2.2. Constante în C
2.3. Tip de dată. Operatori aritmetici, logici, relaţionali în C
2.4. Definirea tipurilor de date simple în C
2.5. Variabile. Declararea variabilelor în C
2.6. Mediul de programare C
2.7. Expresii. Instrucțiuni de atribuire în C
2.8. Instrucțiuni de intrare/ieșire în C
2.9. Instrucțiuni pentru descrierea structurilor de control în C
2.10. Tipuri de date structurate în C
2.11. Fișiere de tip text în C
Unitatea de învățare conține teme ce se propun spre rezolvare în vederea fixării cunoștințelor de programare de bază în C / C++
Vă recomandăm:
1. Rezolvați problemele propuse prin introducerea în mediul de lucru C a programului C corespunzător
2. Testați programul
3. Atașați fișierul sursă (cpp sau bak) după apelarea temei
4. Vizualizați și rezolvarea propusă de către autor.
4.1. Probleme care operează asupra cifrelor unui număr
4.2. Divizibilitate. Numere prime. Algoritmul lui Euclid
4.3. Şirul lui Fibonacci. Calculul unor sume cu termenul general dat
4.4. Determinare minim/maxim
4.5. Metode de ordonare (metoda min/max, bulelor, inserţiei)
4.6. Interclasare
4.7. Metode de căutare (secvenţială, binară)
4.8. Analiza complexităţii unui algoritm (considerând criteriile de eficienţă durata de executare şi spaţiu de memorie utilizat)
5.1. Funcţii utilizator în C
– declarare şi apel
– parametri formali şi parametri efectivi
– parametri transmişi prin valoare, parametri transmişi prin referinţă
– variabile globale şi variabile locale, domeniu de vizibilitate
5.2. Proiectarea modulară a rezolvării unei probleme
6.1. Prezentare generală
6.2. Utilizarea funcțiilor recursive în C / C++
Calculăm n!
Se observă ca n!=(n-1) !*n și se știe ca 0 !=1. Așadar :
5 !=4 !*5
4 !=3 !*4
3 !=2 !*1
1 !=0 !*1
0 !=1 (prin conventie matematica)
Definitia recursiva a lui n ! este :
n! = n * (n-1)! dacă n>0
0! = 1
Funcția recursivă se va scrie astfel:
long fac(int n)
{if(n==0) return 1;
else return fac(n-1)*n;}
void main()
{cout<<"5!="<<fac(5) ;}
Se observă ca functia fac se autoapelează. Autoapelul se realizează prin instructiunea return fac(n-1)*n.
Să revedem mecanismul prin care subprogramele se pot autoapela. Se știe ca la apelul fiecarui subprogram, se genereaza un nou nivel în segmentul de stiva, corespunzător acelui apel. Pe acel nivel se memoreaza :
- valorile parametrilor transmiși prin valoare
- adresele parametrilor transmiși prin referință
- variabilele locale
- adresa de revenire din funcție
In modulul anterior am discutat proprietățile structurii de date numita stivă. Exact aceleași proprietăți are și segmentul de stivă, numai ca acesta este gestionat automat de către calculator, nu de către programator. De fiecare dată când o funcție se autoapelează, se creează un nou nivel în segmentul de stivă.
Cele trei programe solicitate prin temă sunt atașate!!!
7.1. Prezentare generală
7.2. Probleme rezolvate prin utilizarea metodei backtracking iterativ sau recursiv
8.1. Permutări, aranjamente, combinări
8.2. Produs cartezian, submulţimi
9.1 Variabile de tip pointer.
9.2 Alocarea dinamică a memoriei
9.3 Probleme propuse (temă)
10.1 Crearea listelor liniare simplu înlănțuite
10.2 Operații asupra listelor liniare simplu înlănțuite
10.3 Aplicații folosind liste liniare simplu înlănțuite
10.4 Crearea listelor dublu înlănțuite. Operații
10.5 Stiva implementată prin liste liniare simplu înlănțuite
10.6 Coada implementată prin liste liniare simplu înlănțuite
10.7 Probleme propuse (temă)
11. Grafuri
11.1 Grafuri orientate
– terminologie (nod/vârf, arc, adiacenţă, incidenţă, grad intern şi extern, drum, drum elementar, circuit, circuit elementar, lungime, subgraf, graf parţial)
– metode de reprezentare (matrice de adiacenţă, liste de adiacenţă)
– proprietăţi (tare conexitate, componentă tare conexă)
11.2 Grafuri neorientate
– terminologie (nod/vârf, muchie, adiacenţă, incidenţă, grad, lanţ, lanţ elementar, ciclu, ciclu elementar, lungime, subgraf, graf parţial)
– metode de reprezentare (matrice de adiacenţă, liste de adiacenţă)
– proprietăţi (conex, componentă conexă, graf complet, hamiltonian, eulerian)
11.3 Arbori
– terminologie (nod, muchie, rădăcină, descendent, descendent direct/fiu, ascendent, ascendent direct/părinte, fraţi, nod terminal, frunză)
– metode de reprezentare în memorie (matrice de adiacenţă, liste ”de descendenţi”, vector ”de taţi”)