Referat Curs Algoritm

Mai jos puteti citi fragmente din Referat Curs Algoritm si de asemenea puteti face Download Referat Curs algoritm

Citeste fragmente din Referat Curs Algoritm

CAPITOLUL I. DESCRIEREA ALGORITMILOR PRIVATE 1.1 Algoritm, program, programare Apariţia primelor calculatoare electronice a constituit un salt uriaş în direcţia automatizării activităţii umane. Nu există astăzi domeniu de activitate în care calculatorul să nu îşi arate utilitatea. Calculatoarele pot fi folosite pentru a rezolva probleme, numai dacă pentru rezolvarea acestora se concep programe corespunzătoare de rezolvare. Termenul de program (programare) a suferit schimbări în scurta istorie a informaticii. Prin anii 60 problemele rezolvate cu ajutorul calculatorului erau simple şi se găseau algoritmi nu prea complicaţi pentru rezolvarea lor. Prin program se înţelegea rezultatul scrierii unui algoritm într-un limbaj de programare. Din cauza creşterii complexităţii problemelor, astăzi pentru rezolvarea unei probleme adesea vom concepe un sistem de mai multe programe. Dar ce este un algoritm? O definiţie matematică, riguroasă, este greu de dat, chiar imposibilă fără a introduce şi alte noţiuni. Vom încerca în continuare o descriere a ceea ce se înţelege prin algoritm. Ne vom familiariza cu această noţiune prezentând mai multe exemple de algoritmi şi observând ce au ei în comun. Cel mai vechi exemplu este algoritmul lui Euclid, algoritm care determină cel mai mare divizor comun a două numere naturale. Evident, vom prezenta mai mulţi algoritmi, cei mai mulţi fiind legaţi de probleme accesibile absolvenţilor de liceu. Vom constata că un algoritm este un text finit, o secvenţă finită de propoziţii ale unui limbaj. Din cauză că este inventat special în acest scop, un astfel de limbaj este numit 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. Oprindu-ne la semnificaţia algoritmului, la efectul execuţiei lui, vom observa că fiecare algoritm defineşte o funcţie matematică. De asemenea, din toate secţiunile următoare va reieşi foarte clar că un algoritm este scris pentru rezolvarea unei probleme. Din mai multe exemple se va observa însă că, pentru rezolvarea aceleaşi probleme, există mai mulţi algoritmi. Pentru fiecare problemă P există date presupuse cunoscute (date iniţiale pentru algoritmul corespunzător, A) şi rezultate care se cer a fi găsite (date finale). Evident, problema s-ar putea să nu aibă sens pentru orice date iniţiale. Vom spune că datele pentru care problema P are sens fac parte din domeniul D al algoritmului A. Rezultatele obţinute fac parte dintr-un domeniu R, astfel că executând algoritmul A cu datele de intrare x(D vom obţine rezultatele r(R. Vom spune că A(x)=r şi astfel algoritmul A defineşte o funcţie A : D ---> R . Algoritmii au următoarele caracteristici: generalitate, finitudine şi unicitate. Prin generalitate se înţelege faptul că un algoritm este aplicabil pentru orice date iniţiale x(D. Deci un algoritm A nu rezolvă problema P cu nişte date de intrare, ci o rezolvă în general, oricare ar fi aceste date. Astfel, algoritmul de rezolvare a unui sistem liniar de n ecuaţii cu n necunoscute prin metoda lui Gauss, rezolvă orice sistem liniar şi nu un singur sistem concret. Prin finitudine se înţelege că textul algoritmului este finit, compus dintr-un număr finit de propoziţii. Mai mult, numărul transformărilor ce trebuie aplicate unei informaţii admisibile x(D pentru a obţine rezultatul final corespunzător este finit. Prin unicitate se înţelege că toate transformările prin care trece informaţia iniţială pentru a obţine rezultatul r(R sunt bine determinate de regulile algoritmului. Aceasta înseamnă că fiecare pas din execuţia algoritmului dă rezultate bine determinate şi precizează în mod unic pasul următor. Altfel spus, ori de câte ori am executa algoritmul, pornind de la aceeaşi informaţie admisibilă x(D, transformările prin care se trece şi rezultatele obţinute sunt aceleaşi. În descrierea algoritmilor se folosesc mai multe limbaje de descriere, dintre care cele mai des folosite sunt: - limbajul schemelor logice; - limbajul Pseudocod. În continuare vom folosi pentru descrierea algoritmilor limbajul Pseudocod care va fi definit în cele ce urmează. În ultima vreme schemele logice sunt tot mai puţin folosite în descrierea algoritmilor şi nu sunt deloc potrivite în cazul problemelor complexe. Prezentăm însă şi schemele logice, care se mai folosesc în manualele de liceu, întrucât cu ajutorul lor vom preciza în continuare semantica propoziţiilor Pseudocod. 1.2 Scheme logice 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. Prin execuţia unui algoritm descris printr-o schemă logică se înţelege efectuarea tuturor operaţiilor precizate prin blocurile schemei logice, în ordinea indicată de săgeţi. În descrierea unui algoritm, deci şi într-o schemă logică, intervin variabile care marchează atât datele cunoscute iniţial, cât şi rezultatele dorite, precum şi alte rezultate intermediare necesare în rezolvarea problemei. Întrucât variabila joacă un rol central în programare este bine să definim acest concept. Variabila defineşte o mărime care îşi poate schimba valoarea în timp. Ea are un nume şi, eventual, o valoare. Este posibil ca variabila încă să nu fi primit valoare, situaţie în care vom spune că ea este neiniţializată. Valorile pe care le poate lua variabila aparţin unei mulţimi D pe care o vom numi domeniul variabilei. În concluzie vom înţelege prin variabilă tripletul (nume, domeniul D, valoare) unde valoare aparţine mulţimii D ( {nedefinit}. Blocurile delimitatoare Start şi Stop (Fig.1.2.1.a şi 1.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. Blocurile de intrare/ieşire Citeşte şi Tipăreşte (Fig. 1.2.1.c şi 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 (Fig.1.2.1.e). seq Figure * Arabic 1 Fig.1.2.1. Blocurile schemelor logice Blocurile de decizie marchează punctele de ramificaţie ale algoritmului în etapa de decizie. Ramificarea poate fi dublă (blocul logic, Fig.1.2.1.f) sau triplă (blocul aritmetic, Fig. 1.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 hotărî 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 (Fig.1.2.1.h). Pentru exemplificare vom da în continuare două scheme logice, corespunzătoare unor algoritmi pentru rezolvarea problemelor P1.2.1 şi P1.2.2. P1.2.1. Să se rezolve ecuaţia de grad doi aX2+bX+c=0 (a,b,c(R _i a(0). Metoda de rezolvare a ecuaţiei de gradul doi este cunoscută. Ecuaţia poate avea rădăcini reale, respectiv complexe, situaţie recunoscută după semnul discriminantului d = b2 - 4ac. seq Figure * Arabic 2 Algoritmul de rezolvare a problemei va citi mai întâi datele problemei, marcate prin variabilele a, b şi c. Va calcula apoi discriminantul d şi va continua în funcţie de valoarea lui d, aşa cum se poate vedea în fig.1.2.2. Fig.1.2.2. Algoritm pentru rezolvarea ecuaţiei de gradul doi. P1.2.2. Să se calculeze suma elementelor pozitive ale unui şir de numere reale dat. seq Figure * Arabic 3 Schema logică (dată în Fig.1.2.3) va conţine imediat după blocul START un bloc de citire, care precizează datele cunoscute în problemă, apoi o parte care calculează suma cerută şi un bloc de tipărire a sumei găsite, înaintea blocului STOP. Partea care calculează suma S cerută are un bloc pentru iniţializarea cu 0 a acestei sume, apoi blocuri pentru parcurgerea numerelor: x1, x2…xn şi adunarea celor pozitive la suma S. Pentru această parcurgere se foloseşte o variabilă contor i, care este iniţializată cu 1 şi creşte mereu cu 1 pentru a atinge valoarea n, indicele ultimului număr dat. Fig.1.2.3. Algoritm pentru calculul unei sume. Schemele logice dau o reprezentare grafică a algoritmilor cu ajutorul unor blocuri de calcul. Execuţia urmează sensul indicat de săgeată, putând avea loc reveniri în orice punct din schema logică. Din acest motiv se poate obţine o schemă logică încâlcită, greu de urmărit. Rezultă importanţa compunerii unor scheme logice structurate (D-scheme, după Djikstra), care să conţină numai anumite structuri standard de calcul şi în care drumurile de la START la STOP să fie uşor de urmărit. 1.3. Limbajul PSEUDOCOD Limbajul Pseudocod este un limbaj inventat în scopul proiectării algoritmilor şi este format din propoziţii asemănătoare propoziţiilor limbii române, care corespund structurilor de calcul folosite în construirea algoritmilor. Acesta va fi limbajul folosit de noi în proiectarea algoritmilor şi va fi definit în cele ce urmează. Ţinând seama că obţinerea unui algoritm pentru rezolvarea unei probleme nu este întotdeauna o sarcină simplă, că în acest scop sunt folosite anumite metode pe care le vom descrie în capitolele următoare, în etapele intermediare din obţinerea algoritmului vom folosi propoziţii curente din limba română. Acestea sunt considerate elemente nefinisate din algoritm, asupra cărora trebuie să se revină şi le vom numi propoziţii nestandard. Deci limbajul Pseudocod are două tipuri de propoziţii: propoziţii standard, care vor fi prezentate fiecare cu sintaxa şi semnificaţia (semantica) ei şi propoziţii nestandard. Aşa cum se va arăta mai târziu, propoziţiile nestandard sunt texte care descriu părţi ale algoritmului încă incomplet elaborate, nefinisate, asupra cărora urmează să se revină. Pe lângă aceste propoziţii standard şi nestandard, în textul algoritmului vom mai introduce propoziţii explicative, numite comentarii. Pentru a le distinge de celelalte propoziţii, comentariile vor fi închise între acolade. Rolul lor va fi explicat puţin mai târziu. Propoziţiile standard ale limbajului Pseudocod folosite în această lucrare, corespund structurilor de calcul prezentate în figura 1.3.1 şi vor fi prezentate în continuare. Fiecare propoziţie standard începe cu un cuvânt cheie, aşa cum se va vedea în cele ce urmează. Pentru a deosebi aceste cuvinte de celelalte denumiri, construite de programator, în acest capitol vom scrie cuvintele cheie cu litere mari. Menţionăm că şi propoziţiile simple se termină cu caracterul ; în timp ce propoziţiile compuse, deci cele în interiorul cărora se află alte propoziţii, au un marcaj de sfârşit propriu. De asemenea, menţionăm că propoziţiile limbajului Pseudocod vor fi luate în seamă în ordinea întâlnirii lor în text, asemenea oricărui text al limbii române. Prin execuţia unui algoritm descris în Pseudocod se înţelege efectuarea operaţiilor precizate de propoziţiile algoritmului, în ordinea citirii lor. În figura 1.3.1, prin A, B s-au notat subscheme logice, adică secvenţe de oricâte structuri construite conform celor trei reguli menţionate în continuare. Structura secvenţială (fig.1.3.1.a) este redată prin concatenarea propoziţiilor, simple sau compuse, ale limbajului Pseudocod, care vor fi executate în ordinea întâlnirii lor în text. Propoziţiile simple din limbajul Pseudocod sunt CITEŞTE, TIPAREŞTE, FIE şi apelul de subprogram. Propoziţiile compuse corespund structurilor alternative şi repetitive. Structura alternativă (fig.1.3.1.b) este redată în Pseudocod prin propoziţia DACĂ, prezentată în secţiunea 1.3.2, iar structura repetitivă din fig.1.3.1.c este redată în Pseudocod prin propoziţia CÂT TIMP, prezentată în secţiunea 1.3.3. Bohm şi Jacopini [Bohm66] au demonstrat că orice algoritm poate fi descris folosind numai aceste trei structuri de calcul. Propoziţiile DATE şi REZULTATE sunt folosite în faza de specificare a problemelor, adică enunţarea riguroasă a acestora. seq Figure * Arabic h 6 a) structura b) structura c) structura secvenţială alternativă repetitivă Figura 1.3.1. Structurile elementare de calcul Propoziţia DATE se foloseşte pentru precizarea datelor iniţiale, deci a datelor considerate cunoscute în problemă (numite şi date de intrare) şi are sintaxa: DATE listă ; unde listă conţine toate numele variabilelor a căror valoare iniţială este cunoscută. În general, prin listă se înţelege o succesiune de elemente de acelaşi fel despărţite prin virgulă. Deci în propoziţia DATE, în dreapta acestui cuvânt se vor scrie acele variabile care marchează mărimile cunoscute în problemă. Pentru precizarea rezultatelor dorite se foloseşte propoziţia standard REZULTATE listă ; în construcţia "listă" ce urmează după cuvântul REZULTATE fiind trecute numele variabilelor care marchează (conţin) rezultatele cerute în problemă. Acum putem preciza mai exact ce înţelegem prin cunoaşterea completă a problemei de rezolvat. Evident, o problemă este cunoscută atunci când se ştie care sunt datele cunoscute în problemă şi ce rezultate trebuiesc obţinute. Deci pentru cunoaşterea unei probleme este necesară precizarea variabilelor care marchează date considerate cunoscute în problemă, care va fi reflectată printr-o propoziţie DATE şi cunoaşterea exactă a cerinţelor problemei, care se va reflecta prin propoziţii REZULTATE. Variabilele prezente în aceste propoziţii au anumite semnificaţii, presupuse cunoscute. Cunoaşterea acestora, scrierea lor explicită, formează ceea ce vom numi în continuare specificarea problemei. Specificarea unei probleme este o activitate foarte importantă dar nu şi simplă. De exemplu, pentru rezolvarea ecuaţiei de gradul al doilea, specificarea problemei, scrisă de un începător, poate fi: DATE a,b,c; { Coeficienţii ecuaţiei } REZULTATE x1,x2; { Rădăcinile ecuaţiei } Această specificaţie este însă incompletă dacă ecuaţia nu are rădăcini reale. În cazul în care rădăcinile sunt complexe putem nota prin x1, x2 partea reală respectiv partea imaginară a rădăcinilor. Sau pur şi simplu, nu ne interesează valoarea rădăcinilor în acest caz, ci doar faptul că ecuaţia nu are rădăcini reale. Cu alte cuvinte avem nevoie de un mesaj care să ne indice această situaţie (vezi schema logică 1.2.2), sau de un indicator, fie el ind. Acest indicator va lua valoarea 1 dacă rădăcinile sunt reale şi valoarea 0 în caz contrar. Deci specificaţia corectă a problemei va fi DATE a,b,c; { Coeficienţii ecuaţiei } REZULTATE ind, {Un indicator: 1=rădăcini reale, 0=complexe} x1,x2; { Rădăcinile ecuaţiei, în cazul ind=1,} {respectiv partea reală şi cea } {imaginară în cazul ind=0} Evident că specificarea problemei este o etapă importantă pentru găsirea unei metode de rezolvare şi apoi în proiectarea algoritmului corespunzător. Nu se poate rezolva o problemă dacă aceasta nu este bine cunoscută, adică nu avem scrisă specificarea problemei. Cunoaşte complet problema este prima regulă ce trebuie respectată pentru a obţine cât mai repede un algoritm corect pentru rezolvarea ei. 1.3.1. Algoritmi liniari Propoziţiile CITEŞTE şi TIPĂREŞTE sunt folosite pentru iniţializarea variabilelor de intrare cu datele cunoscute în problemă, respectiv pentru tipărirea (aflarea) rezultatelor obţinute. În etapa de programare propriu-zisă acestor propoziţii le corespund într-un limbaj de programare instrucţiuni de intrare-ieşire. Propoziţia CITEŞTE se foloseşte pentru precizarea datelor iniţiale, deci a datelor considerate cunoscute în problemă (numite şi date de intrare) şi are sintaxa: CITEŞTE listă ; unde listă conţine toate numele variabilelor a căror valoare iniţială este cunoscută. Deci în propoziţia CITEŞTE, în dreapta acestui cuvânt se vor scrie acele variabile care apar în propoziţia DATE în specificarea problemei. Se subînţelege că aceste variabile sunt iniţializate cu valorile cunoscute corespunzătoare. Pentru aflarea rezultatelor dorite, pe care calculatorul o va face prin tipărirea lor pe hârtie sau afişarea pe ecran, se foloseşte propoziţia standard TIPĂREŞTE listă ; în construcţia listă ce urmează după cuvântul TIPĂREŞTE fiind trecute numele variabilelor a căror valori dorim să le aflăm. Ele sunt de obicei rezultatele cerute în problemă, specificate şi în propoziţia REZULTATE. Blocului de atribuire dintr-o schemă logică îi corespunde în Pseudocod propoziţia standard [FIE] var := expresie ; Această propoziţie este folosită pentru a indica un calcul algebric, al expresiei care urmează după simbolul de atribuire ":=" şi de atribuire a rezultatului obţinut variabilei var. Expresia din dreapta semnului de atribuire poate fi orice expresie algebrică simplă, cunoscută din manualele de matematică din liceu şi construită cu cele patru operaţii: adunare, scădere, înmulţire şi împărţire (notate prin caracterele +, -, *, respectiv /). Prin scrierea cuvântului FIE între paranteze drepte se indică posibilitatea omiterii acestui cuvânt din propoziţie. El s-a folosit cu gândul ca fiecare propoziţie să înceapă cu un cuvânt al limbii române care să reprezinte numele propoziţiei. De cele mai multe ori vom omite acest cuvânt. Atunci când vom scrie succesiv mai multe propoziţii de atribuire vom folosi cuvântul FIE numai în prima propoziţie, omiţându-l în celelalte. Din cele scrise mai sus rezultă că o variabilă poate fi iniţializată atât prin atribuire (deci dacă este variabila din stânga semnului de atribuire :=) cât şi prin citire (când face parte din lista propoziţiei CITEŞTE). O greşeală frecventă pe care o fac începătorii este folosirea variabilelor neiniţializate. Evident că o expresie în care apar variabile care nu au valori nu poate fi calculată, ea nu este definită. Deci nu folosiţi variabile neiniţializate. Pentru a marca începutul descrierii unui algoritm vom folosi propoziţia: ALGORITMUL nume ESTE: fără a avea o altă semnificaţie. De asemenea, prin cuvântul SFALGORITM vom marca sfârşitul unui algoritm. Algoritmii care pot fi descrişi folosind numai propoziţiile prezentate mai sus se numesc algoritmi liniari. Ca exemplu de algoritm liniar prezentăm un algoritm ce determină viteza v cu care a mers un autovehicul ce a parcurs distanţa D în timpul T. ALGORITMUL VITEZA ESTE: { A1: Calculează viteza } { D = Distanţa (spaţiul) } { T = Timpul; V = Viteza } CITEŞTE D,T; { v:= spaţiu/timp } FIE V:=D/T; TIPĂREŞTE V SFALGORITM 1.3.2 Algoritmi cu ramificaţii Foarte mulţi algoritmi execută anumite calcule în funcţie de satisfacerea unor condiţii. Aceste calcule sunt redate de structura alternativă prezentată în figura 1.3.1.b, căreia îi corespunde propoziţia Pseudocod DACĂ cond ATUNCI A ALTFEL B SFDACĂ sau varianta redusă a ei, DACĂ cond ATUNCI A SFDACĂ folosită în cazul în care grupul de propoziţii B este vid. Aceste propoziţii redau în Pseudocod structura alternativă de calcul. Ele cer mai întâi verificarea condiţiei scrise după cuvântul DACĂ. În caz că această condiţie este adevărată se va executa grupul de propoziţii A. În cazul în care această condiţie este falsă se va executa grupul de propoziţii B, dacă este prezentă ramura ALTFEL. Indiferent care dintre secvenţele A sau B a fost executată, se va continua cu propoziţia următoare propoziţiei DACĂ. O generalizare a structurii alternative realizată de propoziţia DACĂ este structura selectivă: SELECTEAZĂ i DINTRE v1: A1; v2: A2; . . . vn: An SFSELECTEAZĂ structură echivalentă cu următorul text Pseudocod: DACĂ i=v1 ATUNCI A1 ALTFEL DACĂ i=v2 ATUNCI A2 ALTFEL . . . DACĂ i=vn ATUNCI An SFDACĂ ... SFDACĂ SFDACĂ Cu propoziţiile prezentate până aici putem deja descrie destui algoritmi. Aceştia se numesc algoritmi cu ramificaţii. Ca exemplu vom scrie un algoritm pentru rezolvarea ecuaţiei de gradul al doilea. Am scris mai sus specificaţia acestei probleme şi am precizat semnificaţia variabilelor respective. Pe lângă aceste variabile, pentru rezolvarea problemei mai avem nevoie de două variabile auxiliare: delta - pentru a reţine discriminantul ecuaţiei; r - pentru a reţine valoarea radicalului folosit în exprimarea rădăcinilor. Ajungem uşor la algoritmul dat în continuare. ALGORITMUL ECGRDOI ESTE: { Algoritmul 2: Rezolvarea } { ecuaţiei de gradul doi } CITEŞTE a,b,c; { a,b,c = Coeficienţii ecuaţiei } FIE delta:=b*b-4*a*c; DACĂ delta<0 ATUNCI ind:=0; { rădăcini complexe } r:=radical din (-delta); x1:=-b/(a+a); x2:=r/(a+a); ALTFEL ind:=1; { rădăcini reale } r:=radical din delta; x1:=(-b-r)/(a+a); x2:=(-b+r)/(a+a); SFDACĂ TIPĂREŞTE ind, x1,x2; SFALGORITM 1.3.3 Algoritmi ciclici În rezolvarea multor probleme trebuie să efectuăm aceleaşi calcule de mai multe ori, sau să repetăm calcule asemănătoare. De exemplu, pentru a calcula suma a două matrice va trebui să adunăm un element al primei matrice cu elementul de pe aceeaşi poziţie din a doua matrice, această adunare repetându-se pentru fiecare poziţie. Alte calcule trebuiesc repetate în funcţie de satisfacerea unor condiţii. În acest scop în limbajul Pseudocod există trei propoziţii standard: CÂTTIMP, REPETĂ şi PENTRU. Propoziţia CÂTTIMP are sintaxa CÂTTIMP cond EXECUTĂ A SFCÂT i cere execuţia repetată a grupului de propoziţii A, în funcţie de condiţia "cond". Mai exact, se evaluează condiţia "cond"; dacă aceasta este adevărată se execută grupul A şi se revine la evaluarea condiţiei. Dacă ea este falsă execuţia propoziţiei se termină şi se continuă cu propoziţia care urmează după SFCÂT. Dacă de prima dată condiţia este falsă grupul A nu se va executa niciodată, altfel se va repeta execuţia grupului de propoziţii A până când condiţia va deveni falsă. Din cauză că înainte de execuţia grupului A are loc verificarea condiţiei, această structură se mai numeşte structură repetitivă condiţionată anterior. Ea reprezintă structura repetitivă prezentată în figura 1.3.1.c. Ca exemplu de algoritm în care se foloseşte această propoziţie dăm algoritmul lui Euclid pentru calculul celui mai mare divizor comun a două numere. ALGORITMUL Euclid ESTE: {A3: Cel mai mare divizor comun} CITEŞTE n1,n2; {Cele două numere a căror divizor se cere} FIE d:=n1; i:=n2; CÂTTIMP i(0 EXECUTĂ r:=d modulo i; d:=i; i:=r SFCÂT TIPĂREŞTE d; { d= cel mai mare divizor comun al } SFALGORITM { numerelor n1 şi n2 } În descrierea multor algoritmi se întâlneşte structura repetitivă condiţionată posterior: REPETĂ A PÂNĂ CÂND cond SFREP structură echivalentă cu: CÂTTIMP not(cond) EXECUTĂ A SFCÂT Deci ea cere execuţia necondiţionată a lui A şi apoi verificarea condiţiei "cond". Va avea loc repetarea execuţiei lui A până când condiţia devine adevărată. Deoarece condiţia se verifică după prima execuţie a grupului A această structură este numită structura repetitivă condiţionată posterior, prima execuţie a blocului A fiind necondiţionată. O altă propoziţie care cere execuţia repetată a unei secvenţe A este propoziţia PENTRU c:=li ;lf [;p] EXECUTĂ A SFPENTRU Ea defineşte structura repetitivă predefinită, cu un număr determinat de execuţii ale grupului de propoziţii A şi este echivalentă cu secvenţa c:=li ; final:=lf ; REPETĂ A c:=c+p PÂNĂCÂND (c>final şi p>0) sau (cvalmax ATUNCI valmax:=xi SFDACĂ SFPENTRU TIPĂREŞTE valmin,valmax; SFALGORITM Un rol important în claritatea textului unui algoritm îl au denumirile alese pentru variabile. Ele trebuie să reflecte semnificaţia variabilelor respective. Deci alege denumiri sugestive pentru variabile, care să reflecte semnificaţia lor. În exemplul de mai sus denumirile valmin şi valmax spun cititorului ce s-a notat prin aceste variabile. 1.4 Calculul efectuat de un algoritm Fie X1, X2, ..., Xn, variabilele ce apar în algoritmul A. În orice moment al execuţiei algoritmului, fiecare variabilă are o anumită valoare, sau este încă neiniţializată. Vom numi stare a algoritmului A cu variabilele menţionate vectorul s = ( s1,s2,...,sn ) format din valorile curente ale celor n variabile ale algoritmului. Este posibil ca variabila Xj să fie încă neiniţializată, deci să nu aibă valoare curentă, caz în care sj este nedefinită, lucru notat în continuare prin semnul întrebării ? . Prin executarea unei anumite instrucţiuni unele variabile îşi schimbă valoarea, deci algoritmul îşi schimbă starea. Se numeşte calcul efectuat de algoritmul A o secvenţă de stări s0, s1, s2, ..., sm unde s0 este starea iniţială cu toate variabilele neiniţializate, iar sm este starea în care se ajunge după execuţia ultimei propoziţii din algoritm. 1.5 Rafinare în paşi succesivi Adeseori algoritmul de rezolvare a unei probleme este rezultatul unui proces complex, în care se iau mai multe decizii şi se precizează tot ceea ce iniţial era neclar. Observaţia este adevărată mai ales în cazul problemelor complicate, dar şi pentru probleme mai simple în procesul de învăţământ. Este vorba de un proces de detaliere pas cu pas a specificaţiei problemei, proces denumit şi proiectare descendentă, sau rafinare în paşi succesivi. Algoritmul apare în mai multe versiuni succesive, fiecare versiune fiind o detaliere a versiunii precedente. În versiunile iniţiale apar propoziţii nestandard, clare pentru cititor, dar neprecizate prin propoziţii standard. Urmează ca în versiunile următoare să se revină asupra lor. Algoritmul apare astfel în versiuni succesive, tot mai complet de la o versiune la alta. Apare aici o altă regulă importantă în proiectarea algoritmului: amână pe mai târziu detaliile nesemnificative; concentrează-ţi atenţia la deciziile importante ale momentului.  CAPITOLUL AL II-LEA. SUBALGORITMI PRIVATE 2.1 Conceptul de subalgoritm Orice problemă poate apare ca o subproblemă S a unei probleme mai complexe C. Algoritmul de rezolvare a problemei S devine în acest caz un subalgoritm pentru algoritmul de rezolvare a problemei C. Pentru a defini un subalgoritm vom folosi propoziţia standard SUBALGORITMUL nume (lpf) ESTE: unde nume este numele subalgoritmului definit, iar lpf este lista parametrilor formali. Aceştia sunt formaţi din variabilele care marchează datele de intrare (cele presupuse cunoscute) şi variabilele care marchează datele de ieşire (rezultatele obţinute de subalgoritm). Această propoziţie este urmată de textul efectiv al subalgoritmului, text care precizează calculele necesare rezolvării subproblemei corespunzătoare. Descrierea se va încheia cu cuvântul SFSUBALGORITM sau SF-nume. Dăm ca exemplu un subalgoritm cu numele MAXIM, care găseşte maximul dintre componentele vectorului X = (x1,x2, ..., xn). Datele cunoscute pentru acest subalgoritm sunt vectorul X şi numărul n al componentelor vectorului X. Ca rezultat vom obţine maximul cerut, pe care-l vom nota cu max. Deci lista parametrilor formali conţine trei variabile, n, X şi max. Subalgoritmul este dat în continuare. SUBALGORITMUL maxim(n,X,max) ESTE: FIE max:=x1; PENTRU i:=2;n EXECUTĂ DACĂ xi>max ATUNCI max:=xi SFDACĂ SFPENTRU SF-maxim În cadrul multor algoritmi este necesar calculul valorilor unei funcţii în diferite puncte. Este necesar să definim funcţia printr-un subalgoritm de tip funcţie. Pentru definirea unui subalgoritm de tip funcţie se foloseşte un antet care precizează numele funcţiei şi variabilele de care depinde ea. Subalgoritmul are forma: FUNCŢIA nume(lpf) ESTE: {Antetul funcţiei} text {corpul funcţiei} SF-nume {marca de sfârşit} În corpul funcţiei trebuie să existe cel puţin o atribuire în care numele funcţiei apare în partea stângă, deci prin care funcţia primeşte o valoare. Dăm ca exemplu o funcţie numar : R --> {2,3,4,5}, definită matematic astfel: În Pseudocod descrierea este următoarea: FUNCŢIA numar(x) ESTE: DACĂ x<0.2 ATUNCI numar:=2 ALTFEL DACĂ x<0.5 ATUNCI numar:=3 ALTFEL DACĂ x<0.9 ATUNCI numar:=4 ALTFEL numar:=5 SFDACĂ SFDACĂ SFDACĂ SF-numar Am văzut că definiţia unei funcţii constă dintr-un antet şi dintr-un bloc care va defini acţiunile prin care se calculează valoarea funcţiei. În antet se precizează numele funcţiei şi lista parametrilor formali. În concluzie, există două categorii de subalgoritmi: de tip funcţie şi subalgoritmi propriu-zişi, cărora li se mai spune şi proceduri. Importanţa lor va fi subliniată prin toate exemplele care urmează în acest curs. În încheiere menţionăm că subprogramele de tip funcţie se folosesc în scopul definirii funcţiilor, aşa cum sunt cunoscute ele din matematică, în timp ce subalgoritmii de tip procedură se referă la rezolvarea unor probleme ce apar ca subprobleme, fiind algoritmi de sine stătători. 2.2 Apelul unui subalgoritm Am văzut că un subalgoritm este dedicat rezolvării unei subprobleme S a unei probleme mai complexe C. Algoritmul corespunzător problemei C va folosi toate operaţiile necesare rezolvării problemei S, deci va folosi ca parte întregul subalgoritm conceput pentru rezolvarea subproblemei S. Spunem că el va apela acest subalgoritm. În Pseudocod apelul unei funcţii se face scriind într-o expresie numele funcţiei urmat de lista parametrilor actuali. Trebuie să existe o corespondenţă biunivocă între parametrii actuali şi cei formali folosiţi în definiţia funcţiei. Deşi denumirile variabilelor din cele două liste pot să difere, rolul variabilelor care se corespund este acelaşi. Mai exact, parametrul formal şi parametrul actual corespunzător trebuie să se refere la aceeaşi entitate, trebuie să aibă aceeaşi semnificaţie, să reprezinte aceeaşi structură de date. Putem considera că în timpul execuţiei algoritmului cei doi parametri devin identici. Folosirea unui subalgoritm în cadrul unui algoritm se face apelând acest subalgoritm prin propoziţia standard CHEAMĂ nume (lpa); unde nume este numele subalgoritmului apelat iar lpa este lista parametrilor actuali. Această listă conţine toate datele de intrare (cele cunoscute în subproblema corespunzătoare) şi toate rezultatele obţinute în subalgoritm. Şi în acest caz între lista parametrilor formali din definiţia subalgoritmului şi lista parametrilor actuali din propoziţia de apel trebuie să existe o corespondenţă biunivocă, ca şi în cazul funcţiilor. Ca o primă verificare a respectării acestei corespondenţe, subliniem că numărul parametrilor actuali trebuie să coincidă cu numărul parametrilor formali. Ca exemplu de apelare a funcţiilor, dăm în continuare un program pentru a calcula a câta zi din anul curent este ziua curentă (zi,luna,an). El foloseşte un subprogram de tip funcţie pentru a obţine numărul zilelor lunii cu numărul de ordine i şi un altul pentru a verifica dacă un an este bisect sau nu. Aceste două funcţii sunt: - NRZILE(i) furnizează numărul zilelor existente în luna i a unui an nebisect; - BISECT(an) adevărată dacă anul dintre paranteze este bisect. Algoritmul este următorul: ALGORITMUL NUMĂRĂZILE ESTE: CITEŞTE zi, luna, an; FIE nr:=zi; DACĂ luna>1 ATUNCI PENTRU i:=1, Luna-1 EXECUTĂ nr:=nr+NRZILE(i) SFPENTRU SFDACĂ DACĂ luna>2 ATUNCI DACĂ BISECT(an) ATUNCI nr:=nr+1 SFDACĂ SFDACĂ TIPĂREŞTE nr; SFALGORITM Să observăm că în proiectarea acestui algoritm nu este necesar să cunoaştem textul subalgoritmilor folosiţi, ci doar specificarea acestor subalgoritmi, numele lor şi lista parametrilor formali. La acest nivel accentul trebuie să cadă pe proiectarea algoritmului care apelează, urmând să se revină ulterior la proiectarea subalgoritmilor apelaţi, conform specificaţiei acestora. În cazul de faţă este necesară descrierea funcţiilor NRZILE(i) şi BISECT(an). Lăsăm această descriere ca temă pentru cititor. Ca exemplu de apelare a unei proceduri vom scrie mai jos o procedură care efectuează suma a două polinoame. Un polinom P(X) este dat prin gradul său, m, şi prin vectorul coeficienţilor P = (p0, p1, ..., pm) (prin pi s-a notat coeficientul lui Xi). Procedura SUMAPOL(m,P,n,Q,r,S) trebuie să efectueze suma S(X) = P(X)+Q(X), unde P este un polinom de gradul m, iar Q este un polinom de gradul n, date. Suma lor, S, va fi un polinom de gradul r calculat în subalgoritm. Pentru efectuarea ei este utilă o altă procedură care adună la suma S(X) un alt polinom, T(X), de grad mai mic sau egal decât gradul polinomului S(X). O astfel de procedură se dă în continuare. SUBALGORITMUL SUMAPOL1(n,T,r,S) ESTE: {n ( r} {S(X):=S(X)+T(X)} PENTRU i:=0;n EXECUTĂ si := si+ti SFPENTRU SF-SUMAPOL1 Subalgoritmul SUMAPOL apelează acest subalgoritm, aşa cum se poate vedea în continuare. SUBALGORITMUL SUMAPOL(m,P,n,Q,r,S) ESTE: {S(X):=P(X)+Q(X)} DACĂ mmi+1 ATUNCI {schimbă ordinea celor} FIE t := mi; {două elemente} mi:=mi+1; mi+1:=t; ind:=1; {Cazul M nu era ordonată} SFDACĂ SFPENTRU PÂNĂCÂND ind=0 SFREP SF-ORDON SUBALGORITMUL REUNIUNE(m,A,n,B,k,R) ESTE: { R := A U B } { k = numărul elementelor mulţimii R } FIE k:=m; R := A; PENTRU j:=1,n EXECUTĂ FIE ind:=0; {Ipoteza bj nu e in A} PENTRU i:=1;m EXECUTĂ DACĂ bj=ai ATUNCI ind:=1 {bj este in A} SFDACĂ SFPENTRU DACĂ ind=0 ATUNCI k:=k+1; rk:=bj SFDACĂ SFPENTRU SF-REUNIUNE SUBALGORITMUL TIPMUL(n,M) ESTE: { Tipăreşte cele n elemente } PENTRU i:=1;n EXECUTĂ { ale mulţimii M } TIPĂREŞTE mi SFPENTRU SF-TIPMUL SUBALGORITMUL TIPORDON(n,M) ESTE: { Ordonează şi tipăreşte } CHEAMĂ ORDON(n,M); { elementele mulţimii M } CHEAMĂ TIPMUL(n,M); SF-TIPORDON Tot ca exemplu de folosire a subalgoritmilor, vom scrie un algoritm pentru rezolvarea următoarei probleme: dirigintele unei clase de elevi doreşte să obţină un clasament al elevilor în funcţie de media generală. În plus, pentru fiecare disciplină în parte doreşte lista primilor şase elevi. În rezolvarea acestei probleme este necesară găsirea ordinii în care trebuiesc tipăriţi elevii în funcţie de un anumit rezultat: nota la disciplina "j", sau media generală. Am identificat prin urmare două subprobleme independente, referitoare la: (1) aflarea ordinii în care trebuie tipărite n numere pentru a le obţine ordonate; (2) tipărirea elevilor clasei într-o anumită ordine. Prima subproblemă se poate specifica astfel: Dându-se numerele x1, x2, ... , xn, găsiţi ordinea o1, o2, ..., on, în care aceste numere devin ordonate descrescător, adică x[o1] ( x[o2] ( ... x[on] . Pentru rezolvarea ei vom da un subalgoritm ORDINE în care intervin trei parametri formali: - n, numărul valorilor existente; - X, vectorul acestor valori; - O, vectorul indicilor care dau ordinea dorită. Primii doi parametri marchează datele presupuse cunoscute, iar al treilea, rezultatele calculate de subalgoritm. SUBALGORITMUL ORDINE(n,X,O) ESTE: {n, numărul valorilor existente} {X, vectorul acestor valori} {O, vectorul indicilor care dau ordinea dorită} PENTRU i:=1; n EXECUTĂ oi :=i SFPENTRU REPETĂ ind:=0; PENTRU i:=1;n-1 EXECUTĂ DACĂ x[oi] < x[oi+1] ATUNCI FIE ind:=1; t:=oi+1 ; oi+1 :=oi; oi :=t; SFDACĂ SFPENTRU PANÂCÂND ind=0 SFREP SF-ORDINE A doua subproblemă se poate specifica astfel: Dându-se ordinea o1,o2, ..., on, a elevilor clasei, numele şi mediile acestora, să se tipărească numele şi mediile primilor k elevi în ordinea specificată. Subalgoritmul TIPAR, dat în continuare, rezolvă această problemă. SUBALGORITMUL TIPAR(k, NUME, O) ESTE: PENTRU i:=1;k EXECUTĂ Tipăreşte datele elevului de rang oi. SFPENTRU SF-TIPAR Variabilele folosite pentru problema dată sunt următoarele: - n reprezintă numărul elevilor clasei; - m este numărul disciplinelor la care elevii primesc note; - NUME este vectorul care reţine numele elevilor: NUMEi este numele elevului cu numărul de ordine i; - NOTE este matricea notelor elevilor, având n linii şi m coloane; NOTEi,j este nota elevului cu numele NUMEi la disciplina cu numărul de ordine j; NOTE.j este coloana a j-a a matricei NOTE şi reprezintă notele elevilor la disciplina j; - MEDII este vectorul mediilor generale. Algoritmul se dă în continuare: ALGORITMUL CLASAMENT ESTE: { Algoritmul 7: Ordonare } CITEŞTE m, {numărul disciplinelor şi} n, {al elevilor} NUMEi, i=1,n, {numele elevilor} NOTEi,j, j=1,m, i=1,n; {notele elevilor} PENTRU i:=1;n EXECUTĂ { calculează media generală} FIE S:=0; {a elevului i} PENTRU j:=1;m EXECUTĂ S:=S+NOTEi,j SFPENTRU FIE MEDIIi:=S/m SFPENTRU CHEAMĂ ORDINE(n,MEDII,O); CHEAMĂ TIPAR(n,NUME,O) PENTRU j:=1;m EXECUTĂ CHEAMĂ ORDINE(n,NOTE.j,O); CHEAMĂ TIPAR(6,NUME,O); SFPENTRU SF-ALGORITM Apel recursiv În exemplele date se observă că apelul unui subprogram se face după ce el a fost definit. Este însă posibil ca un subalgoritm să se apeleze pe el însuşi. Într-un astfel de caz spunem că apelul este recursiv, iar subalgoritmul respectiv este definit recursiv. Ca exemplu, definim în continuare o funcţie care calculează recursiv valoarea n!. Se va folosi formula n! = n.(n-1)! în cazul n>0 şi faptul că 0!=1. Recursivitatea constă în faptul că în definiţia funcţiei Factorial de n se foloseşte aceeaşi funcţie Factorial dar de argument n-1. Deci funcţia Factorial se apelează pe ea însăşi. Este important ca numărul apelurilor să fie finit, deci ca procedeul de calcul descris să se termine. FUNCTIA Factorial(n) ESTE: DACĂ n=0 ATUNCI Factorial:=1 ALTFEL Factorial:= n*Factorial(n-1) SFDACĂ SF-Factorial; Tot ca exemplu de apel recursiv putem descrie o funcţie ce calculează maximul a n numere x1,x2,...,xn . Ea se bazează pe funcţia MAXIM2 care calculează maximul a două numere, descrisă în continuare. FUNCŢIA MAXIM2(a,b) ESTE: DACĂ a