INFORMATICA, Manual pentru clasa a 11-a. Profilul real, neintensiv. Pascal si C++

Materialul este aprobat prin Ordinul MEdC nr. 4446 din 19. 06. 2006 si trateaza materia in ambele limbaje simultan – Pascal si C++.

Manualul scolar este structurat in noua capitole:

Capitolul 1. Tablouri

Capitolul 2. Subprograme

Capitolul 3. Siruri de caractere

Capitolul 4. Structuri de date neomogene

Capitolul 5. Structuri de date

Capitolul 6. Introducere in recursivitate

Capitolul 7. Metoda Divide et Impera

Capitolul 8. Metoda Backtracking

Capitolul 9. Grafuri

Anexa 1. Memento

Anexa 2. Aplicatii practice ale grafurilor

Anexa 3. Codul ASCII

La acest manual a colaborat d-na prof. Rodica Pintea.

Cuprins

Capitolul 1. Tablouri ………… 7

1. 1. Notiunea de tablou ….. 7

1. 2. Cum citim si cum afisam un tablou bidimensional?……………… 8

1. 3. Aplicatii cu tablouri bidimensionale.. 10

Probleme propuse……….. 16

Raspunsurile la testele grila…………….. 19

Capitolul 2. Subprograme … 20

2. 1. Notiunea de subprogram …………. 20

2. 2. Subprograme in Pascal… 22

2. 2. 1. Un exemplu de utilizare a functiilor… 22

2. 2. 2. Un exemplu de utilizare a procedurilor… 24

2. 2. 3. Structura unui subprogram… 25

2. 2. 3. 1. Structura subprogramelor de tip functie… 25

2. 2. 3. 2. Structura subprogramelor de tip procedura… 26

2. 2. 4. Definirea si declararea unui subprogram… 27

2. 2. 5. Apelul subprogramelor… 30

2. 2. 5. 1. Apelul functiilor… 30

2. 2. 5. 2. Apelul procedurilor… 31

2. 2. 5. 3. Transmiterea parametrilor la apel… 31

2. 2. 5. 4. Cum memoreaza subprogramele parametrii trimisi?… 33

2. 2. 5. 5. Transmiterea parametrilor prin valoare… 33

2. 2. 5. 6. Transmiterea parametrilor prin referinta… 35

2. 2. 6. Variabile locale si globale… 36

2. 2. 7. Greseli frecvente… 38

2. 2. 8. Unitati de program… 39

2. 3. Subprograme in C++… 42

2. 3. 1. Exemple de utilizare a functiilor… 42

2. 3. 2. Structura unei functii… 44

2. 3. 3. Declararea variabilelor… 46

2. 3. 4. Transmiterea parametrilor… 49

2. 3. 5. Definirea si declararea unui subprogram… 53

2. 4. Aplicatii care folosesc subprograme… 55

Probleme propuse……….. 62

Raspunsuri…….………….. 72

Capitolul 3. Siruri de caractere …………… 73

3. 1. Generalitati …………. 73

3. 2. Siruri de caractere in Pascal………. 74

3. 2. 1. Notiuni introductive… 74

3. 2. 2. Concatenarea sirurilor… 76

4 Cuprins

3. 2. 3. Compararea sirurilor… 77

3. 2. 4. Lungimea sirurilor de caractere… 79

3. 2. 5. Subsiruri… 80

3. 2. 6. Conversii de la siruri la valori numerice si invers… 84

3. 2. 7. Citirea si scrierea datelor de tip String din si in fisiere text… 88

3. 3. Siruri de caractere in C++…………. 89

3. 3. 1. Generalitati………… 89

3. 3. 2. Citirea si scrierea sirurilor de caractere… 89

3. 3. 3. Tipul char*… 92

3. 3. 4. Lungimea unui sir de caractere… 93

3. 3. 5. Copierea si concatenarea sirurilor de caractere… 94

3. 3. 6. Cautarea unui caracter intr-un sir… 95

3. 3. 7. Compararea sirurilor… 97

3. 3. 8. Subsiruri… 99

3. 3. 9. Alte functii utile in prelucrarea sirurilor… 101

3. 3. 10. Conversia sirurilor in valori numerice si invers… 104

3. 3. 11. Citirea si scrierea sirurilor de caractere din si in fisiere text… 108

3. 3. 11. 1. Operatia de citire… 108

3. 3. 11. 2. Operatia de scriere… 109

3. 3. 12. O modalitate de conversie de la sir la alt tip… 109

Probleme propuse……… 110

Capitolul 4. Structuri de date neomogene …………… 112

4. 1. Notiuni introductive.. 112

4. 2. Structuri neomogene in Pascal….. 112

4. 2. 1. Tipul Record……… 112

4. 2. 2. Accesul simplificat la campuri… 114

4. 2. 3. Inregistrari imbricate… 115

4. 2. 4. Vectori de inregistrari… 115

4. 2. 5. Inregistrare cu variante… 116

4. 3. Structuri neomogene in C++….…. 118

4. 3. 1. Tipul struct……… 118

4. 3. 2. Inregistrari imbricate… 120

4. 3. 3. Inregistrari cu structura variabila… 121

Probleme propuse……… 123

Capitolul 5. Structuri de date …………… 124

5. 1. Conceptul de structura de date….. 124

5. 2. Structura de tip lista liniara……….. 126

5. 2. 1. Prezentarea structurii… 126

5. 2. 2. Liste alocate secvential… 127

5. 2. 3. Liste alocate inlantuit… 128

5. 2. 4. Implementarea alocarii inlantuite prin utilizarea vectorilor… 129

5. 3. Structura de tip stiva…………..….. 133

5. 4. Structura de tip coada…………….. 138

Probleme propuse……… 138

Raspunsuri…….………… 140

Manual de informatica pentru clasa a XI-a 5

Capitolul 6. Introducere in recursivitate 141

6. 1. Prezentare generala 141

6. 2. Modul in care se realizeaza autoapelul….………141

6. 2. 1. Realizarea autoapelului in Pascal… 141

6. 2. 2. Realizarea autoapelului in C++… 142

6. 3. Mecanismul recursivitatii….……… 143

6. 4. Cum gandim un algoritm recursiv?………………. 147

6. 5. Aplicatii recursive………………… 148

6. 5. 1. Aplicatii la care se transcrie o formula recursiva… 148

6. 5. 2. Aplicatii la care nu dispunem de o formula de recurenta… 153

Probleme propuse……… 159

Indicatii / Rezolvari…………….………. 166

Capitolul 7. Metoda Divide et Impera … 172

7. 1. Prezentare generala 172

7. 2. Aplicatii …………….. 172

7. 2. 1. Valoarea maxima dintr-un vector… 172

7. 2. 2. Sortarea prin interclasare… 174

7. 2. 3. Sortarea rapida… 176

7. 2. 4. Turnurile din Hanoi… 179

7. 2. 5. Problema taieturilor… 180

7. 3. Fractali …………….. 183

7. 3. 1. Elemente de grafica… 183

7. 3. 1. 1. Generalitati (varianta Pascal)… 183

7. 3. 1. 2. Generalitati (varianta C++)… 185

7. 3. 1. 3. Setarea culorilor si procesul de desenare (Pascal si C++)… 186

7. 3. 2. Curba lui Koch pentru un triunghi echilateral… 188

7. 3. 3. Curba lui Koch pentru un patrat… 191

7. 3. 4. Arborele… 193

Probleme propuse……… 195

Raspunsuri……………… 196

Capitolul 8. Metoda Backtracking ……… 199

8. 1. Prezentarea metodei …………….. 199

8. 1. 1. Cand se utilizeaza metoda backtracking?… 199

8. 1. 2. Principiul ce sta la baza metodei backtracking… 199

8. 1. 3. O modalitate de implementare a metodei backtracking… 201

8. 1. 4. Problema celor n dame… 204

8. 2. Mai putine linii in programul sursa. 207

8. 3. Cazul in care se cere o singura solutie. Ex.: problema colorarii hartilor……. 210

8. 4. Aplicatii ale metodei backtracking in combinatorica…………… 212

8. 4. 1. O generalizare utila… 212

8. 4. 2. Produs cartezian… 213

8. 4. 3. Generarea tuturor submultimilor unei multimi… 215

8. 4. 4. Generarea combinarilor… 217

6 Cuprins

8. 4. 5. Generarea aranjamentelor… 219

8. 4. 6. Generarea tuturor partitiilor multimii {1, 2,…, n}… 221

8. 5. Alte tipuri de probleme care se rezolva prin utilizarea metodei backtracking…. 223

8. 5. 1. Generalitati… 223

8. 5. 2. Generarea partitiilor unui numar natural… 224

8. 5. 3. Plata unei sume cu bancnote de valori date… 226

8. 5. 4. Problema labirintului… 228

8. 5. 5. Problema bilei… 231

8. 5. 6. Saritura calului… 233

Probleme propuse……… 235

Indicatii…………….……. 238

Capitolul 9. Grafuri ………… 239

9. 1. Grafuri neorientate…………….….. 239

9. 1. 1. Introducere… 239

9. 1. 2. Definitia grafului neorientat… 240

9. 1. 3. Memorarea grafurilor… 242

9. 1. 4. Graf complet… 247

9. 1. 5. Graf partial, subgraf… 248

9. 1. 6. Parcurgerea grafurilor neorientate… 250

9. 1. 6. 1. Parcurgerea in latime (BF – bredth first)… 250

9. 1. 6. 2. Parcurgerea in adancime (DF – depth first)… 253

9. 1. 6. 3. Estimarea timpului necesar parcurgerii grafurilor… 255

9. 1. 7. Lanturi… 255

9. 1. 8. Graf conex… 259

9. 1. 9. Componente conexe… 260

9. 1. 10. Cicluri… 262

9. 1. 11. Arbori… 264

9. 1. 11. 1. Notiunea de arbore… 264

Autor(i): Tudor Sorin, Vlad Tudor (Hutanu)

Format: 16, 5 x 23, 5

Nr. pagini: 320