Algoritmi si scheme logice

Realizarea unei aplicatii folosind un sistem de calcul presupune parcurgerea, in principiu, a urmatoarelor etape:

• Analiza problemei
• Proiectarea aplicatiei
• Implementarea aplicatiei
• Intretinerea aplicatiei

Analiza problemei

Rol Elaborarea unui enunt complet si precis al problemei, tinand cont de conditiile concrete de realizare si executie a aplicatiei

Obiective

• Stabilirea functiei aplicatiei (ce urmeaza sa realizeze aceasta)
• Identificarea informatiei de prelucrat (datele de intrare)
• Identificarea rezultatelor cerute (datele de iesire)

Referirea datelor se realizeaza cu ajutorul unor notatii simbolice, numite variabile.

Rezultatul etapei de analiza se numeste specificatia aplicatiei si ea trebuie sa contina:

Lista variabilelor de intrare

Modelul de prelucrare

Descrierea organizarii datelor pe suporturile externe de informatii

Proiectarea aplicatiei

Rol Elaborarea algoritmului care realizeaza functia aplicatiei. Adica, conceperea unei liste de comenzi care descrie secventa de operatii pe care le va executa calculatorul pentru rezolvarea problemei.

In cazul problemelor complexe, proiectarea decurge in doua etape:

Descompunerea problemei date in subprobleme;

Construirea algoritmilor de rezolvare a subproblemelor.

In aceste cazuri logica aplicatiei este reprezentata printr-o colectie de algoritmi corelati intr-o structura ierarhica. Aplicatia obtinuta este un sistem de module, fiecare modul rezolvand una din subproblemele in care a fost divizata logica aplicatiei.

Avantajele modularizarii aplicatiilor sunt:

• Simplificarea procesului de codificare;
• Simplificarea procesului de dezvoltare si verificare a algoritmilor;
• Simplificarea procesului de testare si depanarea aplicatiei;
• Posibilitatea refolosirii modulelor componente.

Obiectiv Realizarea algoritmului programului care sa rezolve problema propusa.

Implementarea aplicatiei

Rol Codificarea algoritmilor (programarea) si punerea la punct a aplicatiei.

Obiectiv Obtinerea algoritmilor necesari intocmirii programului care rezolva problema propusa, testarea rezultatelor obtinute si corectarea eventualelor erori de programare.

Intretinerea aplicatiei

Rol Efectuarea modificarilor necesare in scopul corectarii unor erori identificate in cursul exploatarii ei sau pentru a o adapta la noile cerinte aparute.

1. Notiunea de algoritm

Prelucrarea informatiilor intr-un sistem de calcul se realizeaza prin executia unor operatii simple. Operatiile se aplica asupra unor reprezentari ale informatiilor, numite date. Inlantuirea acestor operatii simple, respectand logica de rezolvare, va conduce la obtinerea rezultatelor dorite.

Spre exemplu, notand cu N si M doua numere intregi pozitive si cu C cel mai mare divizor comun al lor, atunci algoritmul lui Euclid pentru aflarea celui mai mare divizor comun a doua numere intregi pozitive date poate fi descris astfel:

1. CITESTE valorile lui M si N.
2. ATRIBUIE lui C valoarea lui N.
3. ATRIBUIE lui R restul impartiri intregi a lui M la N.
4. DACA R <> 0 (R diferit de 0) ATUNCI TRECI LA pasul 7.
5. SCRIE valoarea lui C.
6. STOP.
7. ATRIBUIE lui M valoarea lui N.
8. ATRIBUIE lui N valoarea lui R.
9. TRECI la pasul 2.

Modul in care este prezentat acest algoritm este "imperativ"; propozitiile fiind de fapt niste comenzi pe care trebuie sa le execute cineva (omul sau masina). Fiecare comanda a algoritmului specifica o operatie (actiune) ce se aplica datelor.

Parcurgand algoritmul, se poate constata ca pe parcursul executarii operatiilor valorile asociate lui M, N, R (restul impartirii) si C se modifica. Deci putem spune ca acestea sunt variabile, deoarece valoarea lor se modifica prin executia unei operatii.

In pasul 4, al acestui algoritm, valoarea lui R (restul impartirii) se compara cu 0. Aceasta valoare (0) nu se modifica pe parcursul executarii algoritmului; deci se poate spune ca 0 este o constanta.

Pentru a putea urmari mai usor executia acestui algoritm, se poate folosi un tabel in care se vor nota valorile identificatorilor inainte de executia comenzii si comanda ce se va executa:

Principalele caracteristici ale unui algoritm sunt:

• Secventialitatea - operatiile sunt executate una dupa alta.
• Generalitatea - calitatea lor de a putea furniza rezultate pentru o multime de date de intrare diferite.
• Finitudine - executia algoritmului se termina dupa un numar finit de operatii.

Descrierea algoritmilor pentru a fi executati folosind un sistem de calcul nu se poate realiza folosind un limbaj natural, datorita in primul rand al faptului ca limbajul natural nu este riguros - diversele formulari ale limbajului putand avea mai multe intelesuri.

Cele mai utilizate procedee de reprezentare a algoritmilor sunt schemele logice si limbajul pseudocod. Principala calitate a acestora este posibilitatea de a evidentia cu claritate succesiunea operatiilor:

• Schemele logice - folosesc diferite forme geometrice pentru a simboliza actiunile si sagetile intre acestea prntru a defini ordinea de executie.
• Pseudocodul - foloseste cuvinte cu inteles predefinit, numite cuvinte cheie, si cateva reguli simple de aliniere a textului pentru a preciza actiunile, iar ordinea de excutie este data de ordinea aparitiei lor.

2. Scheme logice

Avantajele utilizarii schemelor logice sunt:

• Usureaza scrierea si depanarea programelor.
• Asigura o mai usoara intelegere a programelor de catre persoanele care nu au participat la intocmirea lor.
• Permite lucrul in echipa si schimbul de informatii intre programatori.
• Permite compararea diferitelor variante pentru a o alege pe cea mai eficienta.

Simbolurile folosite in schemele logice

Principalele simboluri ce se folosesc la intocmirea unor schemelor logice:

Structuri de baza

La intocmirea schemelor logice se folosesc urmatoarele tipuri de structuri:

• Structuri secventiale.
• Structuri alternative.
• Structuri repetitive (cicluri).

Structura secventiala

Se reprezinta sub forma:

Structuri alternative

Exista doua tipuri de structuri alternative: de decizie si de selectie multipla.

Structura de decizie

Se reprezinta sub forma:

Nu Da

Structura de selectie multipla

Se reprezinta sub forma:

1           2 . n

Structuri repetitive

Se folosesc atunci cand pentru a obtine un rezultat, aceleasi operatii se executa de mai multe ori, deci se executa in mod repetat. Exista trei tipuri de structuri repetitive:

• Structura repetitiva cu test initial (conditionata anterior).
• Structura repetitiva cu test final (conditionat posterior).
• Structura repetitiva cu contor.

Primele doua tipuri de structuri se folosesc cand nu se cunoaste numarul de iteratii (repetari), dar exista o posibilitate de terminare a structurii. Cel de-al treilea tip de structura se foloseste cand se cunoaste de la inceput numarul de iteratii. Structurile repetitive se mai numesc si cicluri.

Structura repetitiva cu test initial

Structura se poate reprezenta sub forma:

Da

Nu

Se foloseste cand este posibil ca operatia sa nu se execute niciodata.

Structura repetitiva cu test final

Forma grafica de reprezentare a structurii este:

Nu

Nu

Se foloseste ori de cate ori este necesar ca actiunea sa se execute cel putin o data.

Structura repetitiva cu contor

Structura repetitiva cu contor, cunoscuta si sub numele de ciclu cu numar cunoscut de pasi, se reprezinta grafic sub forma:

Nu

Da

Se foloseste ori de cate ori se cunoaste de la inceput numarul de repetari.

3. Pseudocodul

Pseudocodul foloseste doua tipuri de enunturi:

• nestandard - fraze ale limbajului natural, utilizate de programator in schitarea formelor initiale ale algoritmilor. Enunturile nestandard sunt precedate in algoritm printr-un caracter astersc (*). In dezvoltarea ulterioara a algoritmilor, ele sunt inlocuite, treptat, cu enunturi standard.
• standard - exprima operatiile cu corespondenta directa in limbajele de programare.

Pseudocodul nefiind un limbaj de programare, are putine reguli sintactice, deci programatorul are o mai mare libertate de exprimare.

Totusi, pseudocodul are cateva operatii de baza si structuri de control care se folosesc in descrierea algoritmilor.

Fiecare operatie (comanda) este reprezentata printr-un cuvant (sau succesiune de cuvinte), care exprima actiunea ce trebuie executata, insotit, de obicei, de elemente suplimentare, care ii particularizeaza efectul.

Cuvantul care identifica operatia se numeste cuvant cheie si nu se modifica de la o comanda la alta comanda de acelasi tip.

Pentru a le scoate in evidenta, cuvintele cheie vor fi scrise cu majuscule.

Operatii de baza

Din categoria operatiilor de baza fac parte operatiile: citirea datelor de intrare, scrierea datelor de iesire, atribuirea valorilor si oprirea prelucrarii.

Citirea datelor de intrare

Operatia de citire consta in transferul unei valori de pe un suport extern de informatii intr-o locatie de memorie. Comanda care indica operatia de citire contine cuvantul cheie CITESTE. Avand in vedere ca, in general, originea transferului este cunoscuta, comanda trebuie sa mai precizeze doar numele locatiei (locatiilor) in care se executa transferul.

Forma generala a comenzii este:

CITESTE <variabila>

sau

CITESTE <lista-vriabile>

Exemple:

CITESTE a

CITESTE a, b, c

Scrierea datelor de iesire

Operatia de scriere consta in transferul unei valori dintr-o locatie de memorie pe un suport extern de informatii. Comanda pentru o operatie de scriere trebuie sa contina cuvantul cheie SCRIE, urmat de numele locatiei (locatiilor) de unde se transfera.

Formatul general al comenzii este:

SCRIE <variabila>

sau

SCRIE <lista-variabila>

Exemple:

SCRIE a

SCRIE x, y, z

Operatia de atribuire

Operatia de atribuire consta din calculul valorii unei expresii si stocarea rezultatului intr-o locatie de memorie. Comanda operatiei de atribuire contine cuvantul cheie ATRIBUIE.

Formatul comenzii este:

ATRIBUIE <variabila> <expresie>

Operatia de oprire

Oprirea executiei comenzilor se realizeaza folosind comanda STOP, a carei format este: STOP

Structuri de control

Prelucrarea datelor folosind un sistem de calcul se bazeaza pe inlantuirea efectelor operatiilor in conformitate cu combinatiile (structurile) utilizate de programator in scrierea algoritmilor.

Pentru "disciplinarea" realizarii algoritmilor in scopul scoaterii in evidenta a rationamentelui rezolvarii problemei, programarea structurata[1] foloseste un set redus de tipuri de structuri. Orice algoritm, oricat ar fi el de complex urmeaza a fi realizat printr-o combinatie de structuri din acest set.

Celei trei structuri de baza utilizate in programarea structurata sunt:

secventa - succesiunea a doua sau mai multe operatii;

decizia - alegerea unei operatii din doua alternative posibile;

ciclul cu test initial - repetarea unor operatii atata timp cat o anumita conditie este indeplinita.

Pentru a spori claritatea descrierii algoritmilor, pseudocodul poate include si alte structuri, care insa nu contravin spiritului programarii structurate; au o singura intrare si o singura iesire.

Secventa

Cel mai simplu tip de structura este secventa, adica scrierea comenzilor una sub alta in ordinea executarii lor.

Exemplu: Dandu-se valorile a, b si c sa se calculeze x1 si x2 astfel

X1=(B*B - 4*A*C)/2

X2=X1+75*c

Algoritmul pentru calcul celor doua valori este:

CITESTE a, b, c

ATRIBUIE x1 (b*b - 4*a*c)/2

ATRIBUIE x2 x1 +75*c

SCRIE x1, x2

STOP

Decizia

Operatia de decizie asigura executia uneia din doua alternative posibile. Ea este reprezentata, in general, printr-o comanda de forma:

DACA <conditie> ATUNCI

<secventa 1>

[ALTFEL

<secventa 2>]

Deci inceputul comenzii de decizie este marcat de cuvantul cheie DACA, sfarsitul sau este indicat de semnul . Utilizarea semnului [ (din stanga structurii) si o anumita aliniere a comenzilor incluse, maresc sugestivitatea reprezentarii. Scrierea decalata (indentare) a celor doua <secvente> subliniaza includerea lor in decizie, ca structura de ordin inferioara. Parantezele drepte din formatul structurii indica faptul ca respectiva constructie este optionala.

Modul de executie al comenzii este:

• se evalueaza conditia <conditie>.
• Daca conditia este indeplinita, se executa operatiile din <secventa 1>; in caz contrar se executa operatiile din <secventa 2>.
• Dupa executarea operatiilor din <secventa 1>  sau <secventa 2> se executa operatiile ce urmeaza dupa aceasta structura.

Exemplu: Dandu-se trei valori, a, b si c, sa se determine cea mai mare valoare. Algoritmul de determinare a maximului dintre trei valori este:

CITESTE a, b, c

DACA a > b ATUNCI

DACA a > c ATUNCI

SCRIE a

ALTFEL

SCRIE c

ALTFEL

DACA b > c ATUNCI

SCRIE b

ALTFEL

SCRIE c

STOP

Algoritmul de rezolvare pentru o problema nu este unic. Spre exemplu, folosind o variabila auxiliara x, aloritmul anterior poate fi scris si sub forma:

CITESTE a, b, c

DACA a > b ATUNCI

ATRIBUIE x a

ALTFEL

ATRIBUIE c b

DACA c > x ATUNCI

ATRIBUIE x c

SCRIE x

STOP

Selectia multipla

Reprezinta o extindere a operatiei de decizie. Ea permite alegerea unei alternative din mai multe posibile. Forma generala a comenzii de selectie multipla este:

ALEGE <expresie> DINTRE

<c1>: <secventa 1>

<c2>: <secventa 2>

.

<cn>: <secventa n>

<rest>: <secventa n+1>

unde <c1>, <c2>, . <cn> sunt constante numite etichete si ele folosesc pentru identificarea sceventelor ce urmeaza a fi executate. Eticheta <rest> si <secventa n+1> pot lipsi.

Modul de executie:

• Se evalueaza expresia de selectie <expresie>;
• Se cauta eticheta avand valoarea egala cu rezultatul expresiei si se executa secventa respectiva; daca nici una din etichete nu corespunde rezultatului, atunci se executa <secventa n+1> daca exista;
• Dupa executarea secventei selectate, se continua cu operatiile existente dupa aceasta structura.

Cicluri

Exista situatii cand pentru a ajunge la rezultatul cautat este necesar ca un grup de operatii sa se execute in mod repetat. Spre exemplu, daca vrem sa aflam cel mai mare divizor comun a doua numere folosind algoritmul lui Euclid (vezi pag. 2) este necsar ca secventa de operatii 4, 7, 8, 9, 2, 3 sa se execute de un numar diferit de ori, in functie de valorile lui M si N. Numarul de repetari nu se cunoaste de la inceput; terminarea algoritmului depinde de indeplinirea unei conditii.

Exista trei tipuri de cicluri si anume:

• Ciclu cu test final;
• Ciclu cu test initial;
• Ciclu cu contor.

Reprezentarea unei astfel de operatii compuse se realizeaza folosind o comanda de ciclare, care specifica atat operatiile care se repeta (corpul ciclului) cat si conditia de repetare.

Ciclu cu test final

In cazul in care operatiile trebuie sa se execute cel putin o data si nu se cunoaste numarul de repetari, se foloseste ciclul cu test final care are urmatoarea forma generala:

REPETA

<secventa>

PANA CAND <conditie>

Modul de executie al ciclului cu test final este:

• Se executa operatiile din corpul ciclului (<secventa>);
• Se evalueaza expresia <conditie>;
• Daca conditia nu se indeplineste se reia executia corpului ciclului; in caz contrar ciclul se termina si se trece la comanda ce urmeaza in algoritm dupa aceasta structura.

Folosind aceasta comanda de ciclare algoritmul lui Euclid se poate scrie astfel:

CITESTE m, n

REPETA

ATRIBUIE c n, r m MOD n

ATRIBUIE m n, n r

PANA r = 0

SCRIE c

STOP

MOD este operatorul impartirii intregi.

Ciclul cu test initial

Atunci cand operatiile ciclului nu trebuie sa se execute niciodata si nu se cunoaste numarul de repetari, se va folosi ciclul cu test initial, a carui forma generala este:

CAT TIMP <conditie> EXECUTA <secventa>

Mod de executie:

• Se evalueaza expresia <conditie>; daca conditia nu este indeplinita, se termina executia comenzii.
• Daca conditia este indeplinita, se executa <secventa> si se reia ciclul de la capat.

Ciclu cu contor

Cand se cunoaste de la inceput numarul de repetari, cea mai indicata structura este ciclul cu contor. Ciclul cu contor se caracterizeaza prin existenta unei variabile care numara iteratiile executate. Formatul general al unui ciclu cu contor este:

PENTRU <contor>=<val_initiala>, <val_finala>[, <pas>] EXECUTA

<secventa>

ž

unde:

<contor> - este o variabila cu valori intregi care numara iteratiile executate;

<val_initiala> - este valoarea de la care incepe contorizarea;

<val_finala> - este valoarea la care se termina contorizarea.

<pas> - valoarea cu care se incrementeaza sau decrementeaza contorul dupa executia unei iteratii. Daca nu este precizat, se considera 1.

Mod de executie:

1. Variabilei <contor> i se atribuie <val_initiala>.
2. Se evalueaza conditia <contor> > <val_finala>; daca rezultatul este fals, se continua cu pasul 3, in caz contrar executia ciclului se termina.
3. Se executa <secventa>.
4. Valoarea <contor> este modificata cu valoarea <pas> si se reia de la pasul 2.

Exemplu: Sa se calculeze factorialul unui numar dat.

Algoritmul pentru calculul factorialului unui numar, tinand cont ca n! = 1*2*3*.*n este:

CITESTE n

ATRIBUIE fact 1

PENTRU i = 1, n EXECUTA

fact = fact * i

ž

Proceduri

Intr-un algoritm anumite sectiuni ale acestuia se pot repeta. Pentru a elimina scrierea repetata a acestora, se utilizeaza descrierea separata a lor si marcarea, prin anumite enunturi specifice, locurile din algoritm in care ele ar trebui sa apara.

O astfel de sectiune, evidentiata printr-o descriere separata, de sine statatoare se numeste procedura, iar enuntul care inlocuieste sectiunea in cadrul algoritmului se numeste apel de procedura.

Descrierea unei proceduri trebuie sa specifice secventa de operatii, care constituie corpul procedurii, sa evidentieze clar parametrii acesteia (partea variabila) si sa asocieze procedurii un nume, ce va fi utilizat in toate apelurile de procedura.

Forma generala a descrierii unei proceduri este:

PROCEDURA <nume_procedura> () ESTE

<corp_procedura>

SFARSIT

unde:

<nume_procedura> - este identificatorul (numele) procedurii;

<parametrii> - este o lista de variabile numiti si parametrii formali, care se folosesc pentru a mari gradul de generalitate al procedurii si asigura legatura dintre apelant si apelat. Prin intermediul acetei liste se transmit valorile ce se vor prelucra. Acesti parametrii pot sa lipseasca.

<corp_procedura> - sunt comenzile pe care le va executa procedura.

Apelarea unei proceduri se realizeaza cu enuntul:

EXECUTA <nume_procedura>()

Parametrii care apar in apelul de procedura se numes parametrii efectivi; ei specifica de fiecare data cu ce se inlocuiesc parametrii formali ai procedurii.

Functii

Daca procedura calculeaza o singura valoare, se poate utiliza un tip particular de rutina, numit functie. Descrierea unei functii cuprinde: un enunt ce specifica numele functiei si parametrii ei, secventa de operatii care formeaza corpul functiei si cuvantul cheie SFARSIT astfel:

FUNCTIA <nume_functie> (<parametri>) ESTE

<corp_functie>

SFARSIT

Lista parametrilor contine numai parametrii care se transmit functiei, adica parametrii de intrare in functie. Singurul parametru de iesire al functiei este considerat chiar numele functiei, care trebuie sa fie utilizat in secventa de operatii a functiei, <corp_functie>, pentru ca functia sa furnizeze un rezultat atunci cand este apelata.

Si apelul de functie este deosebit fata de apelul de procedura. Pentru a utiliza o functie, apelul acesteia trebuie sa apara intr-o expresie in partea dreapta a semnului egal, ca orice operand. Apelul de functie are forma:

<nume_functie> (<parametri>)

adica numele functiei urmat de parametrii efectivi.