Descriere - Manual de INFORMATICA pentru clasa a XI-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
9.1.11.2. Notiunea de arbore partial............................................... 266
9.2. Grafuri orientate.….. 267
9.2.1. Notiunea de graf orientat.................................................................. 267
9.2.2. Memorarea grafurilor orientate......................................................... 270
9.2.3. Graf partial, subgraf.......................................................................... 272
9.2.4. Parcurgerea grafurilor. Drumuri. Circuite.......................................... 273
9.2.5. Graf tare conex. Componente tare conexe....................................... 275
Probleme propuse……… 278
Raspunsuri……………... 286
Anexa 1. Memento ………… 289
Anexa 2. Aplicatii practice ale grafurilor  309
Anexa 3. Codul ASCII ……… 316



Autori: Tudor Sorin, Vlad Tudor (Hutanu)