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

Description

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