Informatica, Manual pentru clasa a X-a, profilul real-intensiv. Pascal si C++ - Sorin Tudor

Materialul contine conform noii programe scolare urmatoarele capitole:

\"Alocarea dinamica a memoriei\"

\"Structuri de date alocate dinamic\"

\"Metoda Divide et Impera\"

Materia este tratata utilizand ambele limbaje de programare simultan - Pascal si C++.

Clasa a X-a

Filiera teoretica, profil real, Specializarile: Matematica-Informatica,

Intensiv Informatica

Filiera vocationala, profil militar, Specializarile: Matematica-Informatica,

Intensiv Informatica

Cuprins

Capitolul 1. Subprograme …………… 7

1. 1. Notiunea de subprogram …. 7

1. 2. Subprograme in Pascal... 9

1. 2. 1. Un exemplu de utilizare a functiilor... 9

1. 2. 2. Un exemplu de utilizare a procedurilor... 11

1. 2. 3. Structura unui subprogram... 12

1. 2. 3. 1. Structura subprogramelor de tip functie... 12

1. 2. 3. 2. Structura subprogramelor de tip procedura... 13

1. 2. 4. Definirea si declararea unui subprogram... 14

1. 2. 5. Apelul subprogramelor... 17

1. 2. 5. 1. Apelul functiilor... 17

1. 2. 5. 2. Apelul procedurilor... 18

1. 2. 5. 3. Transmiterea parametrilor la apel... 18

1. 2. 5. 4. Cum memoreaza subprogramele parametrii trimisi?... 20

1. 2. 5. 5. Transmiterea parametrilor prin valoare... 21

1. 2. 5. 6. Transmiterea parametrilor prin referinta... 22

1. 2. 6. Variabile locale si globale... 23

1. 2. 7. Greseli frecvente... 25

1. 2. 8. Unitati de program... 26

1. 3. Subprograme in C++... 29

1. 3. 1. Exemple de utilizare a functiilor... 29

1. 3. 2. Structura unei functii... 31

1. 3. 3. Declararea variabilelor... 33

1. 3. 4. Transmiterea parametrilor... 36

1. 3. 5. Definirea si declararea unui subprogram... 40

1. 4. Aplicatii care folosesc subprograme... 42

Probleme propuse……………….. 49

Raspunsuri...….. 59

Capitolul 2. Siruri de caractere ……… 60

2. 1. Generalitati. 60

2. 2. Siruri de caractere in Pascal61

2. 2. 1. Notiuni introductive... 61

2. 2. 2. Concatenarea sirurilor... 64

2. 2. 3. Compararea sirurilor... 65

2. 2. 4. Lungimea sirurilor de caractere... 66

4 Cuprins

2. 2. 5. Subsiruri... 67

2. 2. 6. Conversii de la siruri la valori numerice si invers... 71

2. 2. 7. Citirea si scrierea datelor de tip String din si in fisiere text... 75

2. 3. Siruri de caractere in C++…. 76

2. 3. 1. Generalitati………... 76

2. 3. 2. Citirea si scrierea sirurilor de caractere... 76

2. 3. 3. Tipul char*……………... 79

2. 3. 4. Lungimea unui sir de caractere... 80

2. 3. 5. Copierea si concatenarea sirurilor de caractere... 81

2. 3. 6. Cautarea unui caracter intr-un sir... 82

2. 3. 7. Compararea sirurilor... 84

2. 3. 8. Subsiruri... 86

2. 3. 9. Alte functii utile in prelucrarea sirurilor... 88

2. 3. 10. Conversia sirurilor in valori numerice si invers... 91

2. 3. 11. Citirea si scrierea sirurilor de caractere din si in fisiere text... 95

2. 3. 11. 1. Operatia de citire... 95

2. 3. 11. 2. Operatia de scriere... 96

2. 3. 12. O modalitate de conversie de la sir la alt tip... 96

Probleme propuse………………97

Capitolul 3. Structuri de date neomogene ………… 99

3. 1. Notiuni introductive……….. 99

3. 2. Structuri neomogene in Pascal…………….. 99

3. 2. 1. Tipul Record...…... 99

3. 2. 2. Accesul simplificat la campuri... 101

3. 2. 3. Inregistrari imbricate... 102

3. 2. 4. Vectori de inregistrari... 102

3. 2. 5. Inregistrare cu variante... 103

3. 3. Structuri neomogene in C++….……………. 105

3. 3. 1. Tipul struct...…... 105

3. 3. 2. Inregistrari imbricate... 107

3. 3. 3. Inregistrari cu structura variabila... 108

Probleme propuse………………110

Capitolul 4. Structuri de date ……… 111

4. 1. Conceptul de structura de date…………….. 111

4. 2. Structura de tip lista liniara.. 113

4. 2. 1. Prezentarea structurii... 113

4. 2. 2. Liste alocate secvential... 114

4. 2. 3. Liste alocate inlantuit... 115

4. 2. 4. Implementarea alocarii inlantuite prin utilizarea vectorilor... 116

4. 3. Structura de tip stiva…..….. 120

4. 4. Structura de tip coada……….…………..….. 125

Probleme propuse………………125

Raspunsuri...…127

Manual de informatica pentru clasa a X-a 5

Capitolul 5. Alocarea dinamica a memoriei………… 128

5. 1. Generalitati

5. 2. Variabile de tip pointer…………... 129

5. 2. 1. Variabile de tip pointer in Pascal... 129

5. 2. 2. Variabile de tip pointer in C++... 132

5. 3. Alocarea dinamica a memoriei…………….. 135

5. 3. 1. Alocarea dinamica in Pascal... 135

5. 3. 2. Alocarea dinamica in C++... 138

Probleme propuse…………….. 142

Raspunsuri …. 143

Capitolul 6. Structuri de date alocate dinamic …… 144

6. 1. Liste liniare ……………….. 144

6. 2. Liste liniare alocate simplu inlantuit………. 145

6. 2. 1. Prezentare generala………………. 145

6. 2. 2. Crearea si afisarea listelor…………145

6. 2. 3. Operatii asupra unei liste liniare….. 149

6. 2. 4. Aplicatii ale listelor liniare…………. 155

6. 2. 4. 1. Sortarea prin insertie... 155

6. 2. 4. 2. Sortarea topologica... 157

6. 2. 4. 3. Operatii cu polinoame... 162

6. 3. Liste liniare alocate dublu inlantuit…………171

6. 3. 1. Crearea unei liste liniare alocata dublu inlantuit….. 171

6. 3. 2. Adaugarea unei inregistrari la dreapta…..…………172

6. 3. 3. Adaugarea unei inregistrari la stanga…..…………….………………. 172

6. 3. 4. Adaugarea unei inregistrari in interiorul listei……... 172

6. 3. 5. Stergerea unei inregistrari din interiorul listei……... 173

6. 3. 6. Stergerea unei inregistrari la stanga/dreapta listei……….…………. 174

6. 3. 7. Listarea de la stanga la dreapta listei………..……... 174

6. 3. 8. Listarea de la dreapta la stanga listei ……..………. 174

6. 4. Liste circulare …………….. 177

6. 5. Stiva implementata ca lista liniara simplu inlantuita………... 177

6. 6. Coada implementata ca lista liniara simplu inlantuita………178

Probleme propuse………………180

Raspunsuri la testele grila…….. 185

Capitolul 7. Introducere in recursivitate …………… 186

7. 1. Prezentare generala ………

7. 2. Modul ia….…

7. 2. 1. Realizarea autoapelului iiat…. 188

7. 4. Cum gandim un algoritm recursiv?……...…. 192

7. 5. Aplicatii recursive……...……………..………193

7. 5. 1. Aplicatii la care se transcrie o formula recursiva... 193

7. 5. 2. Aplicatii la care nu dispunem de o formula de recurenta... 198

Probleme propuse………………204

Indicatii / Rezolvari…………….. 211

6 Cuprins

Capitolul 8. Metoda Divide et Impera ……………… 217

8. 1. Prezentare generala………217

8. 2. Aplicatii…. 217

8. 2. 1. Valoarea maxima dintr-un vector…217

8. 2. 2. Sortarea prin interclasare………………..………….. 219

8. 2. 3. Sortarea rapida…. 221

8. 2. 4. Turnurile din Hanoi224

8. 2. 5. Problema taieturilor……………….. 225

8. 3. Fractali….. 228

8. 3. 1. Elemente de grafica………………. 228

8. 3. 1. 1. Generalitati (varianta Pascal)... 228

8. 3. 1. 2. Generalitati (varianta C++)... 230

8. 3. 1. 3. Setarea culorilor si procesul de desenare... 231

8. 3. 2. Curba lui Koch pentru un triunghi echilateral..……. 233

8. 3. 3. Curba lui Koch pentru un patrat..…236

8. 3. 4. Arborele…………. 238

Probleme propuse…………….. 240

Raspunsuri……241

Capitolul 9. Complexitatea algoritmilor …………… 243

9. 1. Exprimarea complexitǎtii …243

9. 2. Ce trebuie sǎ mai stim? …248

Probleme propuse …………….. 248

Rǎspunsuri …... 250

Anexa 1. Memento … 251

A. 1. Limbajul Pascal ………………. 251

A. 1. 1. Tipuri standard ………………. 251

A. 1. 2. Constante …. 252

A. 1. 3. Operatori ….. 252

A. 1. 3. 1. Prioritatea operatorilor... 252

A. 1. 3. 2. Operatori aritmetici... 253

A. 1. 3. 3. Operatori relationali... 254

A. 1. 3. 4. Operatori logici... 254

A. 1. 4. Instructiuni ….……………….. 255

A. 1. 5. Cateva functii utile ………….. 258

A. 2. Limbajul C++. 260

A. 2. 1. Tipuri standard ………………. 260

A. 2. 2. Constante …. 260

A. 2. 3. Operatori ….. 262

A. 2. 3. 1. Prioritatea operatorilor... 262

A. 2. 3. 2. Operatori aritmetici... 262

A. 2. 3. 3. Operatori relationali... 263

A. 2. 3. 4. Operatori de egalitate... 263

A. 2. 3. 5. Operatori de incrementare si decrementare... 264

A. 2. 3. 6. Operatori logici... 264

A. 2. 3. 7. Operatori logici pe biti... 264

A. 2. 3. 8. Operatori de atribuire... 265

A. 2. 3. 9. Operatorul “,”... 266

A. 2. 3. 10. Operatorul conditional... 266

A. 2. 3. 11. Operatorul “sizeof”... 267

A. 2. 3. 12. Operatorul de conversie explicitǎ... 267

A. 2. 4. Instructuni …. 267

A. 2. 5. Caeva functi utile ……………269