46
ALGORITMI CURS 2
ALGORITMI
CURS 2
Algoritmi
1. Noțiunea de algoritm
2. Reprezentarea unui algoritm
3. Elementele programării structurate
4. Concepția unui algoritm
5. Exemple de algoritmi elementari
1. Noţiunea de algoritm
• În procesul de rezolvare a unei probleme folosind calculatorulexistă două etape:
•1. Definirea şi analiza problemei
•2. Proiectarea şi implementarea unui algoritm carerezolvă problema
•1. Definirea şi analiza problemei poate fi la rândul eidescompusă în:
• specificarea datelor de intrare
• specificarea datelor de ieşire
1. Noţiunea de algoritmSpecificarea 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.
1. Noţiunea de algoritmSpecificarea 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 (necesareutilizatorului), în acest pas se face diferenţierea clară întredate intermediare şi date de ieş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, sauun text poate fi afişat integral sau parţial).
1. Noţiunea de algoritm
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 trebuie transmise către ieşire.
1. Noţiunea de algoritm• O definiţie a noţiunii de algoritm poate fi:
O succesiune finită de operaţii cunoscute care se execută într-osuccesiune logică bine stabilită astfel încât plecand de la un set de date de intrare, să obtinem într-un interval de timp finit un set de date de ieşire.
Un exemplu simplu de algoritm ar fi suita de operaţii matematicefăcută în rezolvarea unei ecuaţii matematice de gradul II:
coeficienții a, b și c se schimbă dar modul de procesare a valorilor lor, nu
02
cxbxa
1. Noţiunea de algoritm•Proprietăţile unui algoritm sunt:1. Generalitate. Un algoritm trebuie să poată fi utilizat pentru o clasă
întreagă de probleme, nu numai pentru o problemă particulară. Dinaceastă cauză, o metodă de rezolvare a unei ecuații particulare nu poatefi considerată algoritm.
2. Finitudine. Orice algoritm trebuie să permită obținerea rezultatului dupăun număr finit de prelucrări (pași).
3. Determinism. Un algoritm trebuie să prevadă, fără ambiguități și fărăneclarități, modul de soluționare a tuturor situațiilor care pot să apară înrezolvarea problemei. Dacă în cadrul algoritmului nu intervin elementealeatoare, atunci ori de câte ori se aplică algoritmul aceluiași set de datede intrare trebuie să se obțină același rezultat.
1. Noţiunea de algoritm
Tipuri de prelucrări:
Prelucrările care intervin într-un algoritm pot fi simple sau structurate.
• Prelucrările simple sunt atribuiri de valori variabilelor, eventual prin evaluareaunor expresii;
• Prelucrările structurate pot fi de unul dintre tipurile:
− Liniare. Sunt secvențe de prelucrări simple sau structurate care suntefectuate în ordinea în care sunt specificate;
− Alternative. Sunt prelucrări caracterizate prin faptul că în funcție derealizarea sau nerealizarea unei condiții se alege una din două sau mai multevariante de prelucrare;
− Repetitive. Sunt prelucrări caracterizate prin faptul că aceeașiprelucrare (simplă sau structurată) este repetată cât timp este îndeplinită oanumită condiție.
1. Noţiunea de algoritm
•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.
2. Reprezentarea unui algoritm
Modul de descriere a unui algoritm, esteindependent de un limbaj de programare,existând două metode clasice:
1. metoda schemei logice
2. metoda pseudocod-ului
3. Elementele programării structurate
•Structurile de control de bază – cu ajutorul lor se pot descrie algoritmii: secvența, decizia alternativă binară (if) și structura repetitivă cu test inițial (while)
•Care sunt cele derivate?
•Cum sunt reprezentate cu scheme logice sau pseudocod?
3. Elementele programării structurate•Prin generalizare, putem spune că programarea este arta şi
tehnica realizării de algoritmi, care ulterior vor fi descrişi şiimplementaţi în programe pe calculator, scrise într-un limbajde programare.
•Programarea pe baza celor trei structuri (şi a celor auxiliare)se numeşte programare structurată.
• Informaticienii Böhm şi Jacopini au formulat un principiu alprogramării structurate, sub forma unei teoreme: cele treistructuri (secvenţa, decizia şi repetiţia condiţionată anterior)sunt suficiente pentru a descrie orice algoritm.
3. Elementele programării structurate
Teorema programării structurate a lui Böhm şi Jacopinicare se poate enunţa astfel:
Orice schemă logică nestructurată poate fi înlocuită cuuna echivalentă, dar structurată, prin adăugarea de noiacţiuni şi condiţii.
Aşadar, orice program poate fi pus sub o formăstructurată, adică să conţină doar structurile de bazăşi/sau structurile auxiliare, prin utilizarea unor variabileboolene asociate unor funcţii suplimentare.
3. Elementele programării structurateExemplu:Algoritmul următor determină cel mai mic element (notat min) din şirul de n elemente X și este într-o formă nestructurată
Citeste n, Xi = 1min = X(0)
A: dacă i>n atuncitreci la pasul B -> instrucțiune de salt necondiționată, nu e secvențială
altfeldacă X(i)<min atunci
min = X(i)i = i+1treci la pasul A
B: Scrie min
3. Elementele programării structurateExemplu:
Algoritmul rescris într-o formă structurată, utilizând structurile de bază
Citeste n, X
min = X(0)
i = 1
cât timp i <= n execută
dacă X(i)<min atunci
min = X(i);
i = i+1
Scrie min
Cum se rescrie algoritmul folosind o structură repetitivă derivată?
4. Concepția unui algoritm
Pași necesari:
1. Problema care va fi rezolvată, trebuie citită cuatenţie.
2. Apoi se stabilesc prelucrările care sunt necesareobţinerii rezultatelor dorite.
Pentru a crea un algoritm eficient trebuieevidenţiate datele de intrare şi datele de ieşire.
5. Exemple de algoritmi elementari
5.1 Algoritmi cu structura de decizie
5.2. Algoritmi cu structura repetitivă cu test initial
5.3. Algoritmi cu structura repetitivă cu test final
5.4. Algoritmi cu structura repetitivă cu numărcunoscut de pași
5.1 Algoritmi cu structura de decizie
Să se citească trei valori naturale a, b și c. Să se scrie un algoritm care să verifice dacă cele trei numere sunt sau nu numere pitagorice.
Precizare: Numim numere pitagorice, trei valori careîndeplinesc Teorema lui Pitagora, adică verifică una dincondițiile:
𝑎2= 𝑏2 + 𝑐2
𝑏2= 𝑎2 + 𝑐2
𝑐2= 𝑏2 + 𝑎2
5.1 Algoritmi cu structura de decizie
Pas 1: Stabilim care sunt datele de intrare, adică celecare vor fi prelucrate cu ajutorul algoritmului,împreunăcu datele de ieşire.
În cazul problemei date, avem:
•Date de intrare: a, b și c numere naturale
•Date de ieşire: mesaj corespunzător
5.1 Algoritmi cu structura de decizie
Pas 2: Analiza problemeiStabilim condiţiile pe care trebuie să le îndeplineascădatele de intrare pentru a fi prelucrate în cadrulalgoritmului.În cadrul problemei pe care o avem de rezolvat, verificămcondiţiile care trebuie îndeplinite de cele trei valori:1) Dacă 𝑎2 = 𝑏2 + 𝑐2, atunci sunt numere pitagorice.•Sau2) Dacă 𝑏2 = 𝑎2 + 𝑐2, atunci sunt numere pitagorice.•Sau3) Dacă 𝑐2 = 𝑎2 + 𝑏2, atunci sunt numere pitagorice.
5.1 Algoritmi cu structura de decizie
citeşte a,b,c
dacă 𝑎2 = 𝑏2 + 𝑐2 sau 𝑏2 = 𝑎2 + 𝑐2 sau 𝑐2 = 𝑎2 + 𝑏2 atunci
scrie ‘Numere pitagorice’
altfel
scrie ‘NU SUNT nr. pitagorice’
sfarşit dacă
stop
5.2 Algoritmi cu structura repetitivă cu test inițial
Să se citească un număr natural n. Să se scrie un algoritmcare verifică dacă numărul dat este sau nu număr prim.
Un număr n este prim dacă are ca divizori doar valorile 1 şi n.
Exemplu:
Pentru n = 7, se va afişa mesajul ‘numărul este prim’, iar pentru n = 22, se va afişa mesajul ‘numărul NU este prim’.
5.2 Algoritmi cu structura repetitivă cu test inițial
Pas 1: Stabilim care sunt datele de intrare, adică celecare vor fi prelucrate cu ajutorul algoritmului, împreună cu datele de ieşire.
În cazul problemei date, avem:
•Date de intrare: n număr natural
•Date de ieşire: număr prim sau nu
5.2 Algoritmi cu structura repetitivă cu test inițial
Pas 2: Analiza problemei:
1) Vom presupune, la începutul problemei, că numărul n dat esteprim, şi vom specifica acest lucru cu ajutorul unei variabile de tiplogic, căreia îi vom da valoarea ‘adevărat’.
2) Apoi vom evalua, pe rând, toate valorile începând cu valoarea 2şi până la n-1, ca să determinăm dacă sunt divizori ai numărului ndat.
3) Dacă găsim un singur divizor printre aceste numere, atunci vomacorda valoarea ‘fals’ variabilei de tip logic de la începutulalgoritmului.
4) La sfârşit vom verifica care este valoarea variabilei de tip logic şivom afişa un mesaj corespunzător.
5.2 Algoritmi cu structura repetitivă cu test inițial
natural n, ilogic pciteşte nP = adevărati = 2cât timp i <= n-1 execută
dacă n % i = 0 atuncip = fals
sfârşit dacăi = i + 1
sfârşit cât timp->
dacă p = adevărat atunciScrie ‘Numarul este prim’
altfelscrie ‘Numarul NU este prim’
sfârşit dacă
Stop
5.3 Algoritmi cu structura repetitivă cu test final
Să se scrie un program care verifică dacă un număr n este perfect sau nu.
Un număr perfect este egal cu suma divizorilor lui, inclusiv 1 (exemplu: 6 = 1 + 2 + 3).
Exemplu:
•Pentru n = 28, se va afişa mesajul
Numar perfect (divizorii lui 28 sunt 1, 2, 4, 7, 14)
5.3 Algoritmi cu structura repetitivă cu test final
Pas 1: Stabilim care sunt datele de intrare, adică celecare vor fi prelucrate cu ajutorul algoritmului,împreună cu datele de ieşire.
În cazul problemei date, avem:
•Date de intrare: n număr natural
•Date de ieşire: mesaj corespunzător
5.3 Algoritmi cu structura repetitivă cu test final
Pas 2: Analiza problemei
1) La începutul problemei, vom inițializa o variabilă de tip suma cu valoarea 0.
2) Pentru fiecare valoare i de la 1 la n-1 vom verifica dacăi este divizor al numarului n. Daca este divizor atunci il insumam la valoarea s.
3) Verificam daca suma obtinuta este egala cu numarul n. Daca da atunci scriem mesajul
‘Numarul este perfect’.
5.3 Algoritmi cu structura repetitivă cu test final
natural n, i, sciteşte ni = 1s = 0repetă
dacă n % i = 0 atuncis = s + i
sfârşit dacăi = i + 1
până când i > n-1 ->
dacă s = n atunci
scrie ‘Este perfect’
altfel
scrie ‘NU este perfect’
sfârşit dacă
stop
5.3 Algoritmi cu structura repetitivă cu test final
Fie şirul lui Fibonacci, definit astfel:
f(0)=0, f(1)=1,
f(n)=f(n-1)+f(n-2) în cazul în care n>1.
Să se scrie un algoritm care implementează valorileşirului lui Fibonacci.
Exemplu:
Pentru n = 7 se vor afişa valorile 1, 1, 2, 3, 5, 8, 13.
5.3 Algoritmi cu structura repetitivă cu test final
Pas 1: Stabilim care sunt datele de intrare, adică celecare vor fi prelucrate cu ajutorul algoritmului,împreunăcu datele de ieşire.
În cazul problemei date, avem:
•Date de intrare: n număr natural
•Date de ieşire: numerele din şirul lui Fibonacci
5.3 Algoritmi cu structura repetitivă cu test final
Pas 2: Analiza problemei
La începutul problemei, vom iniţializa două valori
(a şi b) cu primele două elemente ale şirului luiFibonacci, adică cu valori de 1.
Apoi, într-un ciclu repetitiv vom calcula cu ajutorul uneia treia valori (variabila c) suma lor, iar apoi vom da:
valoarea b varibilei a
şi valoarea c variabilei b
5.3 Algoritmi cu structura repetitivă cu test final
natural n, i, a, b, cciteşte ni = 1a = 1b = 1repetă
c = a + bscrie ca = bb = ci = i + 1
până când i > n-2stop
5.3 Algoritmi cu structura repetitivă cu test final
Fie un număr natural n de cinci cifre. Să se scrieun algoritm care să calculeze suma cifrelornumărului dat.
Exemplu:
Pentru n = 2178, se va afişa valoarea
s = 2+1+7+8=18
5.3 Algoritmi cu structura repetitivă cu test final
Pas 1: Stabilim care sunt datele de intrare, adicăcele care vor fi prelucrate cu ajutorul algoritmului,împreună cu datele de ieşire.
În cazul problemei date, avem:
•Date de intrare: n număr natural
•Date de ieşire: s = suma cifrelor
5.3 Algoritmi cu structura repetitivă cu test final
Pas 2: Analiza problemei
La începutul problemei, vom iniţializa valoarea sumei cifrelor numărului n dat cu 0.
Apoi, într-un ciclu repetitiv vom calcula
- suma cifrelor numărului,
- ştiind că o cifră a unui număr scris în baza 10 este dată de n%10,
- iar câtul este dat de n/10.
5.3 Algoritmi cu structura repetitivă cu test final
natural n, s
citeşte n
s = 0
repetă
s = s + n%10
n = n/10
până când n = 0
scrie s
stop
Ultimacifra a lui n
Numărul fără ultima
cifră
5.4 Algoritmi cu structura repetitivă cu număr cunoscut de pași
Se citesc două numere întregi a şi b. Să se realizeze in pseudocod un algoritm care să verifice dacă cele douanumere sunt prietene.Spunem ca două numere sunt prietene dacă suma divizorilorproprii ai unui număr este egală cu celălalt număr şi invers.
Exemplu:Pentru n = 220, si m = 284 se vor afişa valorile:Divizorii lui 220, sunt 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 și 110. Suma este 284Divizorii lui 284, sunt 1, 2, 4, 71 și 142. Suma lor este 220
5.4 Algoritmi cu structura repetitivă cu număr cunoscut de pași
Pas 1: Stabilim care sunt datele de intrare, adicăcele care vor fi prelucrate cu ajutorul algoritmului, împreună cu datele de ieşire.
În cazul problemei date, avem:
•Date de intrare: n si m numere naturale
•Date de ieşire: numerele sunt sau nu prietene
5.4 Algoritmi cu structura repetitivă cu număr cunoscut de pași
Pas 2: Analiza problemei
La începutul problemei, vom iniţializa valoarea unei variabilepentru suma divizorilor lui n cu 0, iar apoi valoarea unei variabilepentru suma divizorilor lui m cu 0.
Apoi, într-un ciclu repetitiv avand n/2 pasi vom calcula sumadivizorilor lui n.
Apoi, într-un ciclu repetitiv avand m/2 pasi vom calcula sumadivizorilor lui m.
La sfarsit vom verifica daca suma divizorilor primului numareste egală cu cel de-al doilea număr, iar suma divizorilor celui de-al doilea numar este egală cu primul număr
5.4 Algoritmi cu structura repetitivă cu număr cunoscut de pași
natural n, m, i, j, suma_n, suma_m
citeşte n
suma_n = 0
pentru i=1,n/2 execută
daca n%i=0 atunci
suma_n = suma_n + 1
sfârșit daca
sfârșit pentru
suma_m = 0
pentru j=1,m/2 execută
dacă m%j=0 atunci
suma_m = suma_m + j
sfârșit dacă
sfârșit pentru
dacă suma_n = m AND suma_m=n atunci
scrie “Numere prietene”
altfel
scrie “Numere neprietene”
sfârșit dacă
stop
5.4 Algoritmi cu structura repetitivă cu număr cunoscut de pași
Să se calculeze suma numerelor naturale cuprinseintre două numere date (dintr-un interval).
Exemplu:
Pentru 3 si 6 reprezentand capetele intervalului, se va afisa valoarea 9 reprezentand suma.
5.4 Algoritmi cu structura repetitivă cu număr cunoscut de pași
Pas 1: Stabilim care sunt datele de intrare, adicăcele care vor fi prelucrate cu ajutorul algoritmului,împreună cu datele de ieşire.
În cazul problemei date, avem:
•Date de intrare: a si b numere naturale
•Date de ieşire: suma numerelor aflate inintervalul (a,b)
5.4 Algoritmi cu structura repetitivă cu număr cunoscut de pași
Pas 2: Analiza problemei
La începutul problemei, vom iniţializa cu 0variabila în care vom reține valoarea sumeinumerelor din intervalul (a,b).
Apoi, într-un ciclu repetitiv pornind de la a+1 și
mergand pana la b-1 vom aduna la suma toatevalorile din intervalul dat.
La sfârșit vom avea valoarea suma
5.4 Algoritmi cu structura repetitivă cu număr cunoscut de pași
natural a, b, i, suma
citeşte a,b
suma = 0
pentru i=a+1,b-1 execută
suma = suma + i
sfârșit pentru
scrie suma
stop
