3

1. Descrierea algoritmilor, limbajul Pseudocod.

1.1. Descrierea algoritmilor.

Prin algoritm putem în•elege o succesiune finit• de opera•ii. Acesta

presupune executarea unor calcule într-o anumit• ordine. Putem considera c• un

algoritm este o secven•• finit• de propozi•ii ale unui limbaj de descriere a

algoritmilor. Fiecare propozi•ie a limbajului precizeaz• o anumit• regul• de

calcul, a•a cum se va observa atunci când vom prezenta limbajul Pseudocod.

Algoritmii pe care îi descriem ar trebui s• fie cât mai generali ( s• rezolve o clas•

de probleme de acela•i tip), s• dea rezultate într-un anumit timp (finit, adic• s• se

termine oricare ar fi datele de intrare) •i de asemenea s• asigure unicitatea

rezulatelor ori de câte ori se dau acelea•i date de intrare. Aceste trei caracteristici

generalitate, finitudine •i unicitate trebuie s• ne preocupe ori de câte ori scriem un

algoritm, indiferent de forma (scheme logice sau limbaj Pseudocod) în care este

prezentat acesta.

Schema logic• este un mijloc de descriere a algoritmilor prin reprezentare

grafic•. Regulile de calcul ale algoritmului sunt descrise prin blocuri (figuri

geometrice) reprezentând opera•iile (pa•ii) algoritmului, iar ordinea lor de

aplicare (succesiunea opera•iilor) este indicat• prin s•ge•i. Fiec•rui tip de opera•ie

îi este consacrat• o figur• geometric• (un bloc tip) în interiorul c•reia se va înscrie

opera•ia din pasul respectiv. Datele utilizate într-un algoritm pot fi variabile sau

constante (î•i pot modifica valoarea sau nu ). În descrierea unui algoritm,

intervin variabile care marcheaz• atât datele cunoscute ini•ial, cât •i rezultatele

dorite, precum •i alte rezultate intermediare necesare în rezolvarea problemei.

Variabila define•te o m•rime care î•i poate schimba valoarea. Valorile pe care le

poate lua variabila apar•in unei mul•imi D pe care o vom numi domeniul

variabilei. Prin variabil• vom în•elege tripletul (nume, domeniul D, valoare) .

4

În continuare vor fi descrise blocurile ce descriu în schema logic• o

anumit• opera•ie.

Blocurile delimitatoare (Start •i Stop) (figura 1a •i 1.b) vor marca

începutul respectiv sfâr•itul unui algoritm dat printr-o schem• logic•. Descrierea

unui algoritm prin schem• logic• va începe cu un singur bloc Start •i se va

termina cu cel pu•in un bloc Stop.

Blocurile de intrare/ie•ire (Cite•te •i Tip•re•te) (figura 1.c •i 1.d) indic•

introducerea unor Date de intrare respectiv extragerea unor Rezultate finale. Ele

permit precizarea datelor ini•iale cunoscute în problem• •i tip•rirea rezultatelor

cerute de problem•. Blocul Cite•te ini•ializeaz• variabilele din lista de intrare cu

valori corespunz•toare, iar blocul Tip•re•te va preciza rezultatele ob•inute (la

execu•ia pe calculator cere afi•area pe ecran a valorilor expresiilor din lista de

ie•ire).

Blocurile de atribuire (calcul) se utilizeaz• în descrierea opera•iilor de

atribuire (:=). Printr-o astfel de opera•ie, unei variabile var i se atribuie valoarea

calculat• a unei expresii expr (figura 1.e).

Figura 1. Blocurile schemelor logice.

b) a) c) d)

Stop

Start Cite•te list•_var_intrare Tip•re•te list•_expr.ie•ire

e) f) g)

NuCondi•ie

Da var := expresie

=0

Epr. aritm. <0 >0

i

h)

i

5

Blocurile de decizie marcheaz• punctele de ramifica•ie ale algoritmului în

etapa de decizie. Ramificarea poate fi dubl• (blocul logic, figura 1.f) sau tripl•

(blocul aritmetic, figura 1.g). Blocul de decizie logic indic• ramura pe care se va

continua executia algoritmului în functie de îndeplinirea (ramura Da) sau

neîndeplinirea (ramura Nu) unei condi•ii. Condi•ia care se va înscrie în blocul de

decizie logic va fi o expresie logic• a c•rei valoare poate fi una dintre valorile

"adev•rat" sau "fals". Blocul de decizie aritmetic va hotarî ramura de continuare

a algoritmului în func•ie de semnul valorii expresiei aritmetice înscrise în acest

bloc, care poate fi negativ•, nul• sau pozitiv•.

Blocurile de conectare marcheaz• întreruperile s•ge•ilor de leg•tur• dintre

blocuri, dac• din diverse motive s-au efectuat astfel de întreruperi (figura 1.h).

Vom da în continuare o schem• logic•, pentru rezolvarea ecua•iei de

gradul doi aX2+bX+c=0 (a,b,c ∈ R •i a ≠ 0).

Ecua•ia poate avea

r•d•cini reale, respectiv

complexe, în func•ie de semnul

discriminantului ∆ = b2 - 4ac.

Algoritmul de rezolvare

a problemei va citi mai întâi

datele problemei, marcate prin

variabilele a, b •i c. Va calcula

apoi discriminantul ∆ •i va

continua în func•ie de valoarea

lui ∆, a•a cum se poate vedea în

figura 2.

Figura 2. Algoritm pentru rezolvareaecua•iei de gradul doi.

Start

Cite•te a, b, c

Tip•re•te Re,Im Tip•re•te x1,x2 1

Stop

Re:=-b / 2a

Im:=√-∆/2a

∆<0 Nu Da

Nu

∆:=b2-4ac

Mesaj a=0

1

Da

x2:=-b-√∆ 2a

x1:=-b+√∆ 2a

a=0

6

1.2. Limbajul Pseudocod.

Limbajul Pseudocod a fost conceput pentru descrierea algoritmilor.

Limbajul Pseudocod are dou• tipuri de propozi•ii: standard (care au o structur•

fix• •i este format• cu ajutorul unor cuvinte cheie), propozi•ii nestandard (care

descriu p•r•i ale algoritmului înc• incomplet elaborate, nefinisate, asupra c•rora

urmeaz• s• se revin•) •i comentarii (texte scrise între acolade utilizate pentru

documentarea algoritmului). Propozi•iile limbajului Pseudocod se vor executa în

ordinea întâlnirii lor în text, asemenea oric•rui text al limbii române.

În descrierea algoritmilor se recomand• o scriere structurat• prin

utilizarea urm•toarelor structuri : secven•ial• (format• dintr-o succesiune de

propzi•ii simple), alternativ• (permite executarea anumitor ramuri în func•ie de

anumite condi•ii) repetitiv• (prin care putem execut• acelea•i propozi•ii de mai

multe ori).

Structura general• a unui algoritm descris în Pseudocod este :

Algoritmul Nume Este : { Antetul algoritmului }

. . . { Corpul “ }

Sfar•it_Algoritm. { Sfar•itul “ }

Un algoritm (în general) se desf••oar• în trei etape :

- citirea datelor de intrare (ini•ializarea datelor),

- efectuarea de calcule (prelucrarea datelor),

- tip•rirea rezultatelor (extragerea datelor de ie•ire).

Citirea datelor se face prin propozi•ia Date List•_variabile_de_intrare;

iar Tip•rirea rezultatelor prin Rezultate List•_expresii_de_ie•ire;

Prelucrare

Date de intrare

Date de iesire

7

O propozi•ie des utilizat• în efectuarea calculelor este aceea prin care unei

variabile i se atribuie valoarea unei expresii. Aceasta este de forma [Fie]

Variabil• := Expresie; în care cuvântul Fie poate lipsi. Expresia din dreapta

semnului de atribuire poate fi o expresie construit• cu cele patru opera•ii:

adunare, sc•dere, înmul•ire •i împ•r•ire (notate prin caracterele +, −, *, respectiv

/). Prin aceast• instruc•iune o variabil• prime•te (i se asigneaz•, i se atribuie, sau

este ini•ializat•) valoarea (calculat• a) unei expresii.

Pentru descrierea unei structuri alternative avem trei posibilit••i :

- structura alternativ• cu o ramur• :

Dac• Condi•ie Atunci Dac• a<0 Atunci

Secven•• Fie a := −a

Sf_Dac• ; Sf_Dac•;

interpretat• astfel : dac• este îndeplinit• aceast• Condi•ie atunci se execut•

secven•a de propozi•ii care urmeaz• pân• la sfâr•itul structurii, iar în caz contrar

se trece direct la urmatoarea structur•;

- structura alternativ• cu dou• ramuri :

Dac• Condi•ie Atunci Dac• a<b Atunci

Secven••1 Minim:=a

Altfel Altfel

Secven•a2 Minim:=b

Sf_Dac• ; Sf_Dac•

aceasta se poate interpreta astfel: dac• aceast• Condi•ie este îndeplinit• se execut•

prima secven••, dac• nu, a doua.

8

- structura alternativ• cu mai multe ramuri :

Selecteaz• Expresie Dintre Selecteaz• Luna Dintre

List•_Valori1 : Secven••1; 4, 6, 9, 11: Nr_Zile:=30;

List•_Valori2 : Secven••2; 2: Nr_Zile:=28+Dif_Bisect

. . . Altfel Nr_Zile:=31

List•_Valorin : Secven••n Sf_Selecteaz•;

[ Altfel Secven••n+1 ]

Sf_Selecteaz•;

care se poate “traduce” astfel : se caut• valoarea expresiei în listele de valori •i se

execut• secven•a corespunz•toare. Dac• valoarea calculat• nu se reg•seste în nici

o list• (•i apare alternativa Altfel care este op•ional•, atunci se execut• ultima

secven•• notat• cu n+1).

Structurile repetitive permit executarea unei secven•e de propozi•ii de mai

multe ori (de un anumit num•r de ori, sau cât• vreme este îndeplinit• o anumit•

condi•ie, sau pân• când este îndeplinit• o anumit• condi•ie). Pentru descrierea

structurilor repetitive exist• trei variante pe care le putem alege în func•ie de

problema concret• pe care dorim s• o rezolv•m.

Structura Pentru este o structur• repetitiv• cu un num•r bine determinat de

pa•i, în schimb structura Cât_Timp (cu test ini•ial) •i structura Repet• (cu test

final) sunt structuri repetitive cu un num•r necunoscut de pa•i (lucru pe care îl

vom vedea imediat).

- structura repetitiv• Pentru se descrie prin propozi•ia :

Pentru Varc := Li , Lf [ , Pas ] Execut•

Secven••

Sf_Pentru;

având urm•toarea semnifica•ie : se execut• secven•a (corpul structurii) dând

succesiv valori variabilei contor (Varc ) începând de la limita ini•ial• (Li) pân• la

9

limita final• (Lf) cu pasul precizat (implicit este 1, adic• dac• lipse•te Pas, atunci

se consider• egal cu 1).

- structura repetitiv• Cât_Timp are format general :

Cât_Timp Condi•ie Execut•

Secven••

Sf_Cât_Timp;

•i se interpreteaz• astfel : dac• aceast• condi•ie este îndeplinit• atunci se execut•

secven•a •i din nou se verific• condi•ia, •i asa mai departe. În momentul în care

condi•ia nu este îndeplinit• se termin• structura repetitiv• •i se continu• cu

urmatoarea structur•.

- structura repetitiv• Repet• se va scrie

Repet•Secven••

Pân•_Când Condi•ie ;

având semnifica•ia : se execut• secven•a descris• apoi se verific• dac• este

îndeplinit• condi•ia precizat•. Dac• aceasta este îndeplinit• se termin• structura

repetitiv•, iar dac• nu este îndeplinit•, atunci de execut• din nou secven•a •i se

reevalueaz• condi•ia.

Structura Cât_Timp Structura Repet•

Figura 3.

Se observ• •i în figura 3 c• spre deosebire de structura Cât_Timp care

poate s• nu execute niciodat• secven•a sa, structura Repet• va permite executarea

corpului s•u cel pu•in o dat•. Pentru ambele structuri trebuie s• fim aten•i s•

Secven••

Secven•• NuCondi•ie Da Nu

Condi•ie

Da

10

modific•m în secven•ele lor, variabile care fac parte din condi•ie pentru ca

aceasta s• se modifice. În caz contrar algoritmul nu se va termina, va intra într-o

bucl• infinit•.

Exemplul urm•tor calculeaz• produsul a dou• polinoame P •i Q , date prin

•irurile coeficien•ilor.

Algoritmul Produs Este : { R:=P×Q }

Date m,(Pi, i=0,m), n,(Qj, j=0,n); { m=gradul lui P, n=gradul lui Q }

Pentru k:=0,m+n Execut• { m+n=gradul lui R }

Rk:=0

Sf_Pentru;

Pentru i:=0,m Execut•

Pentru j:=0,n Execut•

Ri+j:=Ri+j+Pi*Qj

Sf_Pentru;

Sf_Pentru;

Rezultate (Rk, k=0,m+n)

Sf_Algoritm.

Algoritmul urm•tor, dat ca exemplu, determin• primele n (n dat) numere

prime.

Algoritmul Prime Este : { Primele n numere Prime }

Date n; { primele n numere prime p =2,3,5, ... }

p:=2; i:=0;

Cât_Timp i<n Execut• { i reprezint• al câtelea num•r prim a fost g•sit }

d:=2; { p este prim ?( se divide cu 2,3, ... )}

Cât_Timp (d<Sqrt(p)) •i (p Mod d > 0) Execut•

d:=d+1 {se caut• divizori d =2,3,... �p}

Sf_Cât_Timp;

Dac• d>Sqrt(p) Atunci { dac• am trecut cu d de �p atunci p este prim ! }

Rezultate p; i:=i+1

Sf_Dac•;

Dac• p=2 Atunci p:=p+1 { Se verific• doar pentru }

11

Altfel p:=p+2 { numerele impare de la 3,... }

Sf_Dac•;

Sf_Cât_Timp

Sf_Algoritm.

Ca exemplu de folosire a structurii Repet• vom scrie urm•torul algoritm

care determin• cel mai mare numar n de patru cifre pentru care este îndeplinit•

condi•ia :

Oglindit (n) + Suma_Cifrelor(n) = n + 99 (Oglinditul lui 123 este 321).

De exemplu pentru n = 4014, egalitatea este adevarat• pentru c•

4104 + 9 = 4014 + 99 (4+0+1+4=9).

Algoritmul Num•r Este : { Cel mai mare num•r n de patru cifre : }

n:=9999; { Ogl (n) + Sc (n) = n + 99 }

Repet•

n:=n−1;

Cât:=n; Sc:=0; Ogl:=0; { Primul Cât este n }

Repet•

Uc :=Cât Mod 10; { Determin Ultima cifr• a num•rului }

Sc :=Sc + Uc; { Adun Ultima cifr• la Suma cifrelor }

Ogl :=Ogl *10+ Uc; { Adaug Ultima cifr• la Oglindit }

Cât :=[Cât / 10] { Sterg Ultima cifr• din num•r }

Pân•_Când Cât=0;

Pân•_Când (Ogl+Sc=n+99) Sau (n=999);

Dac• n>999 Atunci Rezultate n

Altfel Rezultate ‘Nu exist•’

Sf_Dac•

Sf_Algoritm.