Algoritmi C++ [PDF]

Zitiervorschau

Algoritmi Algoritmi. Introducere Notiunile cu care opereaza algoritmii Principiile programarii structurate Teorema lui Bohm si Jacopini Aplicatii propuse

http://infoscience.3x.ro/c++.html ALGORITMI. NOTIUNI GENERALE Algoritmul este conceptul fundamental al informaticii. Orice echipament de calcul poate fi considerat o masina algoritmica. Într-o definitie aproximativa algoritmul este un set de pasi care defineste modul în care poate fi dusa la îndeplinire o anumita sarcina. Exemplu de algoritm: algoritmul de interpretare a unei bucti muzicale (descris în partitura). DEFINITII SI CARACTERISTICI Definitie: Algoritmul este un set finit de pasi executabili, descrisi fara echivoc, care solutioneaza o clasa de probleme. Proprietatile fundamentale ale algoritmilor:      

Caracterul finit: orice algoritm bine proiectat se termina într-un numar finit de pasi; Claritatea : algoritmul trebuie descris clar, fara ambiguitati Generalitatea: orice algoritm trebuie sa rezolve toate problemele dintr-o clasa de probleme; Completitudinea-presupune tratarea cazurilor speciale (a exceptiilor) unei probleme. Realizabilitatea: orice algoritm trebuie sa poata fi codificat într-un limbaj de programare; Eficienta- se refera la timpul de executie (in care sunt folosite resursele calculatorului: memorie, procesor) si la spatiul de memorie utilizat. Un algoritm este cu atat mai eficient cu cat spatiul de memorie utilizat este mai mic si numarul de operatii mai putine.

Nerespectarea acestor caracteristici generale conduce la obtinerea de algoritmi neperformanti, posibil infiniti sau nerealizabili.

1

Observatia1. Nu orice problema admite un algoritm de rezolvare. Observatia2. Doi agoritmi sunt echivalenti cand pentru aceleasi date de intrare se obtin aceleasi date de iesire. Etapele rezolvarii unei probleme: -stabilirea cerintelor problemei -stabilirea datelor de intrare si a datelor de iesire -stabilirea unui rationament general de rezolvare a problemei -reprezentarea algoritmului problemei intr-o forma simpla si clara -verificarea rationamentului pentru valori concrete -implementarea algoritmului intr-un limbaj de programare http://infoscience.3x.ro/c++/alg_introducere.html

Notiunile cu care opereaza algoritmii Algoritmii opereaza cu urmatoarele notiuni: Un algoritm prelucreaza datele de intrare in scopul obtinerii unor rezultate (a datelor de iesire) utilizand si date intermediare. Datele sunt valori concrete specifice fiecarei probleme care vor fi retinute de calculator in anumite zone de memorie. Dimensiunea zonelor de memorie depinde de tipul datelor respective. Intuitiv, memoria poate fi reprezentata ca locatii succesive (zone de memorie) identificate prin adrese (numere de ordine). Programatorul are sarcina de a gandi algoritmul unei probleme si de a utiliza cat mai eficient memoria. În program datele apar fie sub forma unor constante (valori cunoscute anticipat, care nu se modifica pe parcursul executiei), fie sub forma de variabile. Constantele si variabilele sunt obiectele informationale de baza manipulate într-un program. Putem defini o variabila ca fiind un nume dat unei zone de memorie. Datele se caracterizeaza printr-un anumit tip care va determina : -o anumita multime din care data poate lua valori - un anumit mod de reprezentare în memoria calculatorului - o multime de operatori care pot fi aplicati acestor valori. - tipul unei date determina lungimea zonei de memorie ocupata de acea data. În general, lungimea zonei de memorare este dependenta de calculatorul pe care s-a implementat compilatorul. Datele se pot clasifica dupa tipul lor in:  Caractere  Intregi  Reale  Logice 2

 Sir de caractere -variabilele: retin date de un tip anume. O variabila isi poate schimba valoarea dar tipul nu. O variabila pentru a fi prelucrata trebuie sa fie declarata (anuntata). Acest lucru consta de fapt in precizarea tipului variabilei. Exemplu: caracter car intreg a real b,c logic x sir y - expresii: o expresie este alcatuita din unul sau mai multi operanzi legati intre ei prin operatori. Operanzii pot fi constante sau variabile. Exemplu: 4.5+2*a unde 4.4, 2, a sunt operanzi iar + si * sunt operatori Expresiile pot interveni cel mai adesea in instructiuni de atribuire de tipul: variabila expresie Exemplu: c 2*b-1 Operatori pentru tipuri numerice : operator + * / %

semnificatie adunare scadere inmultire catul impartirii restul impartirii

Operatori relationali : operator =

> >=