NFORMATICA, curs pentru clasele a IX-a si a X-a (profilul real-intensiv) – Invata limbajul c++ standard!
Include continuturile manualelor pentru clasele a IX-a si a X-a,
respectand programa scolara aflata in vigoare.
Motivul aparitiei prezentului curs este dat de dorinta autorului de a prezenta unitar atat algorimii si structurile de date cerute de programa, cat si limbajul actual C++. Pentru a scapa de constrangerile programei, se pare, gandita mai mult pentru limbajul Pascal, s-a preferat introducerea unor notiuni strict necesare intelegerii limbajului C++. Desigur, cursul poate fi parcurs fara aceste notiuni, ca pana acum, dar… este pacat.
Iata cateva dintre motivele care au determinat aparitia acestui curs:
1) In C/C++ se lucreaza cu functii. Chiar "programul principal" este o functie. In schimb, conform programei scolare, subprogramele se studiaza in clasa a X-a. Pana atunci, elevii trebuie sa foloseasca functii de mai multe ori, cum ar fi, de exemplu, pentru prelucrarea sirurilor de caractere. De asemenea, poate si din perspectiva algoritmilor, ar fi util sa se studieze functiile mai din timp.
Avem o problema pentru care trebuie sa se elaboreze un algoritm. Nu este mai bine ca, mai intai, aceasta sa fie descompusa in subprobleme pentru care, la implementare, sa utilizam functii?
2) Studiul pointerilor si referintelor nu este de neglijat. In absenta acestui studiu, este dificil ca elevii sa inteleaga, de exemplu, functiile care prelucreaza un sir de caractere. Dincolo de utilitate, studiul lor reprezinta un exercitiu excelent de logica.
3) In actuala programa studiul POO se face, optional, in clasa a XII-a. Nu este cam tarziu? Daca ar fi studiata din timp, ma refer la incapsulare, atunci s-ar intelege cum se efectueaza scrierile / citirile in C++. De asemenea, se poate lucra foarte usor cu metodele unei clase numita STRING. Cu ajutorul lor, se prelucreaza cu mult mai simplu sirurile de caractere, ca in Pascal.
4) Studiul limbajului in mediul Borland este dezavantajos. Mai intai pentru ca programul dispune de putina memorie, iar in cazul unui concurs de programare, acesta este un dezavantaj foarte mare. De altfel, nici nu stiu in ce masura mai este permisa participarea la un concurs utilizand mediul Borland. Apoi, pentru ca C++ Standard contine cu mult mai mult decat ce permite cel utilizat in Borland. Cel mai important este faptul ca putem folosi STL-ul. Nu este de negiljat ca exista implementati in limbaj algoritmi de sortare, de identificare a unei subsecvente dintr-un sir, de generare a urmatoarei valori in ordine lexicografica, de utilizare a min sau max Heap-ului, toate in timp optim.
CUPRINS
Capitolul 1. Elemente de baza ale limbajului C++ 3
1. 1. Despre limbajul C++ 3
1. 2. Structura programelor C++ 4
1. 3. Vocabularul limbajului 5
1. 4. Despre variabile 6
1. 5. Citiri, scrieri 7
1. 6. Tipuri de date fundamentale 9
1. 7. Literali 10
1. 8. Expresii 12
1. 8. 1. Generalitati 12
1. 8. 2. Operatori C++ 13
1. 8. 2. 1. Operatori aritmetici 13
1. 8. 2. 2. Operatori relationali 15
1. 8. 2. 3. Operatori de egalitate 16
1. 8. 2. 4. Operatori de incrementare si decrementare 16
1. 8. 2. 5. Operatori logici 17
1. 8. 2. 6. Operatori logici pe biti 18
1. 8. 2. 7. Operatori de atribuire 19
1. 8. 2. 8. Operatorul ',' (virgula) 21
1. 8. 2. 9. Operatorul conditional 21
1. 8. 2. 10. Operatorul sizeof 22
1. 8. 2. 11. Operatorul de conversie explicita 22
Probleme propuse 23
Raspunsuri 26
Capitolul 2. Instructiunile limbajului C++ 27
2. 1. Instructiunea expresie 27
2. 2. Instructiunea IF 28
2. 3. Instructiunea compusa 30
2. 4. Instructiunea SWITCH 30
2. 5. Instructiunea WHILE 31
2. 6. Instructiunea DO WHILE 33
2. 7. Instructiunea FOR 34
2. 8. Instructiunile "BREAK” si "CONTINUE” 37
Probleme propuse 38
Raspunsuri 44
Capitolul 3. Tablouri 45
3. 1. Tablouri in C++ 45
3. 2. Algoritmi fundamentali care lucreaza cu vectori 47
3. 2. 1. Maxim, minim 47
3. 2. 2. Elemente distincte 48
3. 2. 3. Multimi 49
3. 2. 4. Metode de sortare 55
3. 2. 5. Interclasare 60
3. 2. 6. Cautare binara 62
3. 3. Aplicatii cu matrice 63
3. 4. Sortarea fara comparatii 65
Probleme propuse 67
Capitolul 4. Subprograme 73
4. 1. Notiunea de subprogram 73
4. 2. Exemple de utilizare a functiilor 74
4. 3. Structura functiilor si apelul lor 76
4. 3. 1. Generalitati 76
4. 3. 2. Declararea variabilelor 78
4. 3. 3. Transmiterea parametrilor 81
4. 5. Definirea si declararea unui subprogram 84
4. 6. Aplicatii care folosesc subprograme 85
319
4. 7. Functii "matematice" 89
4. 8. Generarea numerelor aleatoare 90
4. 9. Supraincarcarea functiilor 91
4. 10. Functii cu un numar variabil de parametri 92
Probleme propuse 94
Raspunsuri 107
Capitolul 5. Pointeri si referinte 108
5. 1. Pointeri 108
5. 2. Referinte 111
5. 3. Modificatorul "const” 113
5. 4. Legatura intre masive si pointeri 118
5. 5. Operatii cu pointeri 121
5. 6. Expresii indexate 122
5. 7. Pointeri catre functii 124
5. 8. Alocarea dinamica a memoriei 126
5. 9. Parametri pentru program 129
Capitolul 6. Incapsulare – notiuni elementare 130
6. 1. Tipuri create cu STRUCT 130
6. 2. Pointeri catre variabile de un tip creat cu STRUCT 132
Capitolul 7. Clase in C++ 133
7. 1. Clase 133
7. 2. Constructori 138
7. 3. Destructori 139
7. 4. Copierea obiectelor 140
7. 5. Functii prietene 141
7. 6. Supraincarcarea operatorilor cu metode ale clasei. Generalitati 142
7. 7. Supraincarcarea operatorilor prin functii prietene 143
7. 8. Cuvantul cheie "this” 144
7. 9. Despre supraincarcarea unor operatori unari 145
7. 10. Supraincarcarea operatorilor "++” si "–-” 146
7. 11. Supraincarcarea operatorului "=” 148
7. 12. Constructori de copiere 150
7. 13. Supraincarcarea operatorului "[ ]” 151
7. 14. Supraincarcarea operatorului "( )” 152
7. 15. Membri statici ai unei clase 153
7. 16. Tratarea exceptiilor prin utilizarea claselor 154
Capitolul 8. Siruri de caractere 156
8. 1. Notiuni introductive 156
8. 2. Citirea si afisarea sirurilor de caractere 156
8. 3. Siruri de caractere vs. Pointeri 158
8. 4. Functii din limbajul C care lucreaza cu siruri de caractere 159
8. 5. O alta modalitate de lucru cu sirurile de caractere in C++ 169
Probleme propuse 174
Capitolul 9. Fisiere 175
9. 1. Manipulatori 175
9. 2. Notiunea de fisier 176
9. 3. Fisiere text 177
Probleme propuse 184
Capitolul 10. Structuri de date 187
10. 1. Conceptul de structura de date 187
10. 2. Structura de tip lista liniara 188
10. 2. 1. Prezentarea structurii 188
10. 2. 2. Liste alocate secvential 189
10. 2. 3. Liste alocate inlantuit 191
10. 2. 4. Implementarea alocarii inlantuite prin utilizarea vectorilor 191
10. 3. Structura de tip stiva 195
10. 4. Structura de tip coada 199
Probleme propuse 199
Raspunsuri 201
320
Capitolul 11. Introducere in recursivitate 202
11. 1. Prezentare generala 202
11. 2. Modul in care se realizeaza autoapelul 202
11. 3. Mecanismul recursivitatii 203
11. 4. Cum gandim un algoritm recursiv? 205
11. 5. Aplicatii recursive 206
11. 5. 1. Aplicatii la care se transcrie o formula recursiva 206
11. 5. 2. Aplicatii la care nu dispunem de o formula de recurenta 210
Probleme propuse 215
Indicatii / Rezolvari 220
Capitolul 12. Complexitatea algoritmilor 223
12. 1. Exprimarea complexitatii 223
12. 2. Ce trebuie sa mai stim… 227
Probleme propuse 228
Raspunsuri 229
Capitolul 13. Initiere in programarea generica 230
13. 1. Ce este programarea generica? 230
13. 2. Functii "template” 231
13. 3. Clase "template” 233
13. 4. Ce este STL? 236
13. 5. Mai mult despre containere 237
13. 6. Mai mult despre iteratori 238
13. 7. Clase de tip container 240
13. 7. 1. Clasa vector 240
13. 7. 2. Clasa list 246
13. 7. 3. Clasa stack 250
13. 7. 4. Clasa queue 251
13. 7. 5. Clasa set 252
13. 7. 6. Clasa multiset 256
13. 7. 7. Clasa map 258
13. 7. 8. Clasa priority_queue 262
13. 8. Algoritmi 263
13. 8. 1. Algoritmii si predicatele 263
13. 8. 2. Algoritmii si elementele de asociere 266
13. 8. 3. Algoritmul for_each() 267
13. 8. 4. Algoritmi de tip find 269
13. 8. 5. Algoritmi de tip count 270
13. 8. 6. Algoritmi de tip search 271
13. 8. 7. Algoritmi de tip mismatch si equal 273
13. 8. 8. Algoritmi de tip copy 275
13. 8. 9. Algoritmi de tip replace 276
13. 8. 10. Algoritmi de tip remove 277
13. 8. 11. Algoritmi de tip transform 278
13. 8. 12. Algoritmi de tip sort(sortare) 279
13. 8. 13. Cautarea binara 280
13. 8. 14. Ordinea lexicografica 282
13. 8. 15. Partitionare 283
13. 8. 16. Algoritmi de tip fill 284
13. 8. 17. Algoritmi de tip unique 285
Anexa 1. Tabela codurilor ASCII 286
Anexa 2. Baze de numeratie 287
Anexa 3. Cum se memoreaza datele? 297
Anexa 4. Spatii de nume 306
Anexa 5. Un mediu de dezvoltare – MinGW Developer Studio 308
Anexa 6. Cum se citesc / scriu datele in C++? 316
