Universitatea din Bacu Facultatea de tiine Catedra de Matematic i Informatic Specializarea Informatic Forma de nvmnt cu frecven redus Anul I, semestru 1 Disciplina PROGRAMARE PROCEDURAL Titular de curs BOGDAN PTRU BOGDAN PTRU PROGRAMARE PROCEDURAL Curs pentru Informaic IFR Bacu, 2008 2Cuvnt nainte Cursulipropunesfamiliarizezestudeniicuprincipalelenoiunidespreprogramare procedural.Dupcesedefinescconceptelefundamentaledespredate,algoritmi,sefaceo introducerenconcepteledebazaleprogramriistructurate.Urmtoarelecapitolesereferla subprograme,apoisetrecnrevisttehniciledeprogramare(greedy,backtracking,divideet imper), noiuni despre complexitatea algoritmilor i lucrul cu structurile de date dinamice. Cursul se adreseaz studenilor din anul I, profilul Informatic i este urmat de acetia n semestrul IalanuluiIdefacultate,avndoprelegerededouorepesptmn.Estensoitdelucrride laborator, ce se vor desfura n edine sptmnale de cte dou ore. Cursul poate fi studiat i de ali studeni de la seciile economice, inginerie etc., precum ide orice persoan dornic s ptrund n tainele programrii procedurale. Parcurgereacursuluipresupuneobuncunoatereamoduluideoperarecuuncalculator electronic i, de asemenea, noiuni de limba englez. Deoareceaceastaesteocartedespretehnicaprogramrii,limbajuldeprogramarefolosit este mai puin important. n cadrul textului pot fi observate diferite pictograme care pot ghida cititorul (profesor sau elev) n procesul e predare/nvare. Astfel,urmtoarelesimbolurisemnifictipuldeleciesaumetoddidacticindicatafi folosit cu precdere n cadrul leciei, pe care le recomandm profesorului: Metode comunicative Metode conversative Lectura independent a elevilor Lecie de laborator Lecie de verificare i notare a elevilor Observaii i comentarii n legtur cu obiectivele specifice ale unui capitol sau lecie 3Alte simboluri sunt folosite pentru a marca diferitele activiti ale studenilor: Observaiemenitslmureascchestiunidefineesau deosebite n cadrul textului ~ Atenie! Averizarea cititorului asupra unor chestiuni importante; altfel, cititorul grbit risc s le trateze superficial. ? ntrebriiexerciiideautoverificare,cupatrugradede dificultate, dup cum urmeaz: (nivel sczut) (nivel mediu) (nivel ridicat) e (nivel foarte ridicat) Rezumatulcapitolului,cuscopuldeasistematizamateria predat i de a sedimenta cunotinele acumulate. Neexprimmdorinacacestesimboluri,alturidefigurileiexplicaiilecarensoesc fiecareproblemstudiatvorfacedinaceastcarteunmanualutilelevilor,dariacelor specialiticarevorsptrundntaineletehnicilordeprogramare,aceloracarenuvorsse rezume doar la cunoaterea unui limbaj de programare. Simbolurile menionate nu indic obligaii din partea profesorului sau a elevilor si, ci sunt doar recomandri pe care le facem cititorilor. ncheiem cu sperana c aceast lucrare va fi de folos tuturor cititorilor si. Autorul Refereni tiinifici: conf. univ. dr. Mihai Talmaciu, Universitatea din Bacu, decanul Facultii de tiine conf. univ. dr. Elena Nechita, Universitatea din Bacu, Facultatea de tiine, eful Catedrei de Matematic i Informatic 4Cuprins Tematica seminariilor i a lucrrilor practice Mod de notare Capitolul 1. Introducere - prelegerea I Capitolul 2. Date - prelegerea I 2.1. Constante i variabile. Expresii 2.2. Tipuri de date simple 2.3. Tipuri de date structurate Capitolul 3. Algoritmi - prelegerea a I 3.1. Etapele rezolvrii unei probleme 3.2. Definiia algoritmului 3.3. Caracteristicile algoritmului Capitolul 4. Elementele programrii structurate - prelegerea a II-a 4.1. Structurile de baz 4.2. Structurile auxiliare 4.3. Teorema programrii structurate 4.4. Instruciunea de atribuire. Operaii de intrare i ieire 4.5. Implementarea structurilor de control 4.6. Exemple de algoritmi 4.7. Complexitatea algoritmilor Capitolul 5. Subprograme - prelegerea a III-a 5.1. Definirea subprogramelor 5.2. Circuitul datelor ntre subprograme Capitolul 6. Metoda backtracking prelegerea a IV-a i a V-a 6.1. Prezentare general 6.2. Exemple i aplicaii 6.2.1. Problema celor opt dame 6.2.2. Generarea funciilor injective 6.2.3. Aezarea cailor 6.2.4. Generarea partiiilor unui numr natural 6.2.5. Plata unei sume cu bancnote de valori date 6.2.6. Generarea produsului cartezian a mai multor mulimi 6.2.7. Generarea submulimilor unei multimi 6.2.8. Generarea combinrilor 6.2.9. Problema discret a rucsacului 6.2.10. Generarea funciilor surjective 6.2.11. Generarea partiiilor unei mulimi 6.2.12. Colorarea hrilor 6.2.13. Circuitul hamiltonian 5Capitolul 7. Recursivitate prelegerea a VI-a, a VII-a i a VIII-a 7.1. Prezentare general 7.1.1. Mecanismul recursivitii 7.1.2. Condiia de consisten a unei definiii recursive 7.1.3. Utilizarea stivelor n recursivitate 7.2. Funcii recursive 7.2.1. Inversarea recursiv a unui cuvnt 7.2.2. irul lui Fibonacci 7.2.3. Cel mai mare divizor comun 7.2.4. Funcia lui Ackermann 7.2.5. Suma cifrelor unui numr ntreg 7.2.6. Suma elementelor unui vector 7.2.7. Existena unui element ntr-un vector 7.3. Proceduri recursive 7.3.1. Suma componentelor unui vector 7.3.2. Inversarea unui cuvnt 7.3.3. inversarea elementelor dintr-un ir 7.3.4. Transformarea din baza 10 n alt baz 7.4. Varianta recursiv a metodei Back-tracking 7.4.1. Problema celor opt regine 7.4.2. Generarea funciilor injective 7.4.3. Generarea partiiilor unui numr natural 7.4.4. Plata unei sume cu bancnote de valori date 7.5. Backtracking n plan 7.5.1. Problema labirintului 7.5.2. Acoperirea unei table de ah prin sritura calului 7.5.3. Algoritmul de acoperire a unei suprafee delimitate de un contur nchis 7.5.4. Problema fotografiei 7.6. Metoda Divide-et-impera 7.6.1. Prezentare general 7.6.2. Determinarea maximului si minimului unui ir 7.6.3. Metoda cutarii binare 7.6.4. Cutarea prin interpolare 7.6.5. Turnurile din Hanoi 7.6.6. Sortare rapid prin partiionare 7.6.7. Sortare prin interclasare 7.7. Alte probleme ale cror rezolvri se pot defini n termeni recursivi 7.7.1. Generarea partiiilor unei mulimi 7.7.2. Figuri recursive 7.7.3. Explorarea grafurilor n adncime 7.8. Recursivitate indirect. Directiva forward 7.8.1. irul mediilor aritmetico-geometrice al lui Gauss. 7.8.2. Deplasarea pe ecran a unui text. 7.8.3. Transformarea unei expresii aritmetice n forma polonez prefixat Capitolul 8. Metoda Greedy prelegerea a IX-a i a X-a 8.1. Prezentare general 8.2. Probleme pentru care metoda Greedy determin soluia optim 8.2.1. Maximizarea/minimizarea valorii unei expresii 8.2.2. Problema spectacolelor8.2.3. Problema continu a rucsacului 8.2.4. Algoritmul lui Dijkstra pentru drumuri de cost minim n grafuri 8.2.5. Arborele parial de cost minim 68.3. Probleme pentru care metoda Greedy nu determin soluia optim 8.3.1. Problema comis-voiajorului 8.3.2. Problema colorrii hrilor Capitolul 9. Structuri dinamice de date prelegerea a XI-a i a XII-a 9.1. Tipul referin. Noiunea de variabil dinamic 9.1.1. Variabile statice i variabile dinamice 9.1.2. Definirea unui tip referin 9.1.3. Utilizarea variabilelor dinamice. Avantaje 9.2. Liste 9.2.1. Operaii elementare: inserare, cutare i eliminare element 9.2.2. Stive i cozi. Operaii specifice 9.2.3. Liste dublu nlnuite. Operaii specifice 9.2.4. Liste circulare 9.2.5. Sortare topologic 9.3. Arbori 9.3.1. Arbori binari 9.3.2. Arborele binar asociat unei expresii algebrice 9.3.3. Arbori oarecare 9.3.4. Vizualizarea structurii arborescente de directoare Capitolul 10. Probleme recapitulative prelegerea a XIII-a i a XIV-a 7 Tematica seminariilor i a lucrrilor practice Acestea se vor desfura n laboratorul de informatic, despre care se presupune c poate asigura lucrul a maxim doi studeni la un calculator performant. Orele de practic trebuie s le succead peceledeteorie,delacurs.Petoatduratacursului,esterecomandabilcastudeniislucreze suplimentar n laboratorul de informatic, mai ales cnd vor trebui s-i realizeze aplicaia proprie (discutat n edinele de laborator 9-13). edina 1a. Recapitulare - edin de tip seminar Studeniivorfitestaiasupramoduluincaretiusutilizezeuncalculator,caoperatoriai sistemuluideoperareialunorprodusedebirotic(procesordetexte,detabele,editorgrafic). Laboratorulpoatesconsteanelaborareauneilucrricomplexe,caresmbinelucrulcudiferite pachete de programe. edina 1b. Date i modaliti de reprezentare a datelor - edin de tip seminar ndiscuiesevaabordatemanoiuniidedat.Sevorclasificadatele,sevordaexemplede modaliti de reprezentare a datelor, modelnd situaii din lumea real. edina 2a. Algoritmi - edin de tip seminar Se va discuta cu studenii, sub forma unor studii de caz, care sunt etapele rezolvrii unei probleme. Sevorformuladiferiteprobleme isevastudiacaredinelepotfirezolvateprinalgoritmi icare nu. Se vor enuna caracteristicile algoritmilor i se va discuta pe marginea acestei teme. edina 2b. Elementele programrii structurate - edin de tip seminar+laborator Se vor trece n revist structurile de control folosite n programarea procedural, exemplificndu-se prin scrierea unor algoritmi de calcule matematice i financiar-contabile, precum i a unor algoritmi de cutare isortare.Algoritmiivorfiimplementaui sub forma unor simple programe n limbajul utilizatdemediuldeprogramarecevafipredatulterior(Pascal,C,VisualBasic,Delphi,Visual FoxPro etc.). n final, vor fi analizai algoritmii din punct de vedere al complexitii lor. edinele 3 i 4. Metoda backtracking - edin de tip laborator Vor fi tratate diferite aspecte ale metodei backtracking i se vor rezolva probleme edinele 5 i 6. Recursivitate - edin de tip laborator Sevorrealizaprogramesimplecaresfoloseascrecursivitatea.Programelevorfiscrisen limbajul de programare ales. Se va folosi metoda divide et impera sau backtracking recursiv edinele 7 i 8. Metoda greedy - edin de tip laborator Vor fi tratate diferite aspecte ale metodei greedy i se vor rezolva probleme edinele 9 i 10. Structuri dinamice de date - edin de tip laborator Vor fi implementate structurile de list simplu nlnuit, coad, stiv, list dublu nlnuit, arbore binar, arbore oarecare i se vor rezolva diferite probleme cu aceste structuri. edinele 11, 12 i 13. Lucrare practic - edine de tip laborator Pe parcusul acestor edine, studenii vor lucra n echipe de 2-4 persoane pentru realizarea concret a unei aplicaii concrete, sub ndrumarea i coordonarea cadrului didactic. Lucrul studenilor nu se 8varezumadoarlaceledouorespmnale,cuprinsenplanuldenvmnt,ciinstudiul individual,acassaunlaboratoruldeinformatic.Laoreledelaborator,studeniivorprezenta cadruluididactic,sptmnal,stadiullacareauajunsculucrarea,ceproblemeauntmpinat,iar cadruldidactic ivaajutaslesoluioneze i le va sugera mbuntiri ce pot fi aduse lucrrii. La final, lucrarea practic realizat de studeni trebuie s fie nsoit i de un document scris, n care se prezint scopul, modul de realizare i de utilizare a aplicaiei. edina 14. Prezentarea lucrrii practice - edin de tip colocviu n aceast ultim lucrare, studenii vor prezenta aplicaia realizat comisiei de notare. Comisia va fi format din cadrul didactic de la seminar, titularul de curs i doi reprezentani numii de studeni i evideniai prin aportul lor deosebit la desfurarea orelor de laborator. Mod de notare CursuldeProgramareacalculatoarelorelectronicesetermincuexamen,ncarestudeniivor primi o not, calculat ca o medie ponderat dup cum urmeaz: Forma de verificare (Examen, Colocviu)E Modalitatea de susinere (Scris i Oral, Oral)SOPuncte sau procentajRspunsuri la examene, colocviu30% Evaluare activiti aplicative (laborator, proiect) proiect40% Prezen activ la curs i seminar10% Teme de cas sau studiu individual20% NOTARE TOTAL PUNCTE SAU PROCENTE100% 9 Capitolul 1. Introducere Diferii autori dau diferite definiii informaticii, dar, n esen, tote aceste definiii facapellaorigineacuvntului.Cuvntulinformaticprovinedinfranuzescul informatique,care,larndu-iprovinedininformation=informaieiautomatique=n mod automat, automatic. Informaticaesteuncomplexdedisciplinetiinificecareseocupdeprelucrareai transmiterea electronic a informaiei. Firete, o asemenea definiie presupune ca noi s tim ce nseamn att informaia, ct i ce se nelege prin prelucrare i transmitere electronic. Conceptul de informaie este strns legat de cel de dat. Datelesuntnumere,caractere,imaginisauoricealtemodalitidereprezentare (nregistrare)aunorentitirealentr-oformcepoatefiaccesatdeomsau,nmodspecial, introdus ntr-un calculator, stocat i procesat acolo sau transmis pe cale electronic. Odatnuareeansiunneles,dectcndesteinterpretatdeunanumitsistemde prelucrare a datelor, care i d un neles i atunci data devine informaie. Datelepotfireprezentatepebazaunorabloaneiputemobineinformaii,prin interpretarea lor. Informaiile sunt utilizate pentru a ne spori cunotinele. Exemple: 1234567.89 este dat. "Contul meu bancar a crescut de 80 de ori, ajungnd la 1234567.89 mii lei" este informaie. "Nimeni nu are atia bani ca mine." este cunotin. Pentru a nelege mai bine cum stau lucrurile, s considerm un caz concret din realitate. La ofacultatesedconcursdeadmitere.Numelecandidailorinoteleobinutedeeisuntdate.Se realizeaz o list a candidailor mpreun cu notele acestora.Lista poate fi considerat o informaie, pentru c fiecare element al listei, constituit dintr-un nume i un numr, are o anumit semnificaie.Lista este ordonat n ordinea descresctoare a notelor. Acesta este un proces de prelucrare a informaiilorsauadatelor.Seobinalteinformaiisaudate,carecompunlistaordonat.Dac ordonarea a fost realizat cu ajutorul unui calculator electronic, nseamn c a avut loc o prelucrare automat a datelor, prin mijloace electronice.Ulterior,listaordonatvaputeafitransmisministerului,fieprinpot,fiepeci electronice (de pild prin pot electronic). Unitatea de msur a datelor/informaiei este bitul, o cifr (engl. digit) care poate fi 0 sau 1. S-aconstatatcsistemuldenumeraiebinar(carefolosetedoarceledoucifre)poatefiutilizat 10pentru a reprezenta orice informaie. Reprezentarea binar a unei informaii se numete i digitizare. De fapt, putem observa cu uurin c toat natura are o organizare binar. Multiplul bitului este: octetul (sau byte-ul), care este o grupare de 8 bii. Multiplii octetului sunt: kilooctetul sau kilobyte-ul (notat Kb sau Ko) 1 Kb = 1024 bytes (octei) megaoctetul sau megabyte-ul (notat Mb sau Mo) 1Mb = 1024 Kogigaoctetul sau gigabyte-ul (notat Gb sau Go) 1 Gb = 1024 Mb (1024 = 210) Spuneam c informatica este un complex de discipline tiinifice ce rezolv astfel de probleme. Astfel,distingem,ncadrulinformaticiiurmtoareledisciplinemaiimportante,careconstituietot attea direcii de studiu i cercetare: Arhitectura calculatoarelor - se ocup de componentele fizice (hardware) ale unui calculator, de modul lor de funcionare, precum i de legturile existente ntre ele; Sisteme de operare - se ocup de componenta software de baz a unui calculator (sistemul de operare),demoduldeproiectareaacestuia,defelulncarepotfigetionatemaieficient resursele fizice ale calculatorului (memoria, procesorul, discurile); Reele de calculatoare - reprezint o disciplin strns legat de cele dou anterioare, ocupndu-sedemodulderealizareiconfiguraresoftwareihardwareauneireeledecalculatoare,de integrarea reelelor de calculatoare ntre ele, de tipurile de reele de calculatoare Structuri de date - este o disciplin strns legat de programarea calculatoarelor, ocupndu-se degsireaimbuntireamodalitilordereprezentareadatelorncalculator,nfunciede necesiti i de algoritmii ce le vor prelucra Baze de date - este o disciplin nrudit cu precedenta, ocupndu-se, ns, de coleciile de date mari, cu structuri asemntoare, ce pot fi stocate pe suporturi fizice externe, precum i de modul de interogare a unor baze de date pentru a realiza selecii Analiza, proiectarea i sinteza algoritmilor - dup cum spune i denumirea, aceast disciplin se ocup de modalitile, tehnicile i strategiile cele mai eficiente de rezolvare a problemelor, de stocare a datelor, de prelucrare a informaiilor n vederea obinerii altor informaii, precum i de transmitere eficient a lor pe ci electronice Programareacalculatoarelor-seocupdeimplementareaalgoritmilorproiectaipe calculatoarele electronice, astfel nct acetia s poat fi pui la lucru, deci este arta i tiina de a crea programe de calculator Limbaje de programare - un algoritm proiectat va fi implementat sub forma unui program, iar programulestescrisntr-unanumitlimbajdeprogramare,adicoconveniedesimbolurii cuvinte,precumiregulidembinareaacestora,mpreuncunelesurilelorcepotfi recunoscute de calculator; disciplina se ocup i de evoluia i studiul limbajelor de programare, pentru a determina cel mai potrivit limbaj de programare utilizabil ntr-o anumit situaie Limbajeformaleiconstruciacompilatoarelor-odisciplincarestudiaz(suboform algebric)modalitileprincareunprogramscrisntr-unlimbajdeprogramarepoatefi recunoscutcafiindcorectdectreunautomatsauogramaticdedescrierealimbajuluide programare respectiv; de asemenea, disciplina se ocup i cu construirea compilatoarelor, adic a acelor translatoare ntre limbajul de programare i limbajul procesorului (cod main) 11Ingineriasoftware-esteundomeniustrnslegatdeprogramareacalculatoarelor,dedata aceasta la un nivel mai ridicat, al proiectrii programelor complexe Graficcomputaional-seocupdetehniciledereprezentaregraficpecalculatora curbelor,suprafeelor,corpurilor,demodalitiledeascundereasuprafeelornevizibile, domeniu strns legat de geometrie Inteligen artificial - se ocup cu rezolvarea unor probleme pentru care se folosesc algoritmi specifici; domeniul dorete s simuleze pe calculator unele componente ale inteligenei umane, cumarfirecunoatereatextelorscrise,avorbirii,deducia,gsirearspunsurilorcreative, capacitatea de a nva din experien i capacitatea de a trage concluzii pe baza unor informaii incomplete. Cercetereoperaional-seocup,ngeneral,derezolvareaunorproblemededeciziei conducere ce apar n economie Analiz numeric - este un domeniu de grani ntre informatic i matematic, ocupndu-se de rezolvareapecalenumericaunorproblemedeanalizmatematic(derivabile,integrale, interpolri, rezolvarea de ecuaii, calcule cu matrice i determinani) Teoriagrafurilor-esteundomeniudegranintreinformaticimatematic,careseocup derezolvareaproblemelorlegatedegrafuri,cuaplicabilitatendiferitedomeniialetiineii tehnicii (management, proiectare n construcii etc.). ObiectuldestudiualdisciplineiProgramareacalculatoarelorelectronicevafi,aadar reprezentatdeartaitiinacreriideprograme,pebazaunoralgoritmi,scrisentr-unlimbajde programare.Deaceea,acestcursvatrecenrevist,maintictevamodalitiesenialede reprezentare a datelor, apoi vom vorbi despre algoritmi i proprietile lor.Cursul va continua cu prezentarea principalelor stiluri (paradigme) de programare folosite n prezent,pecarelevomprezentantr-osuccesiunegradat,pnvomajungelaprogramarea vizual.Concepteleprogramriivizualeioscurtintroducerepracticndomeniuvaconstitui parteaadouaacursului,cesevancheiacuuncapitolreferitorlaproiectarea,realizareai ntreinerea produselor softare i o recapitulare pentru examen. 12 CapitolulCapitolul 2. Date 2.1. Constante i variabile. Expresii nprimulcapitolamprecizatcesuntdatele,iarnacestcapitolnevomocupade reprezentarea lor intern, adic n memoria calculatorului i pe suporturi externe, fizice, n fiierele de pe discuri. Dateleaparncadrulunorprogramescrisentr-unlimbajdeprogramaresaualtul, reprezentateprinnitecuvintedeidentificare,numiteidentificatori.nmaitoatelimbajelede programare, un identificator este un ir de litere sau cifre, eventual i alte simboluri (cum ar fi "_"), ce ncepe cu o liter. ncadrulprogramului,datelepotfideclaratecafiindconstantesauvariabile.Oconstant esteodatacreivaloarenusepoatemodificapeparcursulexecuieiprogramului,decirmne constant.Ovariabilesteodatacreivaloaresepoatemodificapeparcursulexecuiei programului, deci ea poate varia, dar acest lucru nu este obligatoriu. Astfel, se poate declara o dat cafiindvariabilncadrulunuiprogram,apoieasprimeascoanumitvaloare,iaraceast valoare s rmn asociat respectivei variabile pn la terminarea programului.Evident, atunci cnd se va declara o dat constant, se va preciza i valoarea ei, iar cnd se va declara o dat variabil, se subnelege c ulterior, pentru a putea fi folosit, aceast variabil va primioanumitvaloare.Majoritatealimbajelordeprogramareasigneazovaloareiniial variabilelor,odatcudeclararealor.Astfel,iruriledecaracteresuntiniializatelairulvid,iar numerele sunt considerate cu valoarea zero. Firete,attconstantelectivariabileleauoanumitstructur,maisimplsaumai complicat, i o anumit natur, dat de mulimea valorilor posibile pentru o dat. Cu ele se pot face anumite operaii, n funcie de natura i structura lor. Astfel, vom spune c o dat are un anumit tip.Prin tip de date vom nelege o mulime de valori, mpreun cu operaiile ce se pot executa cuele.Fiecreivariabile,ladeclarare,isevaasociaunanumittip.Tipuluneiconstantepoatefi determinat implicit din valoarea constantei, sau poate fi precizat explicit ca n cazul variabilelor. Astfel,dacconstantaKarevaloareanumeric7,putemtrageconcluziaceaestedetip ntreg, sau de tip real, nu i logic sau ir de caractere. Totui, exist i limbaje n care se fac anumite convenii,depildcoricenumrdiferitdezeroesteconsideratcafiindcuvaloareadeadevr adevrat, iar numrul zero are valoarea de adevr fals. Unelelimbajedeprogramarepermitdeclarareaunorvariabilefraseprecizatipullor, considerndu-seastfelcaavndunanumittipgeneral.Astfel,atuncicndvafifolosit,variabila respectiv va fi considerat ca avnd cel mai adecvat tip cu putin, n situaia concret respectiv. De pild, dac este declarat o variabil X, iar la un moment dat i se atribuie valoarea 3,. atunci ea Xdelta 3x-3*delta 13poateficonsideratcaavnduntipnumeric.Daculterior,variabilaXvaprimivaloarea"abc", adic un ir de caractere, se poate considera c X este de tip ir de caractere. Pebazaconstantelorivariabilelorseformeazexpresii.Bineneles,nformarea expresiilor se vor folosi acei operatori, precum i acele funcii, permise de tipurile valorilor asupra crora se opereaz. Expresiile mici pot conduce la elaborarea de expresii mai mari, din ce n ce mai complexe. Pentru a nelege cum stau lucrurile, vom considera limbajul Visual Basic, iar exemplele ce vor urma vor fi date n acest limbaj. S considerm urmtoarele declaraii de variabile: Dim X As Integer, Y As Integer, S As String Dim V Astfel,XiYsuntvariabilentregi(cuvalorinmulimeanumerelorntregi),Seste variabil de tip ir de caractere (cuprinse ntre ghilimele), iar V este o variabil a crui tip nu a fost precizat.VisualBasicpuneastfelladispoziietipuldedateVariant,carereunete,subuncadru general, toate celelalte tipuri de date. Urmtoarele expresii sunt corecte din punct de vedere sintactic, n limbajul Visual Basic: 2, X, X+5, X+Y, X+4*Sqr(Y), S, V, V+3, V+X, S+S, X+Len(S), Left(S,2)+Right(S,3) X, Y, V i S pot primi valori n dou feluri: prin atribuire direct sau prin citire (de la tastatur sau dintr-un fiier). Atribuirea se face cu instruciunea de atribuire, care are forma: Variabil = Expresie sau Let Variabil = Expresie Citirea valorilor se poate face folosind o operaie de citire, ca de pild: Input Variabil Sconsidermurmtoareleoperaiiprincareseatribuievalorivariabilelordeclarate anterior: Y = 16 S = "abcd" Y = 7 Input V X = Y + Len(S) + 1 IniialluiYiseatribuievaloarea16,darapoielprimetevaloarea7,renunndu-sela16. Dac de la tastatur se va da valoarea 8 lui V, atunci V va fi considerat ca fiind de tip ntreg.X va luavaloarea12,adicsuma7+4+1,4fiindlungimeairuluidecaractereS("abcd").ncadrul secvenei anterioare apar 4 constante i anume: numrul 16, irul "abcd", numerele 7 i 1. Urmtoarele expresii nu sunt corecte din punct de vedere sintactic, deci, de fapt, ele nu sunt expresii: X +, X****, X Y, S + 14Exist i cazuri speciale, cum ar fi X + S sau S + V. Unele limbaje de programare consider asemenea entiti ca fiind incorecte, pe cnd altele le consider expresii perfect corecte. De pild, n primulcaz,Xconsideratcafiindnumr,iarScafiindirdecaractere,rezultatulaceleiadunri poate fi considerat fie concatenarea dintre X convertit la ir de caractere i S, fie ca numrul obinut dinadunarealuiXcuirulS,convertitlanumr.ngeneral,sealegenfunciedetipulcese dorete a-l avea expresia. De pild, dac X are valoarea 5, S are valoarea "123", atunci printr-o atribuire de genul S = X + S vom putea nelege c S va primi valoarea "5123" (adic "5" concatenat cu "123"), iar printr-o atribuire de genul X = X + S, vom considera c X primete valoarea 128 (adic suma 5 + 123). Majoritatea limbajelor de programare definesc expresiile dup un sistem de reguli sintactice, care, n general sunt urmtoarele: 1. orice constant este expresie; 2. orice variabil este expresie; 3.dacEesteexpresie,atuncii(E),-E,+E,F(E)suntexpresii,undeFestenumeleuneifuncii aplicabile expresiei E; 4. dac E1 i E2 sunt expresii, atunci i E1+E2, E1-E2, E1*E2, E1/E2 sunt expresii. Acum, pe baza regulilor de mai sus putem construi expresii foarte complexe, pornind de la constante i variabile. Astfel, s considerm entitatea (3+A)*(5/(-B+C)) i s verificm dac ea este expresie sau nu. S presupunem c A, B i C sunt variabile numerice ntregi. Cum 3 este constant, conform regulii 1, ea este i expresie. A, fiind variabil este, conform regulii 2 expresie. Acum, conform regulii 4, 3+A este expresie, iar (3+A) este tot expresie, conform regulii3.Dupsimbolulnmulirii(reprezentatadeseaprin*),avem:5esteexpresie,fiind constant, B, C, apoi -B i -B+C sunt expresii. n fine, conform regulii 3, (-B+C) este tot expresie, apoii(5/(-B+C))esteexpresie,nconformitatecuregula4,i,totdupaceastregul,i (3+A)*(5/(-B+C)) este expresie. 2.2. Tipuri de date simple Spuneamcfiecareconstant,variabilsauexpresieareunanumittipdedate. Tipuluneidatedetermincomportamentulacesteia,pentrucellimiteazsauextinde moduldeoperareasuprasa.ngeneral,seacceptcdatelepotficonsideratecafiind simple,primare,adicavndostructuratomic,indivizibil,saustructurate,construite pe baza altor date, cu ajutorul unor constructori speciali.n general, sunt acceptate ca fiind atomice sau simple, urmtoarele tipuri de date: mulimea numerelor ntregi i operaiile cu numere ntregi, care dau rezultat ntreg; mulimea numerelor reale mpreun cu operaiile ce se pot executa cu ele; mulimea caracterelor reprezentabile n calculator i operaiilecuele;mulimeavalorilordeadevr,adevratifals,ceconstituietipullogicdedate. Personal,consideritipulirdecaracterecafiinduntipsimplu,datoritfaptuluicestefoarte necesarnelaborareaunoralgoritmisimpli,debaz,ipentrucasupraluisepoateacionacu operaiidirecte,ntlniteilacelelaltetipuridedate.Totui,tipulirdecaractereesteuntip structurar. Tipurilededatepoartielenume,decisuntdenumiteprinidentificatori.Deobicei,tipul ntreg se numete Integer, dar pot exista mai multe tipuri ntregi, n funcie de necesiti particulare. Astfel, n Visual Basic, Integer reprezint numerele ntregi din intervalul -32768 .. 32767, iar Byte reprezint numerele ntregi ntre 0 i 255. De asemenea, Long este tot un tip ntreg, cu valori ntre 15-2147483648i2147483647.nfunciedemrimeanumerelordereprezentat,ovaloarentreag poatefistocat folosind 1, 2 sau 4 octei. Astfel, de pild, o dat de tip Byte se memoreaz pe un octet, una de tip Integer pe doi octei, iar una de tip Long pe 4. n mod similar, Single stocheaz valori reale pe 4 octei, iar Double valori reale pe 8 octei. uuuuuu PentruiruridecaracteresevafolositipulString,iarcaractereleindividualesunt consideratecafiindiruridecaracteredelungime1.nPascal,depild,existnstipuldedate Char pentru reprezentarea caracterelor.Boolean este tipul de date logic, cuprinznd valorile constante True i False. n Visual Basic existitipulgeneralVariant,desprecareammaivorbit,precumialtetipurispeciale,cumarfi Decimal, Currency sau Date. ngeneral,cudatelenumericepotfirealizateoperaiilespecificenumerelor,cumarfi adunarea, scderea, nmulirea (reprezentat de *), mprirea (reprezentat de \ la numere ntregi, n Visual Basic, de pild, sau / la numere reale). Exist i unele funcii matematice cum ar fi funciile trigonometrice(Sin,Cos,Tan,Atan),funcialogaritmzecimal(Log),funciaradical(Sqr)sau funcia modul (Abs).Cudateledetiplogic(Boolean)serealizeazoperaiispecifice,cumarficonjuncia,disjuncia (inclusiv i exclusiv), negaia, a cror tabele sunt prezentate mai jos (A = adevrat, F = fals): and (i) - conjuncia logic A and A = A A and F = F and A = F and F = F or (sau) - disjuncia logic inclusiv F or F = F A or F = F or A = A or A = A xor (sau exclusiv) - disjuncia logic exclusiv A and F = F and A = A A and A = F and F = F not (non, nu) - negaia logic not A = F not F = A nVisualBasic,cudateledetipBooleansepotrealizaioperaiiledeimplicaieiechivalen logic, prin operatorii Imp, respectiv Eqv. Conversiile de la un tip la altul se pot realiza fie explicit, folosind funcii speciale, fie implicit, dup caz.Astfel,nVisualBasic,dacX,ZsuntdetipInteger,iarYestedetipByte,dacscriem Z=X+Y, atunci automat Y este convertit la tipul Integer, nainte ca s se realizeze adunarea. Conversii mai importante se fac n cazuri ca acestea: Dim X as Integer Dim Y as Double X = Y sau Dim X as Integer Dim S as String 16S = X sau X = S nprimulcaz,evidentcXvaprimiparteantreagaluiY,iarncelelaltedoucazuri,fieXse convertete la ir, fie se preia din S numrul. Totui,putemfolosiifunciileIntpentruaextrageparteantreagdintr-unnumrreal,respectiv Str pentru a converti un numr la un ir i Val pentru a obine un numr dintr-un ir. Cudateledeoricaretipdedatesepotrealizacomparaii.Astfel,deobiceisefolosescnotaiile urmtoare: pentru mai mic i mai mare; = pentru mai mic sau egal, respectiv mai mare sau egal; sau != pentru diferit = sau == pentru egal 2.3. Tipuri de date structurate Pebazadatelorsimplesepotconstruidatestructurate.Depild,putemsne imaginmsituaiancaredorimsstocmlistanumelorinotelorcandidailorla concursul de admitere n facultate. O modalitatea foarte ineficient este de a pstra cte o variabil pentru numele fiecrei persoane i cte o variabil pentru nota obinut de fiecare persoan.Darnuvomtictepersoanevomavea,deaceeaestepracticimposibilsprocedm astfel. Mult mai bine este s folosim un tip de date care s ne permit declararea a dou variabile, szicemNumeiNota,carespstrezeceledouliste.Acesttipdedatesenumetetabloui permitegrupareadedatedeacelaitipsubunsingurnume.Componentelevorputeafireferite printr-unnumrdeordin,numitindice.Pentrucaoperareasfieeficient,vatrebuicanota persoanei cu indicele i din tabloul de nume s fie pe poziia i n tabloul de note. Mult mai natural ar fi s avem un singur tablou, n loc de dou. Astfel, n loc de a pstra un tabloupentrunumelepersoaneloriunulpentrunotelelor,maibineamaveaunsingurtabloude persoane.Astfel,artrebuicafiecarecomponentatablouluimaresconinunarticol,cares grupeze la un loc att numele, ct i nota unei persoane. n acest sens ne vine n sprijin tocmai tipul de date nregistrare (sau articol) ce poate ncapsula sub un singur nume date de tipuri diferite. Cu toate c un tablou de articole poate stoca eficient i natural datele despre candidaii la un concursdeadmitere,aceastanuestentotdeaunasoluiaceamaibun.Dateledintr-untablouse stocheaznmemoriainternacalculatoruluii,cutoatecpotfiaccesaterapididirect,elenu suntpstreazdelaorulareaprogramuluilaaltasaucndcalculatorulesteoprit.Iatimotivul pentru care ar fi necesar ca datele s fie pstrate pe un suport fizic extern, sub forma unui fiier pe disc. Un alt motiv pentru care trebuie utilizat fiierul n locul tabloului este c un fiier poate avea dimensiuni mult mai mari dect un tablou. Structurilededatecomplexesecreeaz pe baza celor simple sau complexe create anterior, aplicnd nite constructori speciali. n Visual Basic, un tip nregistrare se definete astfel: Type NumeDeTip cmp1 As Tip1 cmp2 As Tip2 ....................... End Type 17Pot exista n cadrul definiiei unui tip de date nregistrare i cmpuri de tip tablou.Exemplu: Type Candidat nume As String nota As Single End Type n continuare, putem declara o variabil de tip Candidat prin Dim C as Candidat Pentru a face referirea la un anumit cmp se folosete notaia cu punct, sau operatorul punct, astfel: NumeDeVariabilnregistrare.NumeDeCmp: C.nume este numele candidatului C, iar C.nota estenotaaceluiaicandidat.NusepoatecitiansamblulCnntregime,prinInputC,cidoarpe componente, prin Input C.nume i Input C.nota. Nuexistodefiniiespecialpentruuntiptablou,darfaptulcXesteovariabildetip tablou se poate scrie astfel: Dim X(n) as Tip Astfel, X s-a declarat ca fiind o variabil de tip tablou, cu n componente, numerotate de la 0 lan-1.FiecarecomponentestedetipulTip.Dacsedoretecanumerotareassefacdelao anumit valoare v1 la o alt valoare v2 se va scrie: Dim X(v1 To v2) as Tip Exemplu: Astfel, de pild, Dim X(1 to 10) as Integer declar un tablou cu 10 numere ntregi.Referireaelementelorunuitablousefacecuajutoruloperatorului()(laaltelimbajese folosescparantezeleptrate[]nlocdecelerotunde).Astfel,X(1)esteprimacomponenta tabloului X, iar X(10) este ultima. Exemplu: S considerm urmtoarea declaraie: Dim Cand(1 To 500) as Candidat Astfel, am declarat 500 de candidai, iar Cand(i).nume este numele candidatului al i-lea, pe cnd Cand(i).nota este nota acestuia. Pnacumamvorbitdespretablouriunidimensionale,numiteivectori.Existnsi posibilitateadeadeclaratablouribidimensionale(numitematrice)sauchiarcumaimulte dimensiuni.Astfel, declaraia: Dim A (1 To 10, 1 To 15) defineteomatricecunumeleA,cu10liniii15coloane.Elementuldelaintersecialinieiicu coloana j se va referi prin A(i,j). 18 De ce AND si nu OR? Tipul Boolean. Operatorii logici. Legile lui De Morgan. Logica matematica Adevarat sau fals. A treia varianta nu exista! In urma cu multi, multi ani, oamenii si-au pus problema "sa se joace cu adevarul", adica sa faca rationamente, pornind de la propozitii simple. Aristotel a inventat logica ce-i poarta numele, iar mai apoi Boole, un matematician englez, a formalizat lucrurile obtinand ceea ce ne intereseaza pe noi in programare si anume logica booleana. In aceasta logica avem de a face cu doua valori de adevar: fals si adevarat. A treia varianta nu exista.La un monent dat, ceva (o afirmatie, o propozitie) poate fi fie adevarat, fie fals, dar niciodata amandoua. Unii spun despre o anumita afirmatie ca este "in general adevarata". In programare, in logica booleana, asa ceva nu exista. O expresie booleana nu poate fi in general adevarata. Cand spui "in general adevarat" inseamna, de fapt, fals. Pentru ca ce nu este "intotdeauna" adevarat este fals. De exemplu, afirmatia (propozitia) logica "programatorii sunt buni la matematica" nu poate fi in general adevarata, atata timp cat o privim din punct de vedere logic, boolean. Daca nu exista nici un programator care sa nu fie bun la matematica, atunci propozitia noastra este adevarata. Daca insa exista cel putin un programator care sa nu fir bun la matematica, propozita noastra este falsa. Cum este propozitia noastra, din punct de vedere logic? Falsa, pentru ca am cunoscut eu un programator care nu se pricepea deloc la matematica! Din punctul de vedere al vietii cotidiene, dar nu din punct de vedere logic, despre afirmatia "programatorii sunt buni la matematica" se poate spune ca este in general adevarata. Sa luam acum un exemplu mai din programare. Acolo operam cu variabile, constante si expresii. Constantele nu-si modifica valorile, deci vor avea una (si numai una) din cele doua valori, care, in multe limbaje de programare sunt notate cu True si respectiv False. In alte limbaje de programare (de exemplu in C si C++), in loc de False se foloseste 0 (zero), iar orice alt numar in afara de 0 corespunde valorii True. Sa consideram doua variabile X si Y. Sa zicem ca X are valoarea 3, iar Y are valoarea 5. Afirmatia "X este mai mic decat Y" (notata X=A and X=A) or not (XX(i+1) atunci ordonat = Fals; interschimb pe X(i) cu X(i-1) pn cnd ordonat=Adevrat Observaicdescriereaalgoritmuluinpseudocodfolosetetreistructuridecontrol asemntoarecelorprezentatedeja,darauanumitediferenefadeele.Astfeldestructuride control, numite auxiliare, au fost introduse tocmai pentru a uura scrierea algoritmilor, dar ele pot fi substituite de celelalte. 33Prima dintre ele este decizia cu ramur vid, adic: dac condiie atunci instruciune adic nu mai exist ramura cu altfel n acest caz, dac este adevrat condiia, atunci se execut instruciunea, iar dac este fals condiia,nusemaiexecutnimic.Aiobservat,probabil,cs-afolositaceaststructurn algoritmul de sortare prezentat mai sus. Exist i o form special de decizie, numit decizia multipl: n caz c e este e1: instruciune1; e2: instruciune2; .......................... Astfel,seevalueazexpresiae,iardacvaloareaeiesteidenticcuvaloareauneiadintre expresiile e1, e2 .a.m.d., atunci se execut instruciunea corespunztoare. Algoritmuldesortaredescrismainaintefolosetedoustructurispeciale:structura repetitiv condiionat posterior: repet instruciune1; instruciune2; ..................... pn cnd condiie Aceasta nseamn c se execut n mod repetat secvena de instruciuni specificat, pn la ndeplinireacondiieidelafinal.Spredeosebiredestructurarepetitivcondiionatanterior,aici secvenadeinstruciuniseexecutcelpuinodat.ncazulluicttimp...execut...,dacdela bunnceputnuerandeplinitcondiia,atunciinstruciuneasauinstruciuniledinciclunuse execut. Astfel, structura repet poate fi scris, pe baza structurilor de baz astfel: instruciune1; instruciune2; .................... ct timp not condiie execut instruciune1; instruciune2; .................... Attn cazulrepetiieicondiionat anterior, cti n cea condiionat posterior, prezentate mainainte,numrulde paiaiciclului nu poate fi calculat aprioric. Asemenea structuri repetitive se mai numesc i cu numr necunoscut de pai.Structuraspecialpentruesteostructurrepetitivcunumrcunoscutdepai.Astfel, numrul de pai ai ciclului poate fi calculat aprioric pe baza celor trei expresii ce compun structura: pentru v de la e1 la e2 [cu pasul e3] execut instruciune Structura pentru poate fi considerat fie condiionat anterior, fie condiionat posterior, iar acestlucrudepindedeimplementarealimbajuluincarestructuraseregsetesubformaunei instruciuni. n general, ea este o structur condiionat anterior, iar semnificaia ei este: 34Dac e3 lipsete, atunci se consider e3=1.Dac (e3 > 0 i e1>e2) sau (e3 '); WriteLn(x[1]); if ReadKey=#27 then Halt end; function PotContinua: Boolean; var pc: Boolean; begin pc:=True; { nodul curent (x[k]) trebuie sa fieun nod vecin cu anteriorul } if Vecin[x[k],x[k-1]]=0 then pc:=False else begin { ultimul nod trebuie sa fie vecin cu primul } if k=n then if Vecin[x[n],x[1]]=0 thenpc:=False elsepc:=True; if pc then { trebuie sa nu mai fi trecut prin acest nod } begin for i:=1 to k-1 do if x[i]=x[k] then pc:=False end end; PotContinua:=pc end; begin Write('Dati nr. de orase: '); ReadLn(n); for i:=1 to n-1 do for j:=i+1 to n do begin Write('Este drum de la orasul ',i, ' la orasul ',j,' ? [da=1] '); ReadLn(Vecin[i,j]); Vecin[j,i]:=Vecin[i,j] end; 89 for i:=1 to n do Vecin[i,i]:=0; WriteLn; k:=2; x[1]:=1; {se considera nodul 1 fixat = 1} while k>1 do begin cont:= false; while (x[k]0. S se determine toate irurile de n paranteze care se nchid corect. De exemplu, pentru n=6 avem: ((())), ()()(), (()()), ()(()), (())(). Rezumat 1. Una dintre cele mai cunoscute tehnici generale de elaborare a algoritmilor este metoda Back-tracking. Ea ncearc s elimine generarea tuturor posibilitilor, pentru a ajunge la rezultat. 2. Metoda Back-tracking se poate aplica acelor probleme pentru care soluia se poate reprezenta sub forma unui vector x ale crui elemente iau valori din nite mulimi finite (de exemplu {1,2,...mk}) i care ndeplinesc anumite condiii interne. 3. n metoda Back-tracking, elementele vectorului iau valori pe rnd, atribuirea unei valori pentru o component x[k] fcndu-se abia dup ce s-au atribuit valori pentru toate componentele anterioare ei (x[1], ..., x[k-1]), iar ntre aceste valori nu exist incompatibiliti. Adic se respect nite condiii de continuare. 4. Nerespectarea condiiilor de continuare implic automat nerespectarea condiiilor interne, deoarece orice valori am luat pentru x[k+1], ..., x[n] (n este numrul de elemente al vectorului), condiiile interne nu vor fi respectate. 5. Dac spaiul valorilor pentru x[k] se epuizeaz, atunci se revine la componenta k-1, pentru care se va ncerca alt valoare .a.m.d.. 6. Metoda Back-tracking genereaz mai multe soluii. 7. Probleme clasice care pot fi soluionate prin aceast metod sunt: problema damelor, generarea produsului cartezian, generarea combinrilor, problema discret a rucsacului. 91 Capitolul 7. Recursivitate n atenia profesorului Pe parcursul acestui capitol se vor urmri: a) formarea la studeni a deprinderilor de a utiliza funciile recursive; b) formarea la studeni a deprinderilor de a identifica situaiile n care varianta recursiv este preferabil celei nerecursive sau invers; c) deprinderea studenilor cu utilizarea variabilelor locale n cadrul subprogramelor recursive; d) deprinderea studenilor cu identificarea problemelelor care pot fi rezolvate utiliznd recursivitatea indirect. 7.1. Prezentare general

7.1.1. Mecanismul recursivitii S considerm c vrem s calculm factorialul unui numr ntreg dat n. O modalitate (numit repetitiv sau iterativ) este de a scrie o secven de forma:fact:=1; for i:=1 to n do fact:=fact*i O alt modalitate este de a ne folosi de urmtoarea proprietate a factorialului: 0!=1, iar n!=n*(n-1)! Astfel, pentru a calcula factorialul unui numr ntreg n am putea scrie o funcie de genul: function fact(n: LongInt): LongInt; begin if n=0 then fact:=1 elsefact:=n*fact(n-1) end; Se observ c n cadrul desrierii funciei fact avem un apel al chiar acestei funcii, pentru parametrul efectiv (actual) n-1. Este vorba despre o autoapelare a funciei fact, ceea ce nseamn c funcia fact este recursiv. Astfel, autoapelul funciei fact genereaz o nou activare a acestei funcii, care presupune o eventual autoapelare .a.m.d.. Spunem eventual, deoarece la un moment dat, autoapelarea se va face cu parametrul efectiv 0, ceea ce nseamn c ultimul apel va returna valoarea 1. Aceast valoare se va trimite funciei care a apelat fact pentru n=0, adic tot lui fact, napoi, care va nmuli pe 0!=1 cu 1. Apoi rezultatul (1) va fi trimis napoi funciei care a apelat fact(1), adic tot lui fact, care va obine 1!2=2! .a.m.d. pn la primul apel al lui fact. Putem reprezenta schematic autoapelurile succesive ale funciei fact astfel: apeluri succesive:fact(n)fact(n-1)...fact(2)fact(1)fact(0)=1 (oprire) rentoarceri succesive: fact(1)=1fact(0)=11fact(2)=2fact(1)=21fact(3)=3fact(2)=321...fact(n)=nfact(n-1)=n(n-1)(n-2)...321 Are loc, dup cum se vede un calcul al aceluai produs, dar n ordine invers. Acest caz, cnd un subprogram se autoapeleaz, se numete recursivitate direct. 92Exist i posibilitatea unei recursiviti indirecte sau ncruciate, despre care vom vorbi mai trziu. Deocamdat precizm c aceasta are loc ntre dou sau mai multe subprograme diferite, care se apeleaz reciproc. ? ntrebri i exerciii1 Ce credei c se ntmpl dac ar lipsi condiia i instruciunea pentru n=0 din definiia funciei recursive de calculat factorialul? 2 Descriei schematic apelurile recursive pentru n=3, ale funciei fact. 3 Scriei o funcie recursiv pentru a calcula suma 1+2+...+n, pentru un n dat de la tastatur. 7.1.2. Condiia de consisten a unei definiii recursive S considerm definiia recursiv de mai jos (funcia lui Ackermann): A m nn daca mA m daca nA m A m n altfel( , ), ,( , ), ,( , ( , )), .=+ = = 1 011 01 1 n limbajul Pascal, aceast funcie se va scrie: function A(m,n: Integer); begin if m=0 then A:=n+1 elseif n=0 then A:=A(m-1,1) else A:=A(m-1,A(m,n-1)) end; S determinm A(2,2). Vom aplica succesiv definiia pn la identificarea unor argumente pentru care valoarea funciei A se poate calcula. Apoi vom substitui valoarea calculat n locul celui mai interior argument de pe poziia a doua, dup care vom relua aplicarea definiiei, dac numele funciei nu mai apare. Avem succesiv:A(2,2)=A(1,A(2,1))=A(1,A(1,A(2,0)))=A(1,A(1,A(1,1)))=A(1,A(1,A(0,A(1,0))))=A(1,A(1,A(0,A(0,1))))=A(1,A(1,A(0,2)))=A(1,A(1,3))=A(1,A(0,A(1,2)))=A(1,A(0,A(0,A(1,1))))=A(1,A(0,A(0,A(0,A(1,0)))))=A(1,A(0,A(0,A(0,A(0,1)))))=A(1,A(0,A(0,A(0,2))))=A(1,A(0,A(0,3)))=A(1,A(0,4))=A(1,5)=A(0,A(1,4))=A(0,A(0,A(1,3)))=A(0,A(0,A(0,A(1,2))))=A(0,A(0,A(0,A(0,A(1,1)))))=A(0,A(0,A(0,A(0,A(0,A(1,0))))))=A(0,A(0,A(0,A(0,A(0,A(0,1))))))=A(0,A(0,A(0,A(0,A(0,2)))))=A(0,A(0,A(0,A(0,3))))=A(0,A(0,A(0,4)))=A(0,A(0,5))=A(0,6)=7. Observm tendina de identificare a unor valori direct calculabile, urmat de utilizarea lor n vederea obinerii valorilor cutate. Astfel, o definiie recursiv trebuie s satisfac urmtoarea condiie: valoarea funciei trebuie s fie ori direct calculabil, ori calculabil cu ajutorul unei valori direct calculabile. Aceast condiie se numete condiia de consisten, iar ea este verificat att de funcia lui Ackermann, ct i de funcia recursiv cu ajutorul creia calculasem factorialul unui numr. Un exemplu de funcie inconsistent este urmtoarea: function Inconsistent(n: Integer); begin if n=0 then Inconsistent:=1 elseInconsistent:=n*Inconsistent(n+1) end; 93 ? ntrebri i exerciii1 Care este rolul condiiei de consisten ntr-o definiie recursiv. 2 Ce se nelege prin condiie de consisten? 3 Dai un exemplu de definiie recursiv inconsistent. 4 Este urmtoarea definiie consistent sau nu? function F(n: Integer); begin if n=0 then F:=0 else F:=n+F(n+1) end; 7.1.3. Utilizarea stivelor n recursivitate Mai nti trebuie s precizm c, n informatic, prin stiv se nelege ceea ce se nelege i n viaa de zi cu zi. Deocamdat vom considera o stiv (alocat static) ca fiind un vector asupra cruia se pot face operaiile: adugarea unui element, dup ultimul element (indicat de un numr n), i eliminarea ultimului element (al n-lea) din vector. Vectorul ar putea fi asemuit unei stive de cri: putem pune o carte nou doar peste ultima din celelalte deja existente i putem s lum doar cartea de deasupra. Atunci cnd, de exemplu, se dorete calcularea valoarii 3!, se memoreaz ntr-o stiv, iniial vid, acest numr 3, necesar pentru a fi nmulit cu 2!. Procesul continu pn la 0!, cnd are loc eliminarea, pe rnd, a elementelor din stiv, simultan cu cte o nmulire. function Fact(n: LongInt): LongInt; begin if n=0 then Fact:=1 else Fact:=Fact(n-1)*n end; Mediul Turbo-Pascal dispune de o stiv proprie, cu o anumit dimensiune. Depirea acesteia se face cu opiunea de compilare {$S+}. Opiunea aceasta este implicit. Cnd lucrm cu apeluri recursive ce ncarc foarte mult stiva, dar avem condiia de consisten a recursiei ndeplinit, este bine s folosim opiunea de compilare {$S-}, altfel se poate folosi opiunea{$S+}, care controleaz dimensiunea stivei i nu ne las s o suprancrcm. Noi nine putem simula recursivitatea, implementnd o structur proprie de stiv. Urmtorul program calculeaz factorialului unui numr, folosind o iteraie asupra unei stive, iteraie ce simuleaz recursivitatea. program SimulareRecursivitate; const max=20; type stiva=recordx: array[1..max] of Integer; n: Integer end; procedure InitStiva(var S: stiva); begin S.n:=0 end; function EsteGoalaStiva(var S: stiva): Boolean; { folosim "var" pentru economie } begin EsteGoalaStiva:=S.n=0 end; procedure PuneInStiva(var S: stiva; elem: Integer); begin 94 with S do if n=max then WriteLn('Stiva plina !') else begin Inc(n); x[n]:=elem end end; procedure ScoateDinStiva(var S: stiva; var elem: Integer); begin with S do if n=0 then WriteLn('Stiva goala !')else begin elem:=x[n]; Dec(n) end end; function Factorial(n: Integer): Integer; var S: stiva; F: Integer; begin InitStiva(S); F:=1; repeat PuneInStiva(S,n); Dec(n) until n=0; F:=1; repeat ScoateDinStiva(S,n); F:=F*n until EsteGoalaStiva(S); Factorial:=F end; var n: Integer; begin WriteLn('Calcul factorial - simulare recursivitate'); Write('Dati n = '); ReadLn(n);WriteLn(n,'! = ',Factorial(n)); ReadLn end. Asupra stivelor vom reveni i n leciile urmtoare, odat cu reluarea tehnicii de programare Back-tracking n varianta sa recursiv, precum i atunci cnd vom discuta despre tehnica Divide-et-impera. 7.2. Funcii recursive

n continuare vom da unele exemple la recursivitatea direct prin comparare cu metoda iterativ. 7.2.1. Inversarea recursiv a unui cuvnt Dac dorim s inversm un cuvnt pe msura introducerii caracterelor sale, atunci vom scrie ceva de genul: program InversareRecursivaCuvant; uses Crt; function Invers: String; var c: Char; begin if EoLn then Invers:='' else 95 begin Read(c); Invers:=Invers+c end end; begin Write('Dati cuvantul: '); Write('Cuvantul inversat este: ', Invers); ReadKey end. Funcia Invers se termin cnd se tasteaz Enter. Dac, ns, dorim s scriem o funcie care s returneze inversul (reversul) unui ir dat s, vom proceda ca mai jos: program InverseazaSir; var s: String; function Revers(s: String): String; begin if s='' then Revers := '' else Revers := s[Length(s)] + Revers(Copy(s,1,Length(s)-1)) end; begin Write('Dati sirul de caractere: '); ReadLn(s); WriteLn('Inversul sau este: ',Revers(s)); ReadLn end. Astfel, inversul unui ir s dat este format din ultimul caracter al lui s, care se pune n faa inversului a ceea ce rmne din s dup eliminarea acestui ultim caracter. Firete, dac s este irul vid, atunci i inversul su va fi tot irul vid. Aceeai funcie, n varianta iterativ, s-ar scrie astfel: function Reverse(s: String): String; var t: String;i: Integer; begin t:=; for i:=Length(s) downto 1 do t:=t+s[i]; Reverse:=t end; 7.2.2. irul lui Fibonacci irul lui Fibonacci este un ir de numere celebru n matematic. El este definit astfel: primii doi termeni sunt 1 i 1, iar oricare alt termen se obine din nsumarea celor doi imediat dinaintea sa.Astfel, primii 10 termeni ai irului sunt: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. Urmtorul program conine o funcie F, care pentru argumentul ntreg n returneaz o valoare ce reprezint cel de al n-lea termen din irul lui Fibonacci. program SirulLuiFibonacci; var n: Integer; function F(n: LongInt): LongInt; begin if (n=1) or (n=2) then F:=1 else F := F(n-2) + F(n-1) end; begin Write('Dati n: '); ReadLn(n); WriteLn('Al ',n,'-lea termen ', 96'din sirul lui Fibonacci este: ',F(n)); ReadLn end. Observaie O variant repetitiv a determinrii termenilor irului lui Fibonacci a fost studiat n clasa a IX-a i o propunem ca exerciiu recapitulativ. 7.2.3. Cel mai mare divizor comun

Cel mai mare divizor comun al dou numere ntregi se bucur de urmtoarele proprieti: cmmdc(a,b)=cmmdc(b,a mod b), dac a0, respectiv b, dac a=0; cmmdc(a,b)=cmmdc(a div b, a mod b), dac a mod b 0, respectiv b, dac a mod b = 0; cmmdc(a,b)=cmmdc(a-b,b), dac ab, respectiv a, dac a=b. Pornind de la aceste lucruri se pot scrie funcii recursive. Mai jos sunt date dou funcii, pentru a doua i a treia relaie. program CelMaiMareDivizorComunEuclid; var a,b: Integer; function Cmmdc(a,b: Integer): Integer; begin if a mod b=0 then Cmmdc := b else Cmmdc := Cmmdc(a div b, a mod b) end; begin WriteLn('Alg. lui Euclid pentru c.m.m.d.c.'); WriteLn('*********************************'); Write('Dati a si b: '); ReadLn(a,b); WriteLn('C.m.m.d.c. este: ',Cmmdc(a,b)); ReadLn end. program CelMaiMareDivizorComunScaderi; var a,b: Integer; function Cmmdc(a,b: Integer): Integer; begin if a=0 then Cmmdc:=b else if a=b then Cmmdc := a else if a>b then Cmmdc := Cmmdc(a-b,b) else Cmmdc := Cmmdc(a,b-a) end; begin WriteLn('Alg. lui Euclid pentru c.m.m.d.c.'); WriteLn('*********************************'); Write('Dati a si b: '); ReadLn(a,b); WriteLn('C.m.m.d.c. este: ',Cmmdc(a,b)); ReadLn end. 97n continuare vom prezenta un exemplu ceva mai complex. Vom scrie o funcie pentru determinarea celui mai mare divizor comun al n numere ntregi. Funcia va fi recursiv, conform relaiei:CMMDC(x1,...,xn-1,xn) = CMMDC(CMMDC(x1,...,xn-1),xn). Astfel, vom scrie dou funcii. Prima (recursiv) va determina cel mai mare divizor comun al dou numere ntregi a i b, conform primei proprieti din cele trei prezentate. Cu cea de a doua (tot recursiv) se va determina cel mai mare divizor comun al n numere ntregi, astfel: se va determina d=cel mai mare divizor comun al primelor n-1 numere, apoi se va determina cel mai mare divizor comun al numerelor d i xn. Vom memora numerele ntr-un vector. program Calcul_CMMDC_n_numere; type vector = array[1..10] of Integer; var a: vector; x, n, i: Integer; function Cmmdc2(a,b: Integer): Integer; begin if a = 0 then Cmmdc2:=b else Cmmdc2:=Cmmdc2(b, a mod b) end; function CMMDC(x: vector; n: Integer): Integer; begin if n=2 then CMMDC:=CMMDC2(x[1],x[2]) else CMMDC:=CMMDC2(CMMDC(x,n-1),x[n]) end; begin Write(Dati numarul de elemente: ); ReadLn(n); for i:=1 to n do beginWrite( - dati numarul al ,i, -lea: ); ReadLn(a[i]) end; x:=CMMDC(a,n); WriteLn(Cel mai mare divizor comun este = ,x); ReadLn end. Observaie Deoarece funcia CMMDC apeleaz funcia CMMDC2, aceasta din urm a fost scris naintea primeia. n blocul principal, a este un vector, iar x un numr ntreg. n cadrul funciei CMMDC2, a este un numr ntreg, iar n cadrul funciei CMMDC x este un vector. Pentru datele de intrare n=3, a=(10,14,6) se va afia 2. ? ntrebri i exerciii1 Putei scrie o funcie recursiv pentru a determina cel mai mic multiplu comun al dou numere? 2 Dar pentru a determina cel mai mic multiplu comun al n numere dintr-un vector? 3 e Scriei o variant de funcie recursiv pentru a determina cel mai mare divizor comun al n numere, pe msura citirii lor de la tastatur. Ce avantaje i ce dezavantaje apar n acest nou program? 7.2.4. Funcia lui Ackermann Funcia lui Ackerman a fost prezentat o dat cu definirea condiiei de consisten a unui subprogram recursiv. Ea este dat prin relaiile: 98A m nn daca mA m daca nA m A m n altfel( , ), ,( , ), ,( , ( , )), .=+ = = 1 011 01 1 Urmtorul program conine o funcie Ack pentru calculul ei. program FunctiaLuiAckermann; var m,n: LongInt; function Ack(m,n: LongInt): LongInt; begin if m=0 then Ack:=n+1 else if n=0 then Ack:=Ack(m-1,1) else Ack:=Ack(m-1,Ack(m,n-1)) end; begin WriteLn('Functia lui Ackermann. Dati m si n: '); ReadLn(m,n); WriteLn('Ack(',m,',',n,') = ',Ack(m,n)); ReadLn end. Aceast funcie este, prin definiie, recursiv. Exprimarea repetitiv a unei funcii presupune derecursivarea sa n prealabil. 7.2.5. Suma cifrelor unui numr ntreg Problema determinrii sumei cifrelor unui numr ntreg s-a prezentat la disciplina Algoritmi i limbaje de programare din clasa a IX-a, o dat cu prezentarea instruciunii while. Ideea este de a lua ultima cifr a numrului, de a o aduga sumei (iniial vide), apoi de a proceda la fel cu restul cifrelor. Pentru aceasta, va trebui ca, dup fiecare pas, s se elimine din numr cifra din coad. Aceast ultim cifr a unui numr ntreg n este n mod 10, iar eliminarea sa se face prin n:=n div 10. program SumaCifrelor; var n: Integer; function SumaCifre(n: LongInt): LongInt; begin if n=0 then SumaCifre := 0 else SumaCifre := n mod 10 + SumaCifre(n div 10) end; begin Write('Dati un numar intreg: '); ReadLn(n); WriteLn('Suma cifrelor sale este: ', SumaCifre(n)); ReadLn end. Iat cum funcioneaz programul anterior (i funcia SumaCifre) pentru numrul n=74. Din programul principal se apeleaz SumaCifre(74). Cum 74 nu este zero, se apeleaz recursiv funcia pentru numrul 74 div 10, deci SumaCifre(7). Aici, se va apela SumaCifre(0) (cci 7 div 10 = 0), care returneaz 0. Acest numr se adaug lui 7 mod 10, adic lui 7, obinndu-se 7. (Acest lucru se petrece pentru SumaCifre(7).). Se revine apoi n apelul SumaCifre(74), unde 7 se adaug lui 74 mod 10, adic lui 4, obinnduse 11, care este suma cifrelor numrului 74. 99? ntrebri i exerciii1 Scriei o funcie repetitiv pentru a calcula suma cifrelor unui numr. Comparai aceast funcie cu funcia din varianta recursiv. 2 Scriei o funcie recursiv care s calculeze produsul elementelor unui vector. 3 Scriei o funcie recursiv care s determine inversul (oglinditul) unui numr natural dat. Scriei i varianta iterativ a acestei funcii. 7.2.6. Suma elementelor unui vector S scriem un program care, pe baza unei funcii recursive. s calculeze suma sum a componentelor unui vector a cu ne numere ntregi.Ideea care st la baza calculrii recursive a sumei componentelor vectorului este asemntoare celei de la calculul factorialului unui numr. Astfel, dac vectorul nu ar avea elemente, suma ar fi nul. Dac are cel puin un element, atunci suma este dat de suma celor dinainte plus ultimul element. program SumaElementelorUnuiVector_FunctieRec; type vector=array[1..10] of Integer; function Suma(x: vector; n: Integer):Integer; begin if n=0 then Suma:=0 else Suma:=x[n]+Suma(x,n-1) end; var a: vector; i,ne,sum: Integer; begin WriteLn('Suma elementelor unui vector - recursiv'); WriteLn('***************************************'); Write('Dati nr. de elemente: '); ReadLn(ne); for i:=1 to ne do begin Write('Dati a[',i,']: '); ReadLn(a[i]) end; sum := Suma(a,ne); WriteLn('Suma elementelor vectorului: ',sum); ReadLn end. ? ntrebri i exerciii1 Scriei un program asemntor celui de mai nainte pentru a calcula produsul elementelor dintr-un vector. 2 Ce calculeaz urmtoarea funcie recursiv? function NuStiuCe(x: vector; n: Integer):Integer; begin if n=1 then NuStiuCe:=x[1] else NuStiuCe:=x[n]+NuStiuCe(x,n-1) end; Ce diferena exist fa de funcia Suma din programul prezentat? 3 Scriei o funcie recursiv care s calculeze suma elementelor pare dintr-un vector de numere reale. 1004 e Scriei o funcie recursiv care s dea produsul elementelor pare de pe poziii impare dintr-un vector de ntregi. 7.2.7. Existena unui element ntr-un vector Un exemplu foarte interesant de funcie recursiv este urmtorul, care face o cutare secvenial a unui element a ntr-un vector x n cadrul primelor sale n componente. Fie, aadar, type vector=array[1..10] of Integer. Putem scrie funcia logic: function Exista(x: vector; a: Integer): Boolean; begin if n=0 then Exista := False else Exista := (x[n]=a) or Exista(x,n-1) end; Astfel, funcia exprim formal urmtorul lucru: dac vectorul nu are elemente, atunci evident a nu se afl n x; n schimb, dac x are elemente, atunci a se afl n x printre primele sale n elemente fie dac este ultimul, fie dac se afl printre cele n-1 anterioare. ? ntrebri i exerciii1 Ce realizeaz urmtoarea funcie logic? function NuStiuCe(x: vector; a: Integer): Boolean; begin if n=1 then NuStiuCe := x[1]=a else NuStiuCe := (x[n]=a) or NuStiuCe(x,n-1) end; 2 Scriei o funcie logic recursiv pentru a determina dac un vector conine un element negativ sau nu. 3 e Scriei o funcie logic recursiv pentru a determina dac un vector conine sau nu un element negativ pe o poziie par din vector. 7.3. Proceduri recursive 7.3.1. Suma componentelor unui vector Pn acum am prezentat recursivitatea prin intermediul subprogramelor de tip funcie. Firete, putem avea i proceduri recursive, iar aici comunicarea de valori ntre diferitele apeluri succesive se realizeaz prin intermediul unor parametri variabili (referin). Astel, de exemplu, vom rescrie programul din seciunea 3.2.7 care calcula (pe baza unei funcii recursive) suma componentelor unui vector cu numere ntregi, nlocuind funcia Suma cu o procedur PSuma, care se bazeaz pe aceeai idee. program SumaElementelorUnuiVector_ProcRec; type vector=array[1..10] of Integer; 101procedure PSuma(x: vector; n: Integer; var s: Integer); begin if n=0 then s:=0 else begin PSuma(x, n-1,s); s:=s+x[n] end end; var a: vector; i,ne,sum: Integer; begin WriteLn('Suma elementelor unui vector - recursiv'); WriteLn('***************************************'); Write('Dati nr. de elemente: '); ReadLn(ne); for i:=1 to ne do begin Write('Dati a[',i,']: '); ReadLn(a[i]) end; Suma(a,ne,sum); WriteLn('Suma elementelor vectorului: ',sum); ReadLn end. 7.3.2. Inversarea unui cuvnt S se scrie o procedur recursiv care citete caractere (numere) i le afieaz n ordinea invers citirii (far a lucra cu iruri; nu se cunoate apriori numrul de caractere). Rezolvarea se bazeaz pe procedura Inverseaza din programul de mai jos: Dac s-a tastat Enter (deci funcia EoLn returneaz True, atunci procesul apelurilor recursive se oprete, se afieaz ultimul caracter i, la ntoarcerile din apelurile recursive are loc o afiare a celorlalte caractere, n ordine invers. {$X+} program InversareCuvint; uses Crt; var n: Integer; procedure Inverseaza; var c: Char; begin Read(c); if not EoLn then Inverseaza; Write(c) end; begin ClrScr; Write('Dati cuvantul: '); Inverseaza; WriteLn(' este cuvantul inversat.'); ReadKey end. 1027.3.3. inversarea elementelor dintr-un ir Vom considera urmtoarea problem: se d un ir de cuvinte citite de la tastatur, numrul lor iniial (n) cunoscndu-se. Se cere s se prezinte irul acestor cuvinte n ordinea invers citirii lor.Firete, programul se poate rezolva repetitiv, folosind un vector care s pstreze cele n cuvinte introduse de la tastatur. O rezolvare mai elegant se bazeaz pe recursivitate. Astfel, inversarea irului de cuvinte se poate face pe msura citirii lor.Astfel, n cadrul procedurii recursive Inverseaza din programul de mai jos, dac s-a ajuns la ultimul cuvnt, acesta se afieaz, iar dac nu (i