Post on 30-Aug-2019
1
ALGORITMI. NOTIUNI GENERALE
- Într-o definitie aproximativa :
-Algoritmul este conceptul fundamental al informaticii.
- algoritmul reprezinta o succesiune de pasi care poate îndeplini o anumita sarcina in functie de datele de
intrare pt a obtine datele de iesire
- mulţime finită de reguli de calcul care indică operaţiile elementare necesare şi ordinea efectuării lor în
scopul rezolvării unei probleme într-un timp finit
- metodă (procedeu) de rezolvare a unei probleme Observaţii:
1. Oricărei probleme care admite o formulare matematică i se poate asocia un algoritm.
2. Dezvoltarea unui algoritm este, în general, mai dificilă decât scrierea programului sursă pe baza
algoritmului.
Caracteristici fundamentale: Orice algoritm trebuie să îndeplinească cinci caracteristici:
1. generalitate - un algoritm trebuie sa ofere o metodă generală de rezolvare a unui anumit
tip de probleme, pentru date iniţiale arbitrare.
2. precizie (claritate) - descrierea algoritmului trebuie facută fără ambiguităţi, iar
comenzile trebuie să exprime operaţii cunos-cute calculatorului, care pot fi executate
de către procesor.
3. determinare - la fiecare pas, acţiunea care urmează a fi executată trebuie să poată fi
determinată fără echivoc şi unic pe baza acţiunilor precedente.
4. finitudinea - un algoritm trebuie să conducă la obţinerea rezultatelor într-un număr finit
de paşi.
5. eficienţă - un algoritm trebuie să fie construit în aşa fel încât să folosească resurse hard
cât mai puţine şi să necesită un timp minim de execuţie.
6. executabilitate - algoritmul ca întreg şi fiecare pas al său trebuie să poată fi executat.
OBSERVATIE:
1. Nerespectarea acestor caracteristici generale conduce la obtinerea de algoritmi neperformanti,
posibil infiniti sau nerealizabili.
2. 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.
2
Etapele rezolvarii unei probleme:
1 Citirea cerintelor problemei :
(se citesc doua valori ce reprezinta
notele unui elev. Sa se calculeze media
obtinuta de elev)
2 Stabilirea tipurilor datelor de intrare si a datelor de iesire : (Se creeaza locatii de memorie pentru fiecare variabila
declarata)
(intregi (INT), reale(FLOAT), sir de caractere(CHAR))
Ex:
In pseudocod In C++
DI: intregi nota1, nota2;
char nume[10];
DE: real medie;
#include <iostream>
#include <string.h>
using namespace std;
int main()
{
int nota1, nota2;
char nume[10];
float medie;
Citirea (memorarea) datelor de intrare:
In pseudocod In C++
Read nume
Read nota1;
Read nota2;
cout<<”numele elevului: ”; cin>>nume;
cout<<”prima nota: ”; cin>>nota1;
cout<<”a doua nota: ”; cin>>nota2;
3 Stabilirea unui rationament general de rezolvare a problemei
In pseudocod In C++
medie=(nota1+nota2)/2;
4 Afisarea datelor de iesire
In pseudocod In C++
Scrie ”Elevul”, nume, ”a obtinut media=”,medie; cout<<”Elevul ”<< nume<< ” a obtinut media= ”<<medie;
cin.ignore();
cin.get();
return 0;
}
3
5 verificarea rationamentului pentru valori concrete
6 implementarea algoritmului intr-un limbaj de programare ( C++ , codeblocks) si compilare (F9)
Tema:
1. Descrireti algoritmul de tratare a gripei
2. Descrieti algoritmul de rezolvare a unei ecuatii de gradul II : ax2+bx+c=0 , unde a,b,c sunt
numere reale
3. Puneti in evidenta succesiunea pasilor de calculare a mediei semestriale a unui elev , la un
obiect unde sustine teza.
Exista 2 modalitati de reprezentare a algoritmilor:
1. Scheme logice (algoritm in mod grafic folosind blocuri diferite pentru operatii diferite )
-dezavantaje: sunt stufoase si greu de urmarit
-avantaje: utile celor care invata sa programeze si sunt in faza de gandire algoritmica
2. Limbajul pseudocod (este o scriere intermediară, menită să simplifice scrierea unui
algoritm într-un limbaj de programare și să ajute la realizarea clarității algoritmului, în timp
scurt.)
nota1 nota2 medie
5 8 6,5
numele elevului: popescu
prima nota: 5
a doua nota: 8
Elevul popescu a obtinut media 6,5
Ce locatii de memorie se creeaza si ce memoreaza Ce afiseaza pe monitor
4
Descrierea algoritmilor cu ajutorul schemelor logice
În schemele logice, operaţiile de bază din algoritmi sunt reprezemtate prin figuri geometrice,
specifice fiecărui tip de operaţie, legate între ele prin săgeţi pentru a
evidenţia ordinea de execuţie a operaţiilor.
În interiorul figurii se scrie operaţia corespunzătoare, tot acest ansamblu formează un bloc al
schemei logice.
Într-o schemă logică pot să apară blocurile:
Metoda rafinării pas cu pas
- descompunerea unei probleme într-un număr de probleme mai simple care pot fi
Rezolvate pe baza unui algoritm (mai mic mai simplu mai uşor)
Rafinare - detalierea suficientă a fiecărui pas
Exemplu: programarea unui robot să facă ceai
Algoritm iniţial
1. pune frunzele de ceai în vas
2. fierbe apa
3. adaugă apa fiartă în vas
4. aşteaptă 5 minute
5. pune ceaiul în ceaşcă Rafinarea etapei 1.
1.1 deschide cutia de ceai
1.2 scoate o linguriţă de frunze de ceai din cutie
1.3 răstoarnă frunzele din linguriţă în vas 1.4 închide cutia de ceai sau:
2.1 pune apă în fiebător
5
2.2 porneşte fierbătorul
2.3 aşteaptă până când fierbe apa 2.4 opreşte fierbătorul sau:
5.1 pune ceaiul în ceaşcă până când se umple ceaşca
Rafinarea suplimentară a etapei 1.1
1.1.1 scoate cutia de ceai din dulap
1.1.2 scoate capacul cutiei de ceai
1) Operatorii aritmetici
Operatorii aritmetici sunt: + , - , * , / , % , ^
unde semnul de împărţire „/” (DIVIDE) are sensul de cât al împărţirii (în cazul împărţirilor cu
cât şi rest) sau de împărţire reală
iar semnul „%” (MODULO) reprezintă restul împărţirii a două numere întregi,
^ ridicare la putere.
Exemplu : Fie x un numar întreg format din exact 5 cifre. Sa se afiseze cifra unitatilor si cea a miilor, pe
acelasi rând, cu un spatiu între ele.
Exemplu: daca pentru x se citeste valoarea 12345 se va afisa 5 2.
Pasul2 : date de intrare x întreg
date de manevra cu, cm întregi (sa memoreze cifra unitatilor în cu si cifra miilor in cm )
Pasul 3: citeste x
Pasul 4: cu = x % 10 (extrag cifra unitatilor)
x = x/1000 (elimin ultimele cifre din numar)
cm= x % 10 (retin cifra miilor în cm )
Pasul 5: scrie cu, cm
Observatie:
Pentru a obtine cifrele unui numar trebuie sa efectuam împartiri la 10.
Am aratat ca operatorul MODULO „%” returneaza restul împartirii.
În cazul în care un numar se DIVIDE „/” la 10, numarul ramane fara ultima cifra.
În cazul în care un numar se DIVIDE „/” la 1000, numarul ramane fara ultimele 3 cifre.
6
Ordinea de efectuare a operaţiilor este dată de prioritatea operatorilor aritmetici (cea cunoscută în
matematică: înmulţiri şi împărţiri şi apoi adunări şi scăderi). Aceştia sunt operatori binari adică
acţionează asupra a doi operanzi. În plus există şi operatorii unari plus şi minus (+, -), care acţionează
asupra unui singur operand şi au sensul de semn al numărului (pozitiv sau negativ).
2) Operatori relaţionali
Sunt cei folositi şi în matematică:
1) >(mai mare)
2) < (mai mic),
3) ≥ (mai mare sau egal),
4) ≤ (mai mic sau egal),
5) = (egal),
6) ≠ (diferit).
Ei precizează o relaţie de ordine sau de egalitate între date, care poate fi îndeplinită sau nu.
Expresiile construite cu operatorii relaţionali pot fi evaluate la o valoare de adevar:
„adevarat” sau „fals”, după cum este îndeplinită relaţia sau nu.
în funcţie de limbajul de programare folosit, apar convenţii de notaţie specifice pentru operatori (de
exemplu semnul „diferit” va fi implementat în C++ ca „ != ” iar în Pascal ca „ <> ”, pe când semnele ≤
şi ≥ vor fi implementate ca <= şi >=, la fel, în ambele limbaje).
Operatorii relaţionali sunt operatori binari şi se pot aplica numai operanzilor numerici, logici şi de tip
caracter (ordinea caracterelor fiind cea data de codul ASCII). Nu există o ordine specifică a operaţiilor
atunci când folosim operatorii relaţionali.
Operaţiile se efectuează în ordinea apariţiei operatorilor, de la stanga la dreapta.
7
3) Operatori logici Operatorii logici sunt folosiţi pentru
determinarea valorii de adevar a propoziţiilor logice şi
anume „adevarat” sau „fals”, în unele limbaje codificate
cu „1” respectiv „0”. adevărat 6+28 Operatorii logici sunt:
Operatorul „not” este unar, în timp ce „and” şi „or” sunt binari.
Rezultatul expresiilor ce conţin operatori logici este cel prezentat
în logică matematică şi descris în tabelul urmator:
a b a && b
*
a || b
+
!a !b
1 1 1 1 0 0
1 0 0 1 0 1
0 1 0 1 1 0
0 0 0 0 1 1
4) Operatorul sizeof(expresie) sau sizeof(tip)
Exemplu: sa se afiseze numarul de octeti ocupati pentru tipurile de date:
Semnificatie In limbajul C++
negatia logică (not),
şi logic (and),
sau logic (or).
!=
&&
||
8
5) Operatorul incrementare/ decrementare:
Postfixat variabila++ sau variabila - -
Prefixat ++variabila sau - -variabila
6) Operator de atribuire: := , *= , /= , %= , += , - = , <<= , >>= ,
variabila= valoare/expresie
Exemplu: Fie a şi b două variabile întregi. Dorim să schimbăm între ele valorile celor două variabile.
Mai precis, dacă a = 640 şi b = 480, dorim să obtinem a = 480 şi b = 640.
Un mod de a realiza această schimbare presupune utilizarea unei variabile suplimentare, cu rol de
intermediar. Folosind trei operatii de atribuire, algoritmul are următorii paşi:
1. citeşte a, b
2. t := a
3. a := b
4. b := t
5. scrie a,b
9
Evaluarea unei expresii O expresie se evaluează respectand regulile învaţate la matematică: în
primul rand se evaluează expresiile din parantezele rotunde, apoi se efectuează operaţiile în ordinea
prioriţatii lor. Tabelul urmator prezintă prioritatea operatorilor, în ansamblul lor:
expresie are o valoare si un tip
O expresie este formata din unul sau mai multi operanzi(constyante , variabile sau functii),
legati prin operatori aritmetici
Greşeli frecvente în scrierea expresiilor
Sunt câteva greşeli care se fac în mod frecvent atunci când se scriu expresii matematice pentru a fi
evaluate de calculator.
- Se omite semnul de înmulţire. De exemplu se scrie 5a+3 (greşit) în loc de 5*a+3 (corect)
- Se omit parantezele, de exemplu la scrierea unor fracţii sau la calcularea mediei aritmetice:
a+b/2 (greşit) în loc de (a+b)/2 (corect)
- O alta greşeală este utilizarea înlanţuită a operatorilor relaţionali. De exemplu se scrie a<b <c in
loc de a<b si b<c
Exemple:
Linia de fractie, slash-ul (/), poate fi folosita cu operanzi de tip întreg sau real si furnizeaza un rezultat
real.
Exemplu:
Toate operatiile prezentate în continuare furnizeaza acelasi rezultat: 1.25.
5/4....5.0/4....5/4.0....5.0/4.0
10
Principiile de bază ale programării structurate
Principiile de bază ale programării structurate sunt:
1. Proiectarea descendentă a algoritmilor – este cel mai important principiu deoarece el asigură o
modalitate naturală şi eficientă de dezvoltare a algoritmilor care evidenţiază ideile de bază utilizate
în rezolvarea problemei, pornind de la aspecte generale şi ajungând în final la ultimele detalii ale
rezolvării
2. Utilizarea în algoritm a trei tipuri de structuri de control:
a. Structura secvenţială (secvenţa),
actiune1; actiune2; ……actiune n;
b. structura alternativă (decizia)
IF(conditie)actiune1
ELSE actiune2
c. structura repetitivă (ciclul).
1) FOR(conditii) { actiune1, actiune2; ……actiune n; }
2) WHILE(conditie ){actiune1, actiune2; ……actiune n;}
3) DO{ actiune1,actiune2; ……actiune n;} WHILE(conditie)
Structura secvenţială(secvenţa)
Cuprinde o succesiune de operaţii, reprezentate prin unul sau mai multe blocuri procedurale
care se execută secvenţial, adică unul după celălalt în ordinea în care sunt scrise.
Exemplu: Să se calculeze aria unui triunghi oarecare dacă se cunosc lungimile laturilor
triunghiului.
1. Analiza problemei.
Datele de intrare: Lungimile laturilor: numere reale a, b şi c
Datele de ieşire: Aria triunghiului: număr real notat cu s
Datele de manevră: Semiperimetrul: număr real notat cu p
Funcţia programului:
Este de a calcula cu formula lui Heron aria triunghilui dat prin lungimile laturilor.
2. Determinarea algoritmului de rezolvare a problemei
P1. Se introduce (se citesc, se comunica) de la tastatură valorile reale a, b şi c
P2. Se calculează valoarea semiperimetrului p=(a+b+c)/2
P3. Se calculează valoarea ariei s =sqrt(p*( p -a)*( p -b)*( p -c))
P4. Se scrie aria S
P5. Stop
11
Temă pentru acasă:
1. Determină perimetrul şi aria unui dreptunghi, unde lungimile laturilor sunt citite de la
tastatură.
2. Pentru a un număr real, citit de la tastatură, care reprezintă lungimea laturii unui cub,
calculează şi afişează volumul şi suprafaţa totală a cubului.
3. algoritmul pentru 2 valori a şi b numere întregi, sa afiseze rezultatele celor 5 operaţii (suma,
produsul, diferenţa, câtul şi restul operaţie de împărţire pe mulţimea numerelor întregi)
4. se citesc coordonatele unui punct A(x1.y1) si B(x2,y2). Sa se calculeze lungimea segmentului AB
si mijlocul acestuia
ALGORITMI. NOTIUNI GENERALE 1
Caracteristici fundamentale: ......................................................................................... 1
Etapele rezolvarii unei probleme:................................................................................. 2
12
Exista 2 modalitati de reprezentare a algoritmilor ........................................................ 3
Descrierea algoritmilor cu ajutorul schemelor logice 4
Metoda rafinării pas cu pas ........................................................................................... 4
Operatorii aritmetici ..................................................................................................... 5
Operatori relaţionali...................................................................................................... 6
Operatori logici ............................................................................................................. 7
Evaluarea unei expresii ................................................................................................. 9
Principiile de bază ale programării structurate 10
Structura secvenţială(secvenţa) .................................................................................. 10
Fie a şi b două variabile întregi. Dorim să schimbăm între ele valorile celor
două variabile. .......................................................................................................... 8
Fie x un numar întreg format din exact 5 cifre. Sa se afiseze cifra unitatilor si
cea a sutelor, pe acelasi rând, cu un spatiu între ele. ................................................ 5