Informatica. Curs pentru clasele a 9-a si a 10-a (profilul real-intensiv)

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