Descrierea algoritmilor, limbajul Pseudocod. 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 rezutatelor 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).

În continuare vor fi descrise blocurile ce descriu în schema logică o anumită operaţie (simbolurile acestora).

Figura 2.1. Simboluri folosite în cadrul algoritmilor.

Blocurile delimitatoare (Start şi Stop) (figura 2.1.a şi 2.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

(nu poate exista decât un singur început dar pot exista mai multe posibilităţi de terminare a programului definit de algoritm).

Blocurile de intrare/ieşire (Citeşt şi Tipăreşte) (figura 2.1.c şi 2.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 matematice expresie (figura 2.1.e).

Blocurile de decizie marchează punctele de ramificaţie ale algoritmului în etapa de decizie. Ramificarea poate fi dublă (blocul logic, figura 2.1.f) sau triplă (blocul aritmetic, figura 2.1.g). Blocul de decizie logic indică ramura pe care se va continua execuţia algoritmului în funcţie 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).

Exemplul 1: Algoritmul de rezolvare al ecuaţiei de gradul I:

Fig. 2.2. Algoritmul de rezolvare al ecuaţiei de gradul I. Ecuaţia de gradul I are forma a*x+b=0 iar soluţia

acesteia este x=-b/a. Se observă că mai întâi se face citirea de la tastatură a valorilor coeficienţilor a şi b care sunt asociaţi variabilelor a şi b. S-a folosit acelaşi nume al coeficienţilor din forma matematică a ecuaţiei cu numele variabilelor tocmai pentru o urmărire cât mai uşoară evoluţiei calculelor.

După citirea variabilelor a şi b se face atribuirea în variabila x a expresiei matematice care defineşte rădăcina ecuaţiei. Înainte de sfârşit, aceasta trebuie afişată pentru a se îndeplini în totalitate scopul programului.

Ca algoritmul să fie finit, este evident faptul că el trebuie să se încheie cu instrucţiunea STOP.

Exemplul 2: Algoritmul de rezolvare al ecuaţiei de gradul II: Ecuaţia de gradul II are ca formă a*x2+b*x+c=0. Pentru început aceste valori trebuie

asociate în variabilele respective.

Figura 2.3. Algoritmul de rezolvare al unei ecuaţii de gradul II

Ecuaţia poate avea rădăcini reale, respectiv complexe, în funcţie de semnul

discriminantului delta�= 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 delta şi va continua în funcţie de valoarea lui delta, aşa cum se poate vedea în figura 2.3.

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 propoziţ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 algoritmului }

Sfarşit_Algoritm. { Sfarşitul algoritmului } 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; 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 secventa 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 Secvenţă1 Altfel Secvenţa2

Sf_Dacă ; Aceasta se poate interpreta astfel: dacă această Condiţie este îndeplinită se

execută prima secvenţă, dacă nu, a doua. - structura alternativă cu mai multe ramuri : Selectează Expresie Dintre Listă_Valori 1 : Secvenţă 1;

Listă_Valori 2 : Secvenţă 2;. Listă_Valori n : Secvenţă n; [ 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 variabila := valoare început , valoare sfarşit , pas Execută

Secvenţă Sf_Pentru; având următoarea semnificaţie : se execută secvenţa (corpul structurii) dând

succesiv valori variabilei contor (variabilă ) începând de la limita iniţială (valoare început) până la limita finală (valoare sfârşit) 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 aşa 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.

Figura 3.1. Structuri repetitive 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ă 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ă.