Clasa VI/VII/VIII lecția 36 - 28 mai 2013

From Algopedia
Jump to navigationJump to search

Lecție - toate clasele

Limbajul C: pointeri

În acest capitol vom studia conceptul de bază al pointerilor, cu exemple în limbajul C.

Ce sînt pointerii?

Față de variabilele normale care stochează valori, pointerii sînt variabile speciale care păstrează adresa de memorie a altei variabile. De aceea se spune că ei "pointează la variabile".

Orice variabilă în limbajul C are asociate două valori:

  1. Valoarea acelei variabile, de exemplu 54.
  2. Adresa acelei variabile, care este adresa fizică de memorie la care este păstrată valoarea variabilei, de exemplu 1032

În cazul unei variabile pointer, valoarea ei este adresa de memorie a altei variabile.

Cum declarăm pointerii?

Variabilele de tip pointer se declară ca folosind operatorul special '*'. De exemplu: 

int *ptr;

declară o variabilă de tip pointer la int. Variabila ptr va conține adresa unei variabile de tip int. În acest caz asteriscul semnifică tipul pointer.

Exemplu

int n, i, j, *ptr;
n = 54;
i = 22;
j = 31;
ptr = &n;

Despre variabila n:

  1. Numele variabilei: n
  2. Valoarea păstrată de variabilă: 54
  3. Adresa unde este păstrată valoarea variabilei: 1032 (să presupunem)

Despre variabila ptr:

  1. Numele variabilei: ptr
  2. Valoarea păstrată de variabilă: 1032
  3. Adresa unde este păstrată valoarea variabilei: 1044

Figura de mai jos explică grafic reprezentarea situației de mai sus:

Conceptul de pointer exprimat cu adrese și săgeți

Operatori

În lucrul cu pointeri există doi operatori care returnează adresa unei variabile simple, respectiv valoarea de la adresa stocată într-un pointer:

Operator Semnificație Exemplu
& adresa unei variabile int n, *ptr = &n;
* valoarea stocată la o adresă int c = *ptr;

Cei doi operatori sînt aproape inverși. Astfel: 

*&n == n

deoarece valoarea de la adresa de memorie a variabilei n este chiar n, dar 

&*n == n

este incorect, dînd eroare de compilare, deoarece *n este o valoare și nu o variabilă căreia să-i putem extrage adresa de memorie.

Exemplu

Să scriem o funcție care incrementează valoarea unei variabile primite ca parametru: 

void inc( int *ptr ) { // ptr este un pointer la int
  (*ptr)++;            // valoarea de la adresa din ptr se incrementează
}

int main() {
  int n = 10;
  inc( &n );  // trimitem funcției adresa variabilei n si nu valoarea ei
  // in acest moment n are valoarea 11
}

Deoarece limbajul C transmite parametrii funcțiilor numai prin copiere acesta este singurul mod de a modifica valoarea unui parametru și anume să transmitem adresa parametrului de modificat. Un alt exemplu este funcția fscanf: ne aducem aminte că ea trebuie apelată cu &n și nu cu n. Motivul este același și anume faptul că fscanf modifică valoarea variabilei primite ca parametru.

Echivalența între vectori și pointeri

În limbajul C un vector de întregi este totuna cu un pointer la int. Similar, o matrice de întregi este totuna cu un pointer la pointer la int. Astfel, putem scrie următorul program: 

int v[10], *ptr;
ptr = v;

Se spune că variabilele v și ptr au tipuri echivalente, amîndouă fiind de tip pointer la int. Există următoarele diferențe:

  • v este o constantă, pe cînd ptr este o variabilă. Putem să spunem ptr = ptr + 1, pentru a aduna 1 la adresa din ptr, dar nu putem să spunem v = v + 1.
  • În declarația lui v se alocă automat spațiu pentru zece elemente de tip întreg, pe cînd în declarația lui ptr nu se alocă nimic.

Aritmetica pointerilor

Ce se întîmplă cînd adunăm unu la un pointer? Să nu uităm ce reprezintă el: o adresă de memorie. În concluzie adunînd unu vom obține o adresă de memorie mai mare cu unu? Aproape corect. Deoarece pointerii sînt echivalenți cu vectorii, ei putînd fi folosiți efectiv ca vectori, prin adunarea lui unu se consideră că pointerul trebuie să avanseze astfel încît să pointeze la următorul element din vector. De aceea, în CodeBlocks, adunînd 1 la un pointer la int vom aduna în realitate 4, mărimea unui întreg, pentru a "sări" peste acesta. Acest fapt este ilustrat și în figura de mai sus: remarcați că adresele de memorie sînt divizibile cu 4. Similar, dacă adunam i la un pointer, în realitate vom aduna 4i.

Astfel, a spune v[i] este echivalent cu a spune *(v + i). Fun fact: acest lucru înseamnă că în loc de: 

fscanf( fin, "%d", &v[i] );

putem scrie, echivalent: 

fscanf( fin, "%d", v + i );

Alt fun fact: înțelegeți acum ceva mai bine ce înseamnă declarația: 

FILE *fin;

Aceasta înseamnă că declarăm o variabilă de tip pointer la FILE, unde FILE este un tip compus definit in stdio.h.

Alocarea și dealocarea pointerilor

În măsura în care mai avem timp: malloc, free, NULL.

Tehnici de programare: divide at impera

Denumită și divide and conquer sau dezbină și stăpînește, este o tehnică cunoscută de mii de ani conducătorilor. Este o tehnică de cucerire sau menținere a puterii asupra unui grup care ar avea putere mai mare dacă s-ar uni. Ținînd acel grup dezbinat, fiecare facțiune în parte are putere mică și poate fi cucerită, sau condusă. Tehnica a fost aplicată de Cezar, Napoleon, iar, mai recent, de către Britanici în Africa și de către Stalin în Rusia. Dintre tehnicile folosite în lumea reală putem menționa:

  • Ajutorarea și promovarea celor care cooperează cu puterea, pedepsirea celor ce nu cooperează.
  • Încurajarea cheltuielilor prostești, pentru a reduce capitalul disponibil organizării sau luptei.
  • Încurajarea divizării oamenilor pentru a preveni formarea alianțelor.
  • Încurajarea turnătorilor, cei care trîmbițează orice alianță posibil periculoasă.
  • Sădirea de neîncredere între oameni.

O parte din aceste tehnici se regăsesc și în țara noastră, precum și în majoritatea țărilor lumii, inclusiv cele dezvoltate. De exemplu, toate țările lumii folosesc un număr uriaș de taxe și impozite, fiecare din ele relativ mici. Cînd le însumăm constatăm că în jur de 90% din banii noștri se duc pe aceste taxe și impozite. Dacă ar exista o taxă unică de 90%, oamenii s-ar revolta. Astfel, tehnica de împărțire a unor taxe mari în mai multe taxe mici îi face pe oameni să nu le observe și să nu se revolte.

Pentru exemple clasice de folosire a acestei tehnici în lumea reală vizitați pagina de divide at impera a wikipediei.

Tehnica divide et impera

În informatică divide et impera constă în împărțirea problemei în subprobleme mai mici, nesuprapuse (o tehnică în care subproblemele sînt suprapuse este programarea dinamică). Fiecare din aceste subprobleme se rezolvă separat, mai ușor, deoarece sînt mai mici. Rezultatul final se obține din combinația rezultatelor subproblemelor.

Căutare binară

Precum știm, căutarea binară împarte vectorul original în două, apoi decide care din cele două jumătați ar putea să conțină elementul căutat. Apoi rezolvă problema mai mică. Complexitate: O(log n).

Algoritmul lui Euclid

Și acest binecunoscut algoritm poate fi văzut ca un exemplu de divide et impera. El reduce problema de la cmmdc(a, b) la o problemă mai mică, cmmdc(b, a mod b). Complexitate: O(log min(a, b)).

Puzzle

Se dă o grilă de 2n x 2n pătrate din care lipsește un pătrat. Să se acopere cu piese formate din 3 pătrate aranjate în formă de litera L.

Mergesort

Complexitate: O(n log n).

Medianul unui vector

Complexitate: pe medie O(n), în cel mai rău caz O(n2).

Quicksort

Complexitate: pe medie O(n log n), în cel mai rău caz O(n2).

Temă

  • Jocul, în continuare, dacă mai aveți.
  • Puzzle: avem 26 de bile care arată identic, una este ceva mai ușoară. Avem la dispoziție o balanță. Găsiți bila mai ușoară din trei cîntăriri.
  • Ziua regelui: un rege organizează o petrecere mare de ziua lui. Petrecerea începe peste 24 de ore. Regele află că una din cele 1000 de sticle de vin pe care le va servi este otrăvită. Otrava acționează ciudat: omul care bea chiar și cea mai mică cantitate din această otravă nu are nici un simptom vreme de 24 de ore, apoi moare subit. Regele are sclavi la dispoziție pe care îi poate folosi. Lui nu îi pasă cîți sclavi mor, dar îi pasă cîți sclavi beau vin, deoarece un sclav care a băut vin nu poate fi folosit la treabă, ci trebuie izolat spre observare. Care este numărul minim de sclavi cu care regele poate afla sticla otrăvită?
  • Se dă un vector sortat de n elemente întregi distincte. Să se găsească dacă există indicele i astfel încît v[i] == i. Găsiți un algoritm divide et impera care are complexitate O(log n).
  • Problema latin (generare pătrate latine de dimensiune 2n x 2n).

Soluții aici [1]

Retrieved from "https://www.algopedia.ro/wiki/index.php?title=Clasa_VI/VII/VIII_lecția_36_-_28_mai_2013&oldid=6852"