#1 C++ Algoritmi Adrian · PDF fileExemple de algoritmi elementari 02.11.2016 Programarea...

Programarea calculatoarelor

#1

Adrian Runceanuwww.runceanu.ro/adrian

2016

C++Algoritmi

[email protected]

Obiectivele disciplinei

Obiectivele generale ale disciplinei:1. Cunoaşterea noţiunilor privind algoritmii şi proprietăţile lor2. Reprezentarea algoritmilor prin scheme logice, pseudocod,

programe C++Obiectivele specifice:

1. Pentru curs:

• Cunoaşterea limbajului C++

• Elaborarea de programe în C++

• Analiza şi proiectarea algoritmilor cu ajutorul limbajului de programare C++

2. Pentru aplicații:

• Implementarea unor algoritmi într-un limbaj de programare utilizat pe scară largă – C++

02.11.2016 Programarea Calculatoarelor - curs 2

[email protected]

Câteva precizări

Structura cursului

3 ore curs – titular curs: Lector dr. Adrian Runceanu

2 ore laborator – titular aplicaţii practice: Asist.dr.ing. Alina Cotoi


[email protected]

Câteva precizăriBibliografia necesară cursului:

1. Adrian Runceanu, Mihaela Runceanu, Noțiuni de programare înlimbajul C++, Academica Brâncuşi, Târgu-Jiu, 2012, ISBN 978-973-144-550-2, 483 pagini

2. Adrian Runceanu, Programarea şi utilizarea calculatoarelor,Editura Academică Brâncuși Targu-Jiu, 2003

3. Octavian Dogaru, C++ - Teorie şi practică, volumul I, EdituraMirton, Timişoara, 2004

4. O.Catrina, I.Cojocaru, Turbo C+, Editura Teora, Bucureşti, 19935. D.Costea, Iniţiere în limbajul C, Editura Teora, Bucureşti, 19966. K.Jamsa, C++, Editura Teora,19997. K.Jamsa & L.Klander, Totul despre C si C++, Teora, 2004


[email protected]


[email protected]

Câteva precizări

Referinţele bibliografice nr. 1, 2 şi 3 se potîmprumuta de la Biblioteca Facultăţii de Inginerie, Str.Geneva nr.3, Etaj I – lângă Decanat.

1. Suport curs - varianta electronică disponibilă pe site-ul:

www.runceanu.ro/adrian

2. Îndrumar de laborator - varianta electronică disponibilăpe site pentru fiecare lucrare de laborator.

Notă: Actualizarea site-ului se face săptămânal.02.11.2016 Programarea Calculatoarelor - curs 6

http://www.runceanu.ro/adrian

[email protected]

Câteva precizări

Forme de examinare:

Examen final = 60%Evaluare pe parcursul

semestrului a activităţii de laborator = 30%

Verificare finală lucrări de laborator = 10%


30

1060

Procentaje evaluare

Evaluare pe parcursul semestruluiPrezenta curs si laboratorExamen final

[email protected]

Mod de lucru

Curs:Se prezintă noţiuni teoretice şi exemple de

aplicare practică a acestoraNu ezitaţi să puneţi întrebări

Laborator:Se elaborează şi se depanează programe relativ

simple sau se dezvoltă programe preexistenteSe aplică ceea ce s-a predat la curs


[email protected]

Câteva recomandări

Citiţi cu maximă atenţie enunţurile temelor şirespectaţi-le în totalitate.

Analizaţi în detaliu problema de rezolvat.Identificaţi şi trataţi adecvat toate cazurilespeciale care pot să apară.

Notaţi-vă toate întrebările la care nu aţi găsitsinguri răspunsul şi adresaţi-le cadrelor didactice,la curs sau laborator.


[email protected]

Curs 1Algoritmi


[email protected]

1. ALGORITMI

1.1. Noţiunea de algoritm1.2. Reprezentarea unui algoritm1.3. Concepţia unui algoritm1.4. Obiectele cu care lucrează algoritmii1.5. Exemple de algoritmi elementari


[email protected]

1.1. Noţiunea de algoritm

În procesul de rezolvare a unei probleme folosindcalculatorul există doua etape:

1. Definirea şi analiza problemei2. Proiectarea şi implementarea unui algoritm care

rezolvă problema1. Definirea şi analiza problemei poate fi la rândul ei

descompusă în: specificarea datelor de intrare specificarea datelor de ieşire


[email protected]


Specificarea datelor de intrare constă în:1. Ce date vor fi primite la intrare2. Care este formatul (forma lor de reprezentare) datelor

de intrare3. Care sunt valorile permise sau nepermise pentru

datele de intrare4. Există unele restricţii (altele decât la 3) privind valorile

de intrare5. 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


[email protected]


Specificarea datelor de ieşire trebuie să ţină cont deurmătoarele aspecte:

1. Care din valorile rezultate în cursul aplicării algoritmuluide calcul, asupra datelor de intrare, vor fi afişate(necesare utilizatorului), în acest pas se facediferenţierea clară între date intermediare şi date deieşire

2. Care va fi formatul datelor de ieşire (de exemplu unnumăr real poate fi afişat cu trei sau cu cinci zecimale,sau un text poate fi afişat integral sau parţial)


[email protected]


3. Sunt sau nu necesare explicaţii suplimentarepentru utilizator în afara datelor de ieşire

4. Care este numărul de date de ieşire care trebuietransmise către ieşire


[email protected]


O definiţie a noţiunii de algoritm poate fi:înlănţuirea de paşi simpli, operaţii distincte caredescriu modul de prelucrare a unor date de intrareîn scopul rezolvării unei probleme.

Un exemplu simplu de algoritm ar fi suita deoperaţii matematice făcută în rezolvarea unei ecuaţiimatematice de gradul II:


aX2+bX+c=0, coeficienţii a, b, c se schimbă dar

modul de procesare a valorilor lor, nu

[email protected]


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


[email protected]


Rezolvarea unei probleme este un proces complex, careare mai multe etape:

1. Analiza problemei, pentru a stabili datele de intrare şide ieşire

2. Elaborarea unui algoritm de rezolvare a problemei3. Implementarea algoritmului într-un limbaj de

programare4. Verificarea corectitudinii algoritmului implementat5. Analiza complexitatii algoritmului


[email protected]

1. ALGORITMI



[email protected]

1.2. Reprezentarea unui algoritm

În general, un algoritm poate fi considerat ca odescriere a prelucrărilor efectuate asupra unui flux dedate, prelucrări care au loc cu un scop binedeterminat.

Modul de descriere a unui algoritm, esteindependent de un limbaj de programare, existânddouă metode clasice:

1. metoda schemei logice2. metoda pseudocod-ului


[email protected]


1. Metoda schemei logiceÎn cadrul acestei metode se foloseşte un set de

simboluri, prezentat în figura 1, pentru descriereapaşilor ce trebuie executaţi pentru ca algoritmulrezultat 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ăriide tip pseudocod, poate şi datorită timpuluisuplimentar pierdut de utilizator cu executareasimbolurilor grafice.


[email protected]



Start

Bloc de atribuire

Bloc citire variabile

conditie

Stop

Bloc scriere variabile

Nu Da

Figura 1. Reprezentarea algoritmilor prin metoda schemei logice

[email protected]


Să analizăm unalgoritm de calcul amediei pentru trei noteobținute de un studentîntr-o sesiune deexamene şi să vedemcum ar apărea descrisprin această metodă.


Start

Citire nota1, nota2, nota3

media <-(nota1+nota2+nota3)/3

Scriere media

Stop

[email protected]


2. Metoda pseudocod-ului

Există mai multe variante de limbajealgoritmice, care însă nu diferă esenţial.

Am ales forma în care:cuvintele cheie sunt în limba românăşi operatorii sunt cei uzuali dinmatematică


[email protected]


Pseudocod-ul are în componenţă mai multecomenzi standard care încep, în general cu uncuvânt cheie care defineşte operaţia de bază dinalgoritm şi care va fi evidenţiat prin utilizareaaldinelor (cuvintelor îngroşate).

Comenzilor standard ale pseudocod-ului lecorespund instrucţiuni din limbajele deprogramare, fapt care uşurează implementareaalgoritmului în limbaj.



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


variabilă expresie

[email protected]


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


citeşte listă de variabile

scrie listă de expresii

[email protected]


4) Structura de decizie- are două forme

corespunzătoare celordouă forme alestructurii alternative(structurii de decizie):


dacă condiţie atunciinstructiune1

…instructiunen

altfelinstructiune1

…instructiunen

sfârşit dacă

[email protected]


A doua formă astructurii dedecizie:


dacă condiţie atunciinstructiune1

…instructiunen

sfârşit dacă

[email protected]


5) Structura cât timp- are forma:

- corespunde cicluluirepetitiv cu test iniţial


cât timp condiţie executăinstructiune1

…instructiunen

sfârşit cât timp

[email protected]


6) Structura repetă până când

- are forma:

- corespunde cicluluirepetitiv cu test final


repetăinstructiune1

…instructiunen

până când condiţie

[email protected]


7) Structura pentru- are forma:

- corespunde ciclului repetitiv cu număr cunoscutde pași


pentru variabila<-valoare initiala, valoare finala executa

instructiune1

…instructiunen

sfârşit pentru

[email protected]


8) Structura de oprire a algoritmului

- are forma:


stop

[email protected]


Reluăm exemplul cu media a trei note pecare îl vom scrie atât cu ajutorul schemelorlogice, cât şi cu ajutorul pseudocod-ului.



real nota1, nota2, nota3, mediaciteşte nota1, nota2, nota3media (nota1+nota2+nota3)/3scrie mediastop


Start

Citire nota1, nota2, nota3

media <-(nota1+nota2+nota3)/3

Scriere media

Stop

Se observă că este mult mai uşor să se redacteze un algoritm cu ajutorul pseudocod-ului, decât cu ajutorul schemelor logice.

[email protected]

1. ALGORITMI



[email protected]

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.


[email protected]

1.3. Conceptia unui algoritm


Date de intrare

Date de ieșire

ALGORITM

[email protected]

1. ALGORITMI



[email protected]

1.4. Obiectele cu care lucrează algoritmii

Obiectele cu care lucrează algoritmii sunt:

a) Constanteb) Variabilec) Operaţiid) Expresii


[email protected]


a) Constantele sunt date de un anumit tip care nuse modifică pe parcursul execuţiei unui algoritm.

Pot fi:1. Constante numerice, adică numere întregi sau

reale2. Constante nenumerice, adică şiruri de

caractere cuprinse între apostrofuri3. Constante logice, adevărat şi fals


[email protected]


b) Variabilele sunt date ale căror valori se modificăpe parcursul execuţiei unui algoritm.

Ele se utilizează pentru a păstra dateleiniţiale, sau pentru a păstra rezultatele parţialesau finale ale algoritmului.

Fiecare variabilă va avea o locaţie dememorie asociată ei, unde i se păstreazăvaloarea.

Variabilele pot: naturale, întregi, reale, logicesau şiruri de caractere.


1.4. Obiectele cu care lucreazăalgoritmii

c) Operatorii sunt ceifolosiţi uzuali înmatematică:

1. Operatori aritmetici2. Operatori relaţionali3. Operatori logici

Operatori aritmetici

Operator Semnificaţie

+ Adunare

- Scădere

* Înmulţire

/ Împărţire

Operatori relaţionali

< Mai mic

<= Mai mic sau egal

> Mai mare

>= Mai mare sau egal

= Egal

<> Diferit

Operatori logici

not Negaţie

si Şi (conjuncţie)

sau Sau (disjuncţie)02.11.2016 Programarea Calculatoarelor - curs 43

[email protected]


d) Expresiile sunt formate din constante şi variabilelegate între ele cu ajutorul operatorilor.

Pot fi de mai multe tipuri, în funcţie de tipuloperatorilor si a operanzilor:

1. Expresii aritmetice2. Expresii relaţionale3. Expresii logice


[email protected]


O expresie aritmetică este o expresie carecuprinde:

1. constante2. variabile3. sau funcţii aritmetice elementare legate,

eventual, prin operatori aritmetici.


[email protected]


O expresie relaţională poate fi formată din:Două expresii aritmetice legate printr-un singuroperator relaţional (de exemplu: b2 > 4*a*c)

Două variabile nenumerice legate printr-unoperator relaţional (de exemplu:nume1<>nume2)

O variabilă şi o constantă nenumerice legateprintr-un operator relaţional (de exemplu:raspuns=‘da’)


[email protected]


O expresie logică cuprinde:1. constante2. variabile3. sau expresii relaţionale legate prin operatori

logici a cărei valoare este fie adevărat, fie fals.


[email protected]


Condiţiile care apar în algoritmi vor fiîntotdeauna exprimate prin expresiirelaţionale sau logice.


[email protected]

1. ALGORITMI



[email protected]

1.5. Exemple de algoritmi elementari

Enunţ:Să se calculeze perimetrul şi aria unui triunghi oarecaredacă se cunosc laturile triunghiului.

Pas 1: Stabilim care sunt datele de intrare si datele deiesire, adică cele care vor fi prelucrate cu ajutorulalgoritmului.

Î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



Pas 2: Analiza problemeiStabilim condiţiile pe care trebuie să le

îndeplinească datele de intrare pentru a fiprelucrate în cadrul algoritmului.

În cadrul problemei pe care o avem de rezolvat,cunoaştem formula lui Heron pentru calculul arieiunui triunghi dacă se cunosc laturile sale:

unde p reprezintă semiperimetrul triunghiului.


))()(( cpbpappS


Pas 3: Scriereaalgoritmului în pseudocod:


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

[email protected]


Pas 4: Implementarea algoritmului în limbajul deprogramare dorit - în cazul nostru vom utilizalimbajul C++.

Pas 5: Testarea algoritmului pe date de intrarediferite şi verificarea rezultatelor.

Ultimii doi paşi îi vom scrie dupăprezentarea limbajului C++.


[email protected]


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


[email protected]

1.5. Exemple de algoritmi elementariPas 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 nedeterminata3) Daca a ≠ 0 si b ≠ 0, atunci ecuatia are o singura solutie si

anume:

x = -b/a02.11.2016 Programarea Calculatoarelor - curs 55


Pas 3: Scriereaalgoritmului în pseudocod:


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

[email protected]


Pas 4: Implementarea algoritmului în limbajul deprogramare dorit - în cazul nostru vom utilizalimbajul C++.

Pas 5: Testarea algoritmului pe date de intrarediferite şi verificarea rezultatelor.

Ultimii doi paşi îi vom scrie dupăprezentarea limbajului C++.


[email protected]

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ă cutest iniţial?


[email protected]

Enunţuri de probleme ce pot fi rezolvate

1. Să se calculeze perimetrul şi aria unuidreptunghi, ştiind laturile sale.

2. Să se calculeze unghiurile(in radiani) unuitriunghi, ştiind laturile sale.


[email protected]

Întrebări?


#1 C++ Algoritmi Adrian · PDF fileExemple de algoritmi elementari 02.11.2016 Programarea...

Documents

Transcript of #1 C++ Algoritmi Adrian · PDF fileExemple de algoritmi elementari 02.11.2016 Programarea...