Curs 1 Algoritmi 03.03.2013 Curs - Programarea Calculatoarelor 8 1. ALGORITMI 1.1. Noţiunea de algoritm 1.2. Reprezentarea unui algoritm 1.3. Concepţia unui algoritm 1.4. Obiectele cu care lucrează algoritmii 1.5. Exemple de algoritmi elementari 03.03.2013 Curs - Programarea Calculatoarelor 9 1.1. Noţiunea de algoritm În procesul de rezolvare a unei probleme folosind calculatorul există două etape: 1. Definirea şi analiza problemei 2. Proiectarea şi implementarea unui algoritm care rezolvă problema 1. Definirea şi analiza problemei poate fi la rândul ei descompusă în: specificarea datelor de intrare specificarea datelor de ieşire 03.03.2013 Curs - Programarea Calculatoarelor 10 1.1. Noţiunea de algoritm Specificarea datelor de intrare constă în: 1. Ce date vor fi primite la intrare 2. Care este formatul (forma lor de reprezentare) datelor de intrare 3. Care sunt valorile permise sau nepermise pentru datele de intrare 4. Există unele restricţii (altele decât la 3) privind valorile de intrare 5. Câte valori vor fi la intrare, sau dacă nu se poate specifica un număr fix de valori, cum se va şti când s- au terminat de introdus datele de intrare 03.03.2013 Curs - Programarea Calculatoarelor 11 1.1. Noţiunea de algoritm Specificarea datelor de ieşire trebuie să ţină cont de următoarele aspecte: 1. Care din valorile rezultate în cursul aplicării algoritmului de calcul, asupra datelor de intrare, vor fi afişate (necesare utilizatorului), în acest pas se face diferenţierea clară între date intermediare şi date de ieşire 2. Care va fi formatul datelor de ieşire (de exemplu un număr real poate fi afişat cu trei sau cu cinci zecimale, sau un text poate fi afişat integral sau parţial) 03.03.2013 Curs - Programarea Calculatoarelor 12 1.1. Noţiunea de algoritm 3. Sunt sau nu necesare explicaţii suplimentare pentru utilizator în afara datelor de ieşire 4. Care este numărul de date de ieşire care trebuie transmise către ieşire 03.03.2013 Curs - Programarea Calculatoarelor 13 1.1. Noţiunea de algoritm O definiţie a noţiunii de algoritm poate fi: înlănţuirea de paşi simpli, operaţii distincte care descriu modul de prelucrare a unor date de intrare în scopul rezolvării unei probleme. Un exemplu simplu de algoritm ar fi suita de operaţii matematice făcută în rezolvarea unei ecuaţii matematice de gradul II: aX2+bX+c=0, coeficienţii a, b, c se schimbă dar modul de procesare a valorilor lor, nu. 03.03.2013 Curs - Programarea Calculatoarelor 14 1.1. Noţiunea de algoritm Proprietăţile unui algoritm sunt: 1. Este compus din instrucţiuni simple şi clare. 2. Operaţiunile specificate de instrucţiuni se execută într-o anumită secvenţă. 3. Soluţia trebuie obţinută într-un număr finit de paşi. Concluzia care rezultă este că: UN ALGORITM ESTE INDEPENDENT DE TIPUL DE LIMBAJ ÎN CARE ESTE TRANSPUS SAU DE TIPUL DE CALCULATOR PE CARE ESTE EXECUTAT. 03.03.2013 Curs - Programarea Calculatoarelor 15 1. ALGORITMI 1.1. Noţiunea de algoritm 1.2. Reprezentarea unui algoritm 1.3. Concepţia unui algoritm 1.4. Obiectele cu care lucrează algoritmii 1.5. Exemple de algoritmi elementari 03.03.2013 Curs - Programarea Calculatoarelor 16 1.2. Reprezentarea unui algoritm În general, un algoritm poate fi considerat ca o descriere a prelucrărilor efectuate asupra unui flux de date, prelucrări care au loc cu un scop bine determinat. Modul de descriere a unui algoritm, este independent de un limbaj de programare, existând două metode clasice: 1. metoda schemei logice 2. metoda pseudocod-ului 03.03.2013 Curs - Programarea Calculatoarelor 17 1.2. Reprezentarea unui algoritm 1. Metoda schemei logice În cadrul acestei metode se foloseşte un set de simboluri, prezentat în figura 1, pentru descrierea paşilor ce trebuie executaţi pentru ca algoritmul rezultat să ne rezolve o anumită problemă. Deşi a fost extrem de folosită, până nu de mult, această metodă a pierdut teren în faţa reprezentării de tip pseudocod, poate şi datorită timpului suplimentar pierdut de utilizator cu executarea simbolurilor grafice. 03.03.2013 Curs - Programarea Calculatoarelor 18 1.2. Reprezentarea unui algoritm 03.03.2013 Curs - Programarea Calculatoarelor 19 Start Bloc de atribuire Bloc citire variabile conditie Stop Bloc scriere variabile Nu Da Figura 1. Reprezentarea algoritmilor prin metoda schemei logice 1.2. Reprezentarea unui algoritm Să analizăm un algoritm de calcul a mediei pentru trei note şi să vedem cum ar apărea descris prin această metodă. 03.03.2013 Curs - Programarea Calculatoarelor 20 Start Citire nota1, nota2, nota3 media 1.2. Reprezentarea unui algoritm 2. Metoda pseudocod-ului Există mai multe variante de limbaje algoritmice, care însă nu diferă esenţial. Am ales forma în care cuvintele cheie sunt în limba română şi operatorii sunt cei uzuali din matematică. Pseudocod-ul are în componenţă mai multe comenzi standard care încep, în general cu un cuvânt cheie care defineşte operaţia de bază din algoritm şi care va fi evidenţiat prin utilizarea aldinelor (cuvintelor îngroşate). 03.03.2013 Curs - Programarea Calculatoarelor 21 1.2. Reprezentarea unui algoritm Comenzilor standard ale pseudocod-ului le corespund instrucţiuni din limbajele de programare, fapt care uşurează implementarea algoritmului în limbaj. 03.03.2013 Curs - Programarea Calculatoarelor 22 1.2. Reprezentarea unui algoritm Comenzile standard de bază ale pseudocod-ului sunt: 1) Comanda de atribuire - are forma: - este comanda care nu conţine cuvinte cheie şi corespunde unei operaţii de atribuire 03.03.2013 Curs - Programarea Calculatoarelor 23 variabilă expresie 1.2. Reprezentarea unui algoritm 2) Comanda de citire - are forma: - este comanda care corespunde unei operaţii de citire 3) Comanda de scriere - are forma: - este comanda care corespunde unei operaţii de scriere 03.03.2013 Curs - Programarea Calculatoarelor 24 citeşte listă de variabile scrie listă de expresii 1.2. Reprezentarea unui algoritm 4) Structura de decizie - are două forme corespunzătoare celor două forme ale structurii alternative (structurii de decizie): 03.03.2013 Curs - Programarea Calculatoarelor 25 dacă condiţie atunci instructiune1 … instructiunen altfel instructiune1 … instructiunen sfârşit dacă 1.2. Reprezentarea unui algoritm A doua formă a structurii de decizie: 03.03.2013 Curs - Programarea Calculatoarelor 26 dacă condiţie atunci instructiune1 … instructiunen sfârşit dacă 1.2. Reprezentarea unui algoritm 5) Structura cât timp - are forma: - corespunde ciclului repetitiv cu test iniţial 03.03.2013 Curs - Programarea Calculatoarelor 27 cât timp condiţie execută instructiune1 … instructiunen sfârşit cât timp 1.2. Reprezentarea unui algoritm 6) Structura repetă până când - are forma: - corespunde ciclului repetitiv cu test final 03.03.2013 Curs - Programarea Calculatoarelor 28 repetă instructiune1 … instructiunen până când condiţie 1.2. Reprezentarea unui algoritm 7) Structura pentru - are forma: - corespunde ciclului repetitiv cu numar cunoscut de pasi 03.03.2013 Curs - Programarea Calculatoarelor 29 pentru variabila 1.2. Reprezentarea unui algoritm 8) Structura de oprire a algoritmului - are forma: 03.03.2013 Curs - Programarea Calculatoarelor 30 stop 1.2. Reprezentarea unui algoritm Reluăm exemplul cu media a trei note pe care îl vom scrie atât cu ajutorul schemelor logice, cât şi cu ajutorul pseudocod-ului. 03.03.2013 Curs - Programarea Calculatoarelor 31 1.2. Reprezentarea unui algoritm real nota1, nota2, nota3, media citeşte nota1, nota2, nota3 media (nota1+nota2+nota3)/3 scrie media stop 03.03.2013 Curs - Programarea Calculatoarelor 32 Start Citire nota1, nota2, nota3 media 1. ALGORITMI 1.1. Noţiunea de algoritm 1.2. Reprezentarea unui algoritm 1.3. Concepţia unui algoritm 1.4. Obiectele cu care lucrează algoritmii 1.5. Exemple de algoritmi elementari 03.03.2013 Curs - Programarea Calculatoarelor 33 1.3. Conceptia unui algoritm Pași necesari: 1. Problema care va fi rezolvată, trebuie citită cu atenţie. 2. Apoi se stabilesc prelucrările care sunt necesare obţinerii rezultatelor dorite. Pentru a crea un algoritm eficient trebuie evidenţiate datele de intrare şi datele de ieşire. 03.03.2013 Curs - Programarea Calculatoarelor 34 1.3. Conceptia unui algoritm 03.03.2013 Curs - Programarea Calculatoarelor 35 Date de intrare Date de ieșire ALGORITM 1. ALGORITMI 1.1. Noţiunea de algoritm 1.2. Reprezentarea unui algoritm 1.3. Concepţia unui algoritm 1.4. Obiectele cu care lucrează algoritmii 1.5. Exemple de algoritmi elementari 03.03.2013 Curs - Programarea Calculatoarelor 36 1.4. Obiectele cu care lucrează algoritmii Obiectele cu care lucrează algoritmii sunt: a) Constante b) Variabile c) Operaţii d) Expresii 03.03.2013 Curs - Programarea Calculatoarelor 37 1.4. Obiectele cu care lucrează algoritmii a) Constantele sunt date de un anumit tip care nu se modifică pe parcursul execuţiei unui algoritm. Pot fi: 1. Constante numerice, adică numere întregi sau reale 2. Constante nenumerice, adică şiruri de caractere cuprinse între apostrofuri 3. Constante logice, adevărat şi fals 03.03.2013 Curs - Programarea Calculatoarelor 38 1.4. Obiectele cu care lucrează algoritmii b) Variabilele sunt date ale căror valori se modifică pe parcursul execuţiei unui algoritm. Ele se utilizează pentru a păstra datele iniţiale, sau pentru a păstra rezultatele parţiale sau finale ale algoritmului. Fiecare variabilă va avea o locaţie de memorie asociată ei, unde i se păstrează valoarea. Variabilele pot: naturale, întregi, reale, logice sau şiruri de caractere. 03.03.2013 Curs - Programarea Calculatoarelor 39 1.4. Obiectele cu care lucrează algoritmii c) Operatorii sunt cei folosiţi uzuali în matematică: 1. Operatori aritmetici 2. Operatori relaţionali 3. Operatori logici Operatori aritmetici Operator Semnificaţie + Adunare - Scădere * Înmulţire / Împărţire Operatori relaţionali < Mai mic Mai mare >= Mai mare sau egal = Egal Diferit Operatori logici not Negaţie si Şi (conjuncţie) sau Sau (disjuncţie) 03.03.2013 Curs - Programarea Calculatoarelor 40 1.4. Obiectele cu care lucrează algoritmii d) Expresiile sunt formate din constante şi variabile legate între ele cu ajutorul operatorilor. Pot fi de mai multe tipuri, în funcţie de tipul operatorilor si a operanzilor: 1. Expresii aritmetice 2. Expresii relaţionale 3. Expresii logice 03.03.2013 Curs - Programarea Calculatoarelor 41 1.4. Obiectele cu care lucrează algoritmii O expresie aritmetică este o expresie care cuprinde: 1. constante 2. variabile 3. sau funcţii aritmetice elementare legate, eventual, prin operatori aritmetici. 03.03.2013 Curs - Programarea Calculatoarelor 42 1.4. Obiectele cu care lucrează algoritmii O expresie relaţională poate fi formată din: Două expresii aritmetice legate printr-un singur operator relaţional (de exemplu: b2 > 4*a*c) Două variabile nenumerice legate printr-un operator relaţional (de exemplu: nume1nume2) O variabilă şi o constantă nenumerice legate printr-un operator relaţional (de exemplu: raspuns=‘da’) 03.03.2013 Curs - Programarea Calculatoarelor 43 1.4. Obiectele cu care lucrează algoritmii O expresie logică cuprinde: 1. constante 2. variabile 3. sau expresii relaţionale legate prin operatori logici a cărei valoare este fie adevărat, fie fals. 03.03.2013 Curs - Programarea Calculatoarelor 44 1.4. Obiectele cu care lucrează algoritmii Condiţiile care apar în algoritmi vor fi întotdeauna exprimate prin expresii relaţionale sau logice. 03.03.2013 Curs - Programarea Calculatoarelor 45 1. ALGORITMI 1.1. Noţiunea de algoritm 1.2. Reprezentarea unui algoritm 1.3. Concepţia unui algoritm 1.4. Obiectele cu care lucrează algoritmii 1.5. Exemple de algoritmi elementari 03.03.2013 Curs - Programarea Calculatoarelor 46 1.5. Exemple de algoritmi elementari Enunţ: Să se calculeze perimetrul şi aria unui triunghi oarecare dacă se cunosc laturile triunghiului. Pas 1: Stabilim care sunt datele de intrare si datele de iesire, adică cele care vor fi prelucrate cu ajutorul algoritmului. În cazul problemei date, avem: Date de intrare: a, b, şi c numere reale ce reprezintă laturile triunghiului. Date de iesire: p = perimetrul si s = aria triunghiului 03.03.2013 Curs - Programarea Calculatoarelor 47 1.5. Exemple de algoritmi elementari Pas 2: Analiza problemei Stabilim condiţiile pe care trebuie să le îndeplinească datele de intrare pentru a fi prelucrate în cadrul algoritmului. În cadrul problemei pe care o avem de rezolvat, cunoaştem formula lui Heron pentru calculul ariei unui triunghi dacă se cunosc laturile sale: unde p reprezintă semiperimetrul triunghiului. 03.03.2013 Curs - Programarea Calculatoarelor 48 ))()(( cpbpappS 1.5. Exemple de algoritmi elementari Pas 3: Scrierea algoritmului în pseudocod: 03.03.2013 Curs - Programarea Calculatoarelor 49 real a, b, c, p, S citeşte a, b, c p a + b + c Scrie ‘Perimetrul triunghiului este ‘, p p p / 2 scrie ‘Aria triunghiului este’, S stop c)b)(pa)(pp(pS 1.5. Exemple de algoritmi elementari Pas 4: Implementarea algoritmului în limbajul de programare dorit - în cazul nostru vom utiliza limbajul C++. Pas 5: Testarea algoritmului pe date de intrare diferite şi verificarea rezultatelor. Ultimii doi paşi îi vom scrie după prezentarea limbajului C++. 03.03.2013 Curs - Programarea Calculatoarelor 50 1.5. Exemple de algoritmi elementari Enunţ: Considerăm ecuaţia de gradul I de forma: ax + b = 0, unde a şi b sunt numere reale. Să se scrie un algoritm care să rezolve ecuaţia dată pentru orice două valori a şi b date. Pas 1: Stabilim care sunt datele de intrare si de iesire, adică cele care vor fi prelucrate cu ajutorul algoritmului. În cazul problemei date, avem: Date de intrare: a, b - numere reale Date de iesire: x - solutia ecuatiei 03.03.2013 Curs - Programarea Calculatoarelor 51 1.5. Exemple de algoritmi elementari Pas 2: Analiza problemei Stabilim condiţiile pe care trebuie să le îndeplinească datele de intrare pentru a fi prelucrate în cadrul algoritmului. Căutăm cazurile particulare. În cadrul problemei pe care o avem de rezolvat, cunoaştem următoarele: Ecuaţia ax+b=0, are solutii reale daca a si b sunt diferite de 0. Cazurile particulare sunt: 1) Daca a = 0, atunci ecuatia data are o infinitate de solutii. 2) Daca a = 0 si b = 0, atunci ecuatia este nedeterminata 3) Daca a ≠ 0 si b ≠ 0, atunci ecuatia are o singura solutie si anume: x = -b/a 03.03.2013 Curs - Programarea Calculatoarelor 52 1.5. Exemple de algoritmi elementari Pas 3: Scrierea algoritmului în pseudocod: 03.03.2013 Curs - Programarea Calculatoarelor 53 real a, b, x citeşte a, b dacă a = 0 atunci scrie ‘Ecuaţia are o infinitate de soluţii’ altfel dacă b = 0 atunci scrie ‘Ecuaţia este nedeterminată’ altfel x - b / a scrie x sfârşit dacă sfarşit dacă stop 1.5. Exemple de algoritmi elementari Pas 4: Implementarea algoritmului în limbajul de programare dorit - în cazul nostru vom utiliza limbajul C++. Pas 5: Testarea algoritmului pe date de intrare diferite şi verificarea rezultatelor. Ultimii doi paşi îi vom scrie după prezentarea limbajului C++. 03.03.2013 Curs - Programarea Calculatoarelor 54 Recapitulare 1. Ce este un algoritm? 2. Cum se pot reprezenta algoritmii? 3. Folosind metoda pseudocod-ului de reprezentare a algoritmilor, cum se reprezintă structura de decizie? 4. Folosind metoda pseudocod-ului de reprezentare a algoritmilor, cum se reprezintă structura repetitivă cu test iniţial? 03.03.2013 Curs - Programarea Calculatoarelor 55 Enunţuri de probleme ce pot fi rezolvate 1. Să se calculeze perimetrul şi aria unui dreptunghi, ştiind laturile sale. 2. Să se calculeze unghiurile(in radiani) unui triunghi, ştiind laturile sale. 03.03.2013 Curs - Programarea Calculatoarelor 56 Întrebări? 03.03.2013 Curs - Programarea Calculatoarelor 57