Algoritmi. Tehnici si Limbaje de Programare

VALERIU LUPU

ALGORITMI. TEHNICI I

LIMBAJE DE PROGRAMARE

EDITURA UNIVERSITII TEFAN cel MARE SUCEAVA

2007

Prefa

Cartea isi propune in primul rand sa fie un curs si nu o "enciclopedie" de algoritmi. Pornind de la structurile de date cele mai uzuale si de la analiza eficientei algoritmilor, cartea se concentreaza pe principiile fundamentale de elaborare a algoritmilor: greedy, divide et impera, programare dinamica, backtracking. Majoritatea algoritmilor selectati au o conotatie estetica. Efortul necesar pentru intelegerea elementelor mai subtile este uneori considerabil. Ce este insa un algoritm "estetic"? Putem raspunde foarte simplu: un algoritm este estetic daca exprima mult in cuvinte putine. Un algoritm estetic este oare in mod necesar si eficient? Cartea raspunde si acestor intrebari.

In al doilea rand, cartea prezinta mecanismele interne esentiale ale limbajului Visual Basic si trateaza implementarea algoritmilor in mod iterative cat si recursiv. Totusi, aceasta carte nu este un curs complet de Visual Basic. Algoritmii nu sunt pur si simplu "transcrisi" din pseudo-cod in limbajul Visual Basic, ci sunt reganditi din punct de vedere al programarii orientate pe obiect. Speram ca, dupa citirea cartii, veti dezvolta aplicatii de programare in mod iterative cat si recursiv si veti elabora implementari ale altor structuri de date. Programele pot fi scrise si in limbajul C#. Acest limbaj se caracterizeaza, in principal, prin introducerea claselor parametrice si a unui mecanism de tratare a exceptiilor foarte avansat, facilitati deosebit de importante pentru dezvoltarea de biblioteci C#.

Fara a face concesii rigorii matematice, prezentarea este intuitiva, cu numeroase exemple. Am evitat, pe cat posibil, situatia in care o carte de informatica incepe - spre disperarea ne-matematicienilor - cu celebrul "Fie ... ", sau cu o definitie. Am incercat, pe de alta parte, sa evitam situatia cand totul "este evident", sau "se poate demonstra". Fiecare capitol este conceput fluid, ca o mica poveste, cu putine referinte si note. Multe rezultate mai tehnice sunt obtinute ca exercitii. Algoritmii sunt prezentati intr-un limbaj pseudo-cod compact, fara detalii inutile.

Presupunem ca cititorul nu are la baza cel putin un curs introductiv in programare, fiindu-i straini termeni precum algoritm, recursivitate, functie, procedura si pseudo-cod. Exista mai multe modalitati de parcurgere a cartii. In functie de interesul si pregatirea cititorului, acesta poate alege oricare din partile referitoare la elaborarea, analiza, sau implementarea algoritmilor. Cu exceptia partilor de analiza a eficientei algoritmilor (unde sunt necesare elemente de matematici superioare), cartea poate fi parcursa si de catre un elev de liceu. Pentru parcurgerea sectiunilor de implementare, este recomandabila cunoasterea limbajului Visual Basic.

S-a dovedit utila si experienta autorului de peste douzeci de ani in dezvoltarea produselor software. Le multumesc pentru aprecieri pro/contra asupra lucrrii membrilor catedrei de informatic de la Facultatea de tiine Economice i Administraie Public.

Autorul,

Conf. univ. dr. Lupu Valeriu

Universitatea tefan cel Mare Suceava

Facultatea de tiine Economice i Administraie Public

Catedra de InformaticCuprins

Capitolul IDescrierea algoritmilor .................................................................................................6

Capitolul IISubprograme ..............................................................................................................16

Capitolul IIIMetode de proiectare a algoritmilor ...........................................................................23

Capitolul IVAnaliza algoritmilor ...................................................................................................27

Capitolul VClase de algoritmi ........................................................................................................34

Capitolul VIEvoluia limbajelor de programare .............................................................................41

Capitolul VIILimbajul Visual Basic ................................................................................................55

Capitolul VIIIReguli privind alegerea unui limbaj de programare ...................................................69

Capitolul IXMetoda backtracking ..................................................................................................73

Capitolul XMetoda Divide et impera ............................................................................................91

Capitolul XIMetoda Greedy ...........................................................................................................95

Capitolul XIIStudii de caz Aplicaii ...........................................................................................109

Bibliografie....................................................................................................................................135

CAPITOLUL I

DESCRIEREA ALGORITMILOR

1.1 Algoritm, program, programare

Apariia primelor calculatoare electronice a constituit un salt uria n direcia automatizrii activitii umane. Nu exist astzi domeniu de activitate n care calculatorul s nu i arate utilitatea[18].

Calculatoarele pot fi folosite pentru a rezolva probleme, numai dac pentru rezolvarea acestora se concep programe corespunztoare de rezolvare. Termenul de program (programare) a suferit schimbri n scurta istorie a informaticii. Prin anii '60 problemele rezolvate cu ajutorul calculatorului erau simple i se gseau algoritmi nu prea complicai pentru rezolvarea lor. Prin program se nelegea rezultatul scrierii unui algoritm ntrun limbaj de programare. Din cauza creterii complexitii problemelor, astzi pentru rezolvarea unei probleme adesea vom concepe un sistem de mai multe programe.

Dar ce este un algoritm? O definiie matematic, riguroas, este greu de dat, chiar imposibil fr a introduce i alte noiuni. Vom ncerca n continuare o descriere a ceea ce se nelege prin algoritm.

Ne vom familiariza cu aceast noiune prezentnd mai multe exemple de algoritmi i observnd 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 muli algoritmi, cei mai muli fiind legai de probleme accesibile absolvenilor de liceu.

Vom constata c un algoritm este un text finit, o secven finit de propoziii ale unui limbaj. Din cauz c este inventat special n acest scop, un astfel de limbaj este numit limbaj de descriere a algoritmilor. Fiecare propoziie a limbajului precizeaz o anumit regul de calcul, aa cum se va observa atunci cnd vom prezenta limbajul Pseudocod.

Oprindu-ne la semnificaia algoritmului, la efectul execuiei lui, vom observa c fiecare algoritm definete o funcie matematic. De asemenea, din toate seciunile urmtoare va reiei foarte clar c un algoritm este scris pentru rezolvarea unei probleme. Din mai multe exemple se va observa ns c, pentru rezolvarea aceleai probleme, exist mai muli algoritmi.

Pentru fiecare problem P exist date presupuse cunoscute (date iniiale pentru algoritmul corespunztor, A) i rezultate care se cer a fi gsite (date finale). Evident, problema s-ar putea s nu aib sens pentru orice date iniiale. Vom spune c datele pentru care problema P are sens fac parte din domeniul D al algoritmului A. Rezultatele obinute fac parte dintr-un domeniu R, astfel c executnd algoritmul A cu datele de intrare x(D vom obine rezultatele r(R. Vom spune c A(x)=r i astfel algoritmul A definete o funcie

A : D ---> R .

Algoritmii au urmtoarele caracteristici: generalitate, finitudine i unicitate.

Prin generalitate se nelege faptul c un algoritm este aplicabil pentru orice date iniiale x(D. Deci un algoritm A nu rezolv problema P cu nite date de intrare, ci o rezolv n general, oricare ar fi aceste date. Astfel, algoritmul de rezolvare a unui sistem liniar de n ecuaii cu n necunoscute prin metoda lui Gauss, rezolv orice sistem liniar i nu un singur sistem concret.

Prin finitudine se nelege c textul algoritmului este finit, compus dintr-un numr finit de propoziii. Mai mult, numrul transformrilor ce trebuie aplicate unei informaii admisibile x(D pentru a obine rezultatul final corespunztor este finit.

Prin unicitate se nelege c toate transformrile prin care trece informaia iniial pentru a obine rezultatul r(R sunt bine determinate de regulile algoritmului. Aceasta nseamn c fiecare pas din execuia algoritmului d rezultate bine determinate i precizeaz n mod unic pasul urmtor. Altfel spus, ori de cte ori am executa algoritmul, pornind de la aceeai informaie admisibil x(D, transformrile prin care se trece i rezultatele obinute sunt aceleai.

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 puin folosite n descrierea algoritmilor i nu sunt deloc potrivite n cazul problemelor complexe. Prezentm ns i schemele logice, care se mai folosesc n manualele de liceu, ntruct cu ajutorul lor vom preciza n continuare semantica propoziiilor 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) reprezentnd operaiile (paii) algoritmului, iar ordinea lor de aplicare (succesiunea operaiilor) este indicat prin sgei. Fiecrui tip de operaie i este consacrat o figur geometric (un bloc tip) n interiorul creia se va nscrie operaia din pasul respectiv.

Prin execuia unui algoritm descris printr-o schem logic se nelege efectuarea tuturor operaiilor precizate prin blocurile schemei logice, n ordinea indicat de sgei.

n descrierea unui algoritm, deci i ntr-o schem logic, intervin variabile care marcheaz att datele cunoscute iniial, ct i rezultatele dorite, precum i alte rezultate intermediare necesare n rezolvarea problemei. ntruct variabila joac un rol central n programare este bine s definim acest concept. Variabila definete o mrime 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, situaie n care vom spune c ea este neiniializat. Valorile pe care le poate lua variabila aparin unei mulimi D pe care o vom numi domeniul variabilei. n concluzie vom nelege prin variabil tripletul

(nume, domeniul D, valoare)

unde valoare aparine mulimii D ( {nedefinit}.

Blocurile delimitatoare Start i Stop (Fig.1.2.1. a i 1.2.1. b) vor marca nceputul respectiv sfritul 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 puin un bloc Stop.

Blocurile de intrare/ieire Citete i Tiprete (Fig. 1.2.1. c i d) indic introducerea unor Date de intrare respectiv extragerea unor Rezultate finale. Ele permit precizarea datelor iniiale cunoscute n problem i tiprirea rezultatelor cerute de problem. Blocul Citete iniializeaz variabilele din lista de intrare cu valori corespunztoare, iar blocul Tiprete va preciza rezultatele obinute (la execuia pe calculator cere afiarea pe ecran a valorilor expresiilor din lista de ieire).

Blocurile de atribuire (calcul) se utilizeaz n descrierea operaiilor de atribuire (:=). Printr-o astfel de operaie, unei variabile var i se atribuie valoarea calculat a unei expresii expr (Fig.1.2.1. e).

Fig.1.2.1. Blocurile schemelor logice

Blocurile de decizie marcheaz punctele de ramificaie 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 execuia algoritmului n funcie de ndeplinirea (ramura Da) sau nendeplinirea (ramura Nu) unei condiii. Condiia care se va nscrie n blocul de decizie logic va fi o expresie logic a crei valoare poate fi una dintre valorile "adevrat" sau "fals". Blocul de decizie aritmetic va hotr ramura de continuare a algoritmului n funcie de semnul valorii expresiei aritmetice nscrise n acest bloc, care poate fi negativ, nul sau pozitiv.

Blocurile de conectare marcheaz ntreruperile sgeilor de legtur 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, corespunztoare unor algoritmi pentru rezolvarea problemelor P1.2.1 i P1.2.2.

P1.2.1. S se rezolve ecuaia de grad doi aX2+bX+c=0 (a,b,c(R _i a(0).Metoda de rezolvare a ecuaiei de gradul doi este cunoscut. Ecuaia poate avea rdcini reale, respectiv complexe, situaie recunoscut dup semnul discriminantului d = b2 - 4ac.

Fig.1.2.2. Algoritm pentru rezolvarea ecuaiei de gradul doiFig.1.2.3. Algoritm pentru calculul unei sume.

Algoritmul de rezolvare a problemei va citi mai nti datele problemei, marcate prin variabilele a, b i c. Va calcula apoi discriminantul d i va continua n funcie de valoarea lui d, aa cum se poate vedea n fig.1.2.2.

P1.2.2. S se calculeze suma elementelor pozitive ale unui ir de numere reale dat.1

Schema logic (dat n Fig.1.2.3) va conine 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 tiprire a sumei gsite, naintea blocului STOP. Partea care calculeaz suma S cerut are un bloc pentru iniializarea cu 0 a acestei sume, apoi blocuri pentru parcurgerea numerelor: x1, x2xn i adunarea celor pozitive la suma S. Pentru aceast parcurgere se folosete o variabil contor i, care este iniializat cu 1 i crete mereu cu 1 pentru a atinge valoarea n, indicele ultimului numr dat.

Schemele logice dau o reprezentare grafic a algoritmilor cu ajutorul unor blocuri de calcul. Execuia urmeaz sensul indicat de sgeat, putnd avea loc reveniri n orice punct din schema logic. Din acest motiv se poate obine o schem logic nclcit, greu de urmrit. Rezult importana compunerii unor scheme logice structurate (D-scheme, dup Djikstra), care s conin numai anumite structuri standard de calcul i n care drumurile de la START la STOP s fie uor de urmrit.

1.3. Limbajul PSEUDOCOD

Limbajul Pseudocod este un limbaj inventat n scopul proiectrii algoritmilor i este format din propoziii asemntoare propoziiilor limbii romne, 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. innd seama c obinerea 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 urmtoare, n etapele intermediare din obinerea algoritmului vom folosi propoziii curente din limba romn. Acestea sunt considerate elemente nefinisate din algoritm, asupra crora trebuie s se revin i le vom numi propoziii nestandard. Deci limbajul Pseudocod are dou tipuri de propoziii: propoziii standard, care vor fi prezentate fiecare cu sintaxa i semnificaia (semantica) ei i propoziii nestandard. Aa cum se va arta mai trziu, propoziiile nestandard sunt texte care descriu pri ale algoritmului nc incomplet elaborate, nefinisate, asupra crora urmeaz s se revin.

Pe lng aceste propoziii standard i nestandard, n textul algoritmului vom mai introduce propoziii explicative, numite comentarii. Pentru a le distinge de celelalte propoziii, comentariile vor fi nchise ntre acolade. Rolul lor va fi explicat puin mai trziu.

Propoziiile 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 propoziie standard ncepe cu un cuvnt cheie, aa 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. Menionm c i propoziiile simple se termin cu caracterul ';' n timp ce propoziiile compuse, deci cele n interiorul crora se afl alte propoziii, au un marcaj de sfrit propriu. De asemenea, menionm c propoziiile limbajului Pseudocod vor fi luate n seam n ordinea ntlnirii lor n text, asemenea oricrui text al limbii romne.

Prin execuia unui algoritm descris n Pseudocod se nelege efectuarea operaiilor precizate de propoziiile algoritmului, n ordinea citirii lor.

n figura 1.3.1, prin A, B s-au notat subscheme logice, adic secvene de oricte structuri construite conform celor trei reguli menionate n continuare.

Structura secvenial (fig.1.3.1.a) este redat prin concatenarea propoziiilor, simple sau compuse, ale limbajului Pseudocod, care vor fi executate n ordinea ntlnirii lor n text.

a) structura

secvenialb) structura

alternativc) structura

repetitiv

Figura 1.3.1. Structurile elementare de calcul

Propoziiile simple din limbajul Pseudocod sunt CITETE, TIPARETE, FIE i apelul de subprogram. Propoziiile compuse corespund structurilor alternative i repetitive.

Structura alternativ (fig.1.3.1.b) este redat n Pseudocod prin propoziia DAC, prezentat n seciunea 1.3.2, iar structura repetitiv din fig.1.3.1.c este redat n Pseudocod prin propoziia CT TIMP, prezentat n seciunea 1.3.3.

Bohm i Jacopini au demonstrat c orice algoritm poate fi descris folosind numai aceste trei structuri de calcul.

Propoziiile DATE i REZULTATE sunt folosite n faza de specificare a problemelor, adic enunarea riguroas a acestora. Propoziia DATE se folosete pentru precizarea datelor iniiale, deci a datelor considerate cunoscute n problem (numite i date de intrare) i are sintaxa:

DATE list;

unde list conine toate numele variabilelor a cror valoare iniial este cunoscut. n general, prin list se nelege o succesiune de elemente de acelai fel desprite prin virgul. Deci n propoziia DATE, n dreapta acestui cuvnt se vor scrie acele variabile care marcheaz mrimile cunoscute n problem.

Pentru precizarea rezultatelor dorite se folosete propoziia standard

REZULTATE list;

n construcia "list" ce urmeaz dup cuvntul REZULTATE fiind trecute numele variabilelor care marcheaz (conin) rezultatele cerute n problem.

Acum putem preciza mai exact ce nelegem prin cunoaterea complet a problemei de rezolvat. Evident, o problem este cunoscut atunci cnd se tie care sunt datele cunoscute n problem i ce rezultate trebuiesc obinute. Deci pentru cunoaterea unei probleme este necesar precizarea variabilelor care marcheaz date considerate cunoscute n problem, care va fi reflectat printro propoziie DATE i cunoaterea exact a cerinelor problemei, care se va reflecta prin propoziii REZULTATE. Variabilele prezente n aceste propoziii au anumite semnificaii, presupuse cunoscute. Cunoaterea 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 ecuaiei de gradul al doilea, specificarea problemei, scris de un nceptor, poate fi:

DATE a,b,c;{ Coeficienii ecuaiei }

REZULTATE x1,x2;{ Rdcinile ecuaiei }

Aceast specificaie este ns incomplet dac ecuaia nu are rdcini reale. n cazul n care rdcinile sunt complexe putem nota prin x1, x2 partea real respectiv partea imaginar a rdcinilor. Sau pur i simplu, nu ne intereseaz valoarea rdcinilor n acest caz, ci doar faptul c ecuaia nu are rdcini reale. Cu alte cuvinte avem nevoie de un mesaj care s ne indice aceast situaie (vezi schema logic 1.2.2), sau de un indicator, fie el ind. Acest indicator va lua valoarea 1 dac rdcinile sunt reale i valoarea 0 n caz contrar. Deci specificaia corect a problemei va fi

DATE a,b,c;{ Coeficienii ecuaiei }

REZULTATE ind,{Un indicator: 1=rdcini reale, 0=complexe}

x1,x2; { Rdcinile ecuaiei, n cazul ind=1,}

{respectiv partea real i cea }

{imaginar n cazul ind=0}

Evident c specificarea problemei este o etap important pentru gsirea unei metode de rezolvare i apoi n proiectarea algoritmului corespunztor. Nu se poate rezolva o problem dac aceasta nu este bine cunoscut, adic nu avem scris specificarea problemei. Cunoate complet problema este prima regul ce trebuie respectat pentru a obine ct mai repede un algoritm corect pentru rezolvarea ei.

1.3.1 Algoritmi liniari

Propoziiile CITETE i TIPRETE sunt folosite pentru iniializarea variabilelor de intrare cu datele cunoscute n problem, respectiv pentru tiprirea (aflarea) rezultatelor obinute. n etapa de programare propriu-zis acestor propoziii le corespund ntr-un limbaj de programare instruciuni de intrare-ieire.

Propoziia CITETE se folosete pentru precizarea datelor iniiale, deci a datelor considerate cunoscute n problem (numite i date de intrare) i are sintaxa:

CITETE list ;unde list conine toate numele variabilelor a cror valoare iniial este cunoscut.

Deci n propoziia CITETE, n dreapta acestui cuvnt se vor scrie acele variabile care apar n propoziia DATE n specificarea problemei. Se subnelege c aceste variabile sunt iniializate cu valorile cunoscute corespunztoare.

Pentru aflarea rezultatelor dorite, pe care calculatorul o va face prin tiprirea lor pe hrtie sau afiarea pe ecran, se folosete propoziia standard

TIPRETE list ;

n construcia list ce urmeaz dup cuvntul TIPRETE fiind trecute numele variabilelor a cror valori dorim s le aflm. Ele sunt de obicei rezultatele cerute n problem, specificate i n propoziia REZULTATE.

Blocului de atribuire dintr-o schem logic i corespunde n Pseudocod propoziia standard[FIE] var := expresie ;Aceast propoziie este folosit pentru a indica un calcul algebric, al expresiei care urmeaz dup simbolul de atribuire ":=" i de atribuire a rezultatului obinut 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 operaii: adunare, scdere, nmulire i mprire (notate prin caracterele +, -, *, respectiv /).

Prin scrierea cuvntului FIE ntre paranteze drepte se indic posibilitatea omiterii acestui cuvnt din propoziie. El s-a folosit cu gndul ca fiecare propoziie s nceap cu un cuvnt al limbii romne care s reprezinte numele propoziiei. De cele mai multe ori vom omite acest cuvnt. Atunci cnd vom scrie succesiv mai multe propoziii de atribuire vom folosi cuvntul FIE numai n prima propoziie, omindu-l n celelalte.

Din cele scrise mai sus rezult c o variabil poate fi iniializat att prin atribuire (deci dac este variabila din stnga semnului de atribuire :=) ct i prin citire (cnd face parte din lista propoziiei CITETE). O greeal frecvent pe care o fac nceptorii este folosirea variabilelor neiniializate. Evident c o expresie n care apar variabile care nu au valori nu poate fi calculat, ea nu este definit. Deci nu folosii variabile neiniializate.

Pentru a marca nceputul descrierii unui algoritm vom folosi propoziia:

ALGORITMUL nume ESTE:

fr a avea o alt semnificaie. De asemenea, prin cuvntul SFALGORITM vom marca sfritul unui algoritm.

Algoritmii care pot fi descrii folosind numai propoziiile prezentate mai sus se numesc algoritmi liniari.

Ca exemplu de algoritm liniar prezentm un algoritm ce determin viteza v cu care a mers un autovehicul ce a parcurs distana D n timpul T.

ALGORITMUL VITEZA ESTE:{ A1: Calculeaz viteza }

{ D = Distana (spaiul) }

{ T = Timpul; V = Viteza }

CITETE D,T;{ v:= spaiu/timp }

FIE V:=D/T;

TIPRETE V

SFALGORITM1.3.2 Algoritmi cu ramificaii

Foarte muli algoritmi execut anumite calcule n funcie de satisfacerea unor condiii. Aceste calcule sunt redate de structura alternativ prezentat n figura 1.3.1.b, creia i corespunde propoziia Pseudocod

DAC cond ATUNCI A ALTFEL B SFDACsau varianta redus a ei,DAC cond ATUNCI A SFDACfolosit n cazul n care grupul de propoziii B este vid.

Aceste propoziii redau n Pseudocod structura alternativ de calcul. Ele cer mai nti verificarea condiiei scrise dup cuvntul DAC. n caz c aceast condiie este adevrat se va executa grupul de propoziii A. n cazul n care aceast condiie este fals se va executa grupul de propoziii B, dac este prezent ramura ALTFEL. Indiferent care dintre secvenele A sau B a fost executat, se va continua cu propoziia urmtoare propoziiei DAC.

O generalizare a structurii alternative realizat de propoziia DAC este structura selectiv:

SELECTEAZ i DINTRE v1: A1;

v2: A2;

. . .

vn: An

SFSELECTEAZ

structur echivalent cu urmtorul text Pseudocod:

DAC i=v1 ATUNCI A1 ALTFEL

DAC i=v2 ATUNCI A2 ALTFEL

. . .

DAC i=vn ATUNCI An SFDAC . . .

SFDACSFDAC

Cu propoziiile prezentate pn aici putem deja descrie destui algoritmi. Acetia se numesc algoritmi cu ramificaii.

Ca exemplu vom scrie un algoritm pentru rezolvarea ecuaiei de gradul al doilea. Am scris mai sus specificaia acestei probleme i am precizat semnificaia variabilelor respective. Pe lng aceste variabile, pentru rezolvarea problemei mai avem nevoie de dou variabile auxiliare:

delta pentru a reine discriminantul ecuaiei;

r pentru a reine valoarea radicalului folosit n exprimarea rdcinilor.

Ajungem uor la algoritmul dat n continuare.

ALGORITMUL ECGRDOI ESTE:{ Algoritmul 2: Rezolvarea }

{ ecuaiei de gradul doi }

CITETE a,b,c;{ a,b,c = Coeficienii ecuaiei }

FIE delta:=b*b4*a*c;

DAC deltafinal i p>0) sau (c {2,3,4,5}, definit matematic astfel:

n Pseudocod descrierea este urmtoarea:

FUNCIA numar(x) ESTE:

DAC x0 i faptul c 0!=1. Recursivitatea const n faptul c n definiia funciei Factorial de n se folosete aceeai funcie Factorial dar de argument n-1. Deci funcia Factorial se apeleaz pe ea nsi. Este important ca numrul apelurilor s fie finit, deci ca procedeul de calcul descris s se termine.

FUNCTIA Factorial(n) ESTE:

DAC n=0ATUNCI Factorial:=1

ALTFEL Factorial:= n*Factorial(n1)

SFDACSF-Factorial;

Tot ca exemplu de apel recursiv putem descrie o funcie ce calculeaz maximul a n numere x1,x2,...,xn. Ea se bazeaz pe funcia MAXIM2 care calculeaz maximul a dou numere, descris n continuare.

FUNCIA MAXIM2(a,b) ESTE:

DAC akn)}{sau (1k1 atunci Cttimp p(n i a>kp execut p:=p+1 sfct sfdacsf-CautSecvO alt metod, numit cutare binar, care este mult mai eficient, utilizeaz tehnica "divide et impera" privitor la date. Se determin n ce relaie se afl cheia articolului aflat n mijlocul coleciei cu cheia de cutare. n urma acestei verificri cutarea se continu doar ntr-o jumtate a coleciei. n acest mod, prin njumtiri succesive se micoreaz volumul coleciei rmase pentru cutare. Cutarea binar se poate realiza practic prin apelul funciei BinarySearch(a,n,K,1,n), descris mai jos, folosit n SUBPROGRAMul dat n continuare.SUBPROGRAMul CautBin(a,n,K,p) este:{n(N, n(1 i k1 < k2 < .... < kn}{Se caut p astfel ca: (p=1 i a ( k1) sau} {(p=n+1 i a>kn) sau (1kn atunci p:=n+1 altfel p:=BinarySearch(a,n,K,1,n) sfdac sfdacsf-CautBinFuncia BinarySearch (a,n,K,St,Dr) este: Dac St(Dr-1 atunci BinarySearch:=Dr altfel m:=(St+Dr) Div 2; Dac a(K[m] atunci BinarySearch:=BinarySearch(a,n,K,St,m) altfel BinarySearch:=BinarySearch(a,n,K,m,Dr) sfdac sfdacsf-BinarySearchn funcia BinarySearch descris mai sus, variabilele St i Dr reprezint capetele intervalului de cutare, iar m reprezint mijlocul acestui interval.Se observ c funcia BinarySearch se apeleaz recursiv. Se poate nltura uor recursivitatea, aa cum se poate vedea n urmtoarea funcie:Funcia BinSeaNerec (a,n,K,St,Dr) este: Cttimp Dr-St>1 execut m:=(St+Dr) Div 2; Dac a(K[m] atunci Dr:=m altfel St:=m sfdac sfct BinSeaNerec:=Drsf-BinSeaNerec5.2 Sortare internPrin sortare intern vom nelege o rearanjare a unei colecii aflate n memoria intern astfel nct cheile articolelor s fie ordonate cresctor (eventual descresctor).Din punct de vedere al complexitii algoritmilor problema revine la ordonarea cheilor. Deci specificarea problemei de sortare intern este urmtoarea:Date n,K;{K=(k1,k2,...,kn)}Precondiia: ki(R, i=1,nRezultate K';Postcondiia: K' este o permutare a lui K, dar ordonat cresctor. Deci k1 ( k2 ( ... ( kn.O prim tehnic numit "Selecie" se bazeaz pe urmtoarea idee: se determin poziia elementului cu cheie de valoare minim (respectiv maxim), dup care acesta se va interschimba cu primul element. Acest procedeu se repet pentru subcolecia rmas, pn cnd mai rmne doar elementul maxim.SUBPROGRAMul Selectie(n,K) este:{Se face o permutare a celor}{n componente ale vectorului K astfel}{ca k1 ( k2 ( .... ( kn } Pentru i:=1; n-1 execut Fie ind:=i; Pentru j:=i+1; n execut Dac kj < kind atunci ind:=j sfdac sfpentru Dac i ki atunci t := ki-1; ki-1 := ki; ki:=t; kod:=1{N-a fost ordine!} sfdac sfpentru pncnd kod=0 sfrep{Ordonare}sf-BubbleSortO metod mai performant de ordonare, care va fi prezentat n continuare, se numete "QuickSort" i se bazeaz pe tehnica "divide et impera" dup cum se poate observa n continuare. Metoda este prezentat sub forma unei proceduri care realizeaz ordonarea unui subir precizat prin limita inferioar i limita superioar a indicilor acestuia. Apelul procedurii pentru ordonarea ntregului ir este : QuickSort(n,K,1,n), unde n reprezint numrul de articole ale coleciei date. SUBPROGRAMul SortareRapid (n,K) este: Cheam QuickSort(n,K,1,n)sf-SortareRapidProcedura QuickSort (n,K,St,Dr) va realiza ordonarea subirului kSt,kSt+1,..., kDr. Acest subir va fi rearanjat astfel nct kSt s ocupe poziia lui final (cnd irul este ordonat). Dac i este aceast poziie, irul va fi rearanjat astfel nct urmtoarea condiie s fie ndeplinit:kj ( ki ( kl , pentru st ( j < i < l (dr (*)Odat realizat acest lucru, n continuare va trebui doar s ordonm subirul kSt , kSt+1 , ... ,ki-1 prin apelul recursiv al procedurii QuickSort(n,K,St,i-1) i apoi subirul ki+1,..., kDr prin apelul QuickSort(i+1,Dr). Desigur ordonarea acestor dou subiruri (prin apelul recursiv al procedurii) mai este necesar doar dac acestea conin cel puin dou elemente. Procedura QuickSort este prezentat n continuare :SUBPROGRAMul QuickSort (n,K,St,Dr) este: Fie i:=St; j:=Dr; a:=ki; Repet Cttimp kj >= a i (i H {insereaza in min-heap} LU[i] Q[i]; ST[i] 0; DR[i] 0 for i n+1 to 2n1 do (s, j) D[v] + L[v, w] then D[w] D[v] + L[v, w] P[w] v bucla repeat se executa de n -1 oriSa presupunem ca aplicam algoritmul Dijkstra asupra unui graf cu n varfuri si m muchii. Initializarea necesita un timp in O(n). Alegerea lui v din bucla repeat presupune parcurgerea tuturor varfurilor continute in C la iteratia respectiva, deci a n -1,n -2,...,2 varfuri, ceea ce necesita in total un timp in O(n2). Bucla for interioara efectueaza n-2, n-3,...,1 iteratii, totalul fiind tot in O(n2). Rezulta ca algoritmul Dijkstra necesita un timp in O(n2).Incercam sa imbunatatim acest algoritm. Vom reprezenta graful nu sub forma matricii de adiacenta L, ci sub forma a n liste de adiacenta, continand pentru fiecare varf lungimea muchiilor care pleaca din el. Bucla for interioara devine astfel mai rapida, deoarece putem sa consideram doar varfurile w adiacente lui v. Aceasta nu poate duce la modificarea ordinului timpului total al algoritmului, daca nu reusim sa scadem si ordinul timpului necesar pentru alegerea lui v din bucla repeat. De aceea, vom tine varfurile v din C intr-un min-heap, in care fiecare element este de forma (v,D[v]), proprietatea de min-heap referindu-se la valoarea lui D[v]. Numim algoritmul astfel obtinut Dijkstra-modificat. Sa il analizam in cele ce urmeaza.Initializarea min-heap-ului necesita un timp in O(n). Instructiunea CC\{v} consta in extragerea radacinii min-heap-ului si necesita un timp in O(logn). Pentru cele n2 extrageri este nevoie de un timp in O(nlogn).Pentru a testa daca D[w]>D[v]+L[v,w], bucla for interioara consta acum in inspectarea fiecarui varf w din C adiacent lui v. Fiecare varf v din C este introdus in S exact o data si cu acest prilej sunt testate exact muchiile adiacente lui; rezulta ca numarul total de astfel de testari este de cel mult m. Daca testul este adevarat, trebuie sa il modificam pe D[w] si sa operam un percolate cu w in min-heap, ceea ce necesita din nou un timp in O(logn). Timpul total pentru operatiile percolate este deci in O(mlogn).In concluzie, algoritmul Dijkstra-modificat necesita un timp in O(max(n,m)logn). Daca graful este conex, atunci mn si timpul este in O(mlogn). Pentru un graf rar este preferabil sa folosim algoritmul Dijkstra-modificat, iar pentru un graf dens algoritmul Dijkstra este mai eficient.Este usor de observat ca, intr-un graf G neorientat conex, muchiile celor mai scurte drumuri de la un varf i la celelalte varfuri formeaza un arbore partial al celor mai scurte drumuri pentru G. Desigur, acest arbore depinde de alegerea radacinii i si el difera, in general, de arborele partial de cost minim al lui G.Problema gasirii celor mai scurte drumuri care pleaca din acelasi punct se poate pune si in cazul unui graf neorientat.11.6 Euristica greedyPentru anumite probleme, se poate accepta utilizarea unor algoritmi despre care nu se stie daca furnizeaza solutia optima, dar care furnizeaza rezultate acceptabile, sunt mai usor de implementat si mai eficienti decat algoritmii care dau solutia optima. Un astfel de algoritm se numeste euristic.Una din ideile frecvent utilizate in elaborarea algoritmilor euristici consta in descompunerea procesului de cautare a solutiei optime in mai multe subprocese succesive, fiecare din aceste subprocese constand dintr-o optimizare. O astfel de strategie nu poate conduce intotdeauna la o solutie optima, deoarece alegerea unei solutii optime la o anumita etapa poate impiedica atingerea in final a unei solutii optime a intregii probleme; cu alte cuvinte, optimizarea locala nu implica, in general, optimizarea globala. Regasim, de fapt, principiul care sta la baza metodei greedy. Un algoritm greedy, despre care nu se poate demonstra ca furnizeaza solutia optima, este un algoritm euristic.Vom da doua exemple de utilizare a algoritmilor greedy euristici.11.6.1 Colorarea unui grafFie G= un graf neorientat, ale carui varfuri trebuie colorate astfel incat oricare doua varfuri adiacente sa fie colorate diferit. Problema este de a obtine o colorare cu un numar minim de culori.Folosim urmatorul algoritm greedy: alegem o culoare si un varf arbitrar de pornire, apoi consideram varfurile ramase, incercand sa le coloram, fara a schimba culoarea. Cand nici un varf nu mai poate fi colorat, schimbam culoarea si varful de start, repetand procedeul.Figura 11.6 Un graf care va fi colorat.Daca in graful din Figura 11.6 pornim cu varful 1 si il coloram in rosu, mai putem colora tot in rosu varfurile 3 si 4. Apoi, schimbam culoarea si pornim cu varful 2, colorandu-l in albastru. Mai putem colora cu albastru si varful 5. Deci, ne-au fost suficiente doua culori. Daca coloram varfurile in ordinea 1, 5, 2, 3, 4, atunci se obtine o colorare cu trei culori.Rezulta ca, prin metoda greedy, nu obtinem decat o solutie euristica, care nu este in mod necesar solutia optima a problemei. De ce suntem atunci interesati intr-o astfel de rezolvare? Toti algoritmii cunoscuti, care rezolva optim aceasta problema, sunt exponentiali, deci, practic, nu pot fi folositi pentru cazuri mari. Algoritmul greedy euristic propus furnizeaza doar o solutie acceptabila, dar este simplu si eficient.Un caz particular al problemei colorarii unui graf corespunde celebrei probleme a colorarii hartilor: o harta oarecare trebuie colorata cu un numar minim de culori, astfel incat doua tari cu frontiera comuna sa fie colorate diferit. Daca fiecarui varf ii corespunde o tara, iar doua varfuri adiacente reprezinta tari cu frontiera comuna, atunci hartii ii corespunde un graf planar, adica un graf care poate fi desenat in plan fara ca doua muchii sa se intersecteze. Celebritatea problemei consta in faptul ca, in toate exemplele intalnite, colorarea s-a putut face cu cel mult 4 culori. Aceasta in timp ce, teoretic, se putea demonstra ca pentru o harta oarecare este nevoie de cel mult 5 culori.Problema colorarii unui graf poate fi interpretata si in contextul planificarii unor activitati. De exemplu, sa presupunem ca dorim sa executam simultan o multime de activitati, in cadrul unor sali de clasa. In acest caz, varfurile grafului reprezinta activitati, iar muchiile unesc activitatile incompatibile. Numarul minim de culori necesare pentru a colora graful corespunde numarului minim de sali necesare.11.6.2 Problema comis-voiajoruluiSe cunosc distantele dintre mai multe orase. Un comis-voiajor pleaca dintr-un oras si doreste sa se intoarca in acelasi oras, dupa ce a vizitat fiecare din celelalte orase exact o data. Problema este de a minimiza lungimea drumului parcurs. Si pentru aceasta problema, toti algoritmii care gasesc solutia optima sunt exponentiali.Problema poate fi reprezentata printr-un graf neorientat, in care oricare doua varfuri diferite ale grafului sunt unite intre ele printr-o muchie, de lungime nenegativa. Cautam un ciclu de lungime minima, care sa se inchida in varful initial si care sa treaca prin toate varfurile grafului.Conform strategiei greedy, vom construi ciclul pas cu pas, adaugand la fiecare iteratie cea mai scurta muchie disponibila cu urmatoarele proprietati: nu formeaza un ciclu cu muchiile deja selectate (exceptand pentru ultima muchie aleasa, care completeaza ciclul) nu exista inca doua muchii deja selectate, astfel incat cele trei muchii sa fie incidente in acelasi varfLa:23456De la:1310117252612826394204515518Tabelul 11.4 Matricea distantelor pentru problema comis-voiajorului.De exemplu, pentru sase orase a caror matrice a distantelor este data in Tabelul 11.4, muchiile se aleg in ordinea: {1,2}, {3,5}, {4,5}, {2,3}, {4,6}, {1,6} si se obtine ciclul (1,2,3,5,4,6,1) de lungime 58. Algoritmul greedy nu a gasit ciclul optim, deoarece ciclul (1,2,3,6,4,5,1) are lungimea 56.CAPITOLUL XIISTUDII DE CAZ APLICAII1. S se determine toate numerele perechile de numere gemene pana la o anumita valoare n. Dou numere sunt gemene dac sunt ambele prime i diferena dintre cel mai mare i cel mai mic este 2. Private Sub CommandButton1_Click() Dim rad As Integer, n As Integer, p As Integer, i As Integer, j As Integer cit_n "n = ", n For i = 3 To n p = 1 rad = Int(Sqr(i + 2)) For j = 2 To Int(rad) If i Mod j = 0 Or (i + 2) Mod j = 0 Then prim = 0 j = Int(rad) End If Next If p Then MsgBox "(" + Str$(i) + "," + Str$(i + 2) + ")" + Chr(13) End If NextEnd Sub2. S se citeasc o valoare naturala n cu valori cuprinse intre 1 i 100. Sub cit_n(mes As String, nnn As Integer) Do nnn = InputBox(mes, y) Loop Until n > 0 And n < 100End Sub3. Citirea unui vector cu n componenteSub cit_date(mes As String, n As Integer, a As vector) For i = 1 To n a.v(i) = InputBox(mes + "(" + Str$(i) + ")=", y) NextEnd Sub4. Tiprirea unui tablou cu n componenteSub tipar(mes As String, n As Integer, a As vector) sir = "" For i = 1 To n sir = sir + Str$(a.v(i)) + "," Next MsgBox mes + " " + sirEnd Sub5. Generarea permutrilor utiliznd metoda backtrackingPrivate Sub CommandButton14_Click() cit_n "n = ", n back_permEnd Sub6. Generarea produsului cartezian a n mulimi utiliznd metoda backtrackingPrivate Sub CommandButton16_Click() Dim a As vector cit_n "n=", n cit_date "a", n, a tipar " multimile sunt : ", n, a back_prod_cartEnd Sub7. Generarea permutrilor utiliznd metoda backtrackingPrivate Sub CommandButton17_Click() cit_n "n = ", n cit_n "p = ", p back_aranjEnd Sub8. Problema celor n dame utiliznd metoda backtrackingPrivate Sub CommandButton15_Click() cit_n "n = ", n backEnd Sub9. Generarea combinrilor (de n luate cte m) utiliznd metoda backtrackingPrivate Sub CommandButton18_Click() cit_n "n = ", n cit_n "p = ", p back_combEnd Sub10. Generarea partiiilor unei mulimi utiliznd metoda backtrackingPrivate Sub CommandButton19_Click() cit_n "n=", n back_partitiiEnd Sub11. Cutarea binar utiliznd metoda Divide et Impera pentru sortarea unui ir de numerePrivate Sub CommandButton2_Click() Dim n As Integer, x As Integer, a As vector cit_n "n = ", n cit_date "a", n, a tipar "sirul dat este : ", n, a divimp 1, n, a 'MsgBox "Sirul a sortat este" tipar "Sirul a sortat este", n, a x = InputBox(" x = ", y) st = 1 dr = n l = True While st a.v(q) Then m = a.v(p) a.v(p) = a.v(q) a.v(q) = m End IfEnd Sub13. Sortarea Merge-Sort utiliznd metoda Divide et impera Sub interc(p As Integer, q As Integer, m As Integer, a As vector) Dim b As vector, i, j, k As Integer i = p j = m + 1 k = 1 While (i 1 Then If st.ss(k) < st.ss(k - 1) Then ev = False End If End IfEnd Sub35. Subrutina valid pentru produs cartezian a n mulimiSub valid_prod(ev As Boolean, st As stiva, k As Integer) ev = TrueEnd Sub36. Subrutina soluie pentru generarea permutrilorFunction solutie(k As Integer) As Boolean If k = n Then solutie = True Else solutie = False End IfEnd Function37. Subrutina soluie pentru generarea aranjamentelor sau combinrilorFunction solutie1(k As Integer) As Boolean If k = p Then solutie1 = True Else solutie1 = False End IfEnd Function38. Subrutina tiprire pentru problema celor n dameSub tiparr() Dim i As Integer, b As String b = " " For i = 1 To n b = b + "(" + Str$(i) + "," + Str$(st.ss(i)) + ")," Next MsgBox bEnd Sub39. Subrutina tiprire pentru colorarea hrilorSub tipar_col() Dim i As Integer, b As String b = " " For i = 1 To nb = b + "Tara = " + Str$(i) + "; culoarea " + Str$(st.ss(i)) + " " Next MsgBox bEnd Sub40. Subrutina back pentru problema celor n dameSub back() Dim k As Integer k = 1 init k, st While k > 0 Do succesor am_suc, st, k If am_suc = True Then valid ev, st, k End If Loop Until (Not am_suc) Or (am_suc And ev) If am_suc Then If solutie(k) Then tiparr Else k = k + 1 init k, st End If Else k = k - 1 End If WendEnd Sub41. Programul principal pentru problema celor n dameSub Button2_Click() n = InputBox("n=", ib_title) backEnd Sub42. Subrutina back pentru generarea permutrilorSub back_perm() Dim k As Integer k = 1 init k, st While k > 0 Do succesor am_suc, st, k If am_suc = True Then valid1 ev, st, k End If Loop Until (Not am_suc) Or (am_suc And ev) If am_suc Then If solutie(k) Then tipar_r Else k = k + 1 init k, st End If Else k = k - 1 End If WendEnd Sub43. Subrutina back pentru generarea aranjamentelorSub back_aranj() Dim k As Integer k = 1 init k, st While k > 0 Do succesor am_suc, st, k If am_suc = True Then valid1 ev, st, k End If Loop Until (Not am_suc) Or (am_suc And ev) If am_suc Then If solutie1(k) Then tipar_rr Else k = k + 1 init k, st End If Else k = k - 1 End If WendEnd Sub44. Subrutina valid pentru metoda backtracking Sub valid1(ev As Boolean, st As stiva, k As Integer) ev = True For i = 1 To k - 1 If (st.ss(i) = st.ss(k)) Then ev = False End If NextEnd Sub45. Subrutina tipar pentru metoda backtracking Sub tipar_r() Dim i As Integer, b As String b = " " For i = 1 To n b = b + Str$(st.ss(i)) + "," Next MsgBox bEnd Sub46. Subrutina tipar pentru metoda backtracking Sub tipar_rr() Dim i As Integer, b As String b = " " For i = 1 To p b = b + Str$(st.ss(i)) + "," Next MsgBox bEnd Sub47. Subrutina back pentru generarea combinrilorSub back_comb() Dim k As Integer k = 1 init k, st While k > 0 Do succesor_c am_suc, st, k If am_suc = True Then valid_c ev, st, k End If Loop Until (Not am_suc) Or (am_suc And ev) If am_suc Then If solutie1(k) Then tipar_rr Else k = k + 1 init k, st End If Else k = k - 1 End If WendEnd Sub48. Subrutina back pentru generarea produsului cartezian a n multimiSub back_prod_cart() Dim k As Integer k = 1 init k, st While k > 0 Do succesor_prod am_suc, st, k If am_suc = True Then valid_prod ev, st, k End If Loop Until (Not am_suc) Or (am_suc And ev) If am_suc Then If solutie(k) Then tipar_r Else k = k + 1 init k, st End If Else k = k - 1 End If WendEnd Sub49. Subrutina back pentru generarea partiiilor unei mulimiSub back_partitii() Dim k As Integer k = 1 init k, st While k > 0 Do succesor_part am_suc, st, k If am_suc = True Then valid_prod ev, st, k End If Loop Until (Not am_suc) Or (am_suc And ev) If am_suc Then If solutie(k) Then tipar_part Else k = k + 1 init k, st End If Else k = k - 1 End If WendEnd Sub50. Subrutina tiparire pentru problema generare partiii a unei mulimiSub tipar_part() Dim i As Integer, max As Integer, j As Integer, sir As String sir = "" max = st.ss(1) For i = 2 To n If max < st.ss(i) Then max = st.ss(i) End If Next sir = " PARTITII " For j = 1 To max For i = 1 To n If st.ss(i) = j Then sir = sir + Str$(i) + " " End If Next sir = sir + Chr(10) Next MsgBox sirEnd Sub51. Subrutina succesor pentru problema generare partiii a unei mulimiSub succesor_part(am_suc As Boolean, st As stiva, k As Integer) Dim i As Integer, max As Integer If k = 1 Then max = 1 Else max = st.ss(1) For i = 2 To k - 1 If max < st.ss(i) Then max = st.ss(i) End If Next End If If st.ss(k) < max + 1 And st.ss(k) < k Then am_suc = True st.ss(k) = st.ss(k) + 1 Else am_suc = False End IfEnd Sub52. Subrutina back pentru colorarea hrilorSub back_col() Dim k As Integer k = 1 init k, st While k > 0 Do succesor_col am_suc, st, k If am_suc = True Then valid_col ev, st, k End If Loop Until (Not am_suc) Or (am_suc And ev) If am_suc Then If solutie(k) Then tipar_col Else k = k + 1 init k, st End If Else k = k - 1 End If WendEnd SubPublic s As String53. Funcia pentru a verifica dac un numr natural n este prim sau nuFunction prim(n As Integer) As Boolean b = True For i = 2 To Int(Sqr(n)) If n Mod i = 0 Then b = False i = Int(Sqr(n)) End If Next prim = bEnd Function54. Programul principal pentru inversarea unui numr natural n Sub buton1_Click() Dim n As Integer, ninv As Integer, n1 As Integer, sir As String Do n = InputBox(" n = ", y) Loop Until n > 0 n1 = n ninv = 0 sir = "" While n 0 sir = sir + LTrim(RTrim(Str$(n Mod 10))) ninv = ninv * 10 + n Mod 10 n = Int(n / 10) Wend MsgBox " numarul initial este : " + Str$(n1) + " numarul inversat este: " + sirEnd Sub55. Algoritmul lui Euclid pentru calcularea CMMDC a dou numere naturale pozitivePrivate Sub Buton10_Click() Dim a As Integer, b As Integer, c As Integer Do a = InputBox("a = ", y) b = InputBox("b = ", y) a1 = a b1 = b Loop Until a > 0 And b > 0 And a > b c = euclid2(a, b) If c = 1 Then MsgBox " nr. sunt prime intre ele (" + Str$(a1) + "," + Str$(b1) + ")" Else MsgBox "Cmmdc (" + Str$(a1) + "," + Str$(b1) + ")=" + Str$(euclid2(a, b)) End IfEnd Sub56. Sortarea unui sir cu n componente utiliznd metoda bulelor Private Sub Buton11_Click() Dim n As Integer, a As vector cit_n "n = ", n cit_date "a", n, a tipar "vectorul initial a este ", n, a bule n, a tipar "vectorul a sortat este : ", n, aEnd Sub57. Subrutina pentru sortarea prin metoda bulelorSub bule(n As Integer, a As vector) Do k = 0 For i = 1 To n - 1 If a.v(i) > a.v(i + 1) Then x = a.v(i) a.v(i) = a.v(i + 1) a.v(i + 1) = x k = 1 End If Next Loop Until k = 0End Sub58. Sortarea unui sir cu n componente utiliznd metoda seleciei directePrivate Sub Buton12_Click() Dim n As Integer, a As vector cit_n "n = ", n cit_date "a", n, a tipar "vectorul initial a este ", n, a selectie n, a tipar "vectorul a sortat este : ", n, aEnd Sub59. Subrutina pentru sortarea prin metoda seleciei directeSub selectie(n As Integer, a As vector) For i = 1 To n - 1 min = a.v(i) k = i For j = i + 1 To n If min > a.v(j) Then min = a.v(j) k = j End If Next If k i Then x = a.v(i) a.v(i) = a.v(k) a.v(k) = x End If NextEnd Sub60. Sortarea unui sir cu n componente utiliznd metoda prin numrarePrivate Sub Buton14_Click() Dim n As Integer, a As vector cit_n "n = ", n cit_date "a", n, a tipar "vectorul initial a este ", n, a numarare n, a tipar "vectorul a sortat este : ", n, aEnd Sub61. Suma cifrelor unui numr natural dat nSub buton2_Click() Dim n As Integer, s As Long, n1 As Integer Do n = InputBox(" n = ", y) Loop Until n > 0 n1 = n s = 0 While n 0 s = s + n Mod 10 n = Int(n / 10) Wend MsgBox " suma cifrelor numarului n = " + Str$(n1) + " este : " + Str$(s)End Sub62. Verificarea unui numar natural n daca este prim sau nuSub buton3_Click() Dim n As Integer, s As Long, n1 As Integer Do n = InputBox(" n = ", y) Loop Until n > 0 n1 = n b = True For i = 2 To Int(Sqr(n)) If n Mod i = 0 Then b = False i = Int(Sqr(n)) End If Next If b = True Then MsgBox "numarul n = " + Str$(n) + " este prim" Else MsgBox "numarul n = " + Str$(n) + " nu este prim" End IfEnd Sub63. Determinarea numerelor prime mai mici sau egale cu n utiliznd metoda direct Sub buton4_Click() Dim n As Integer, s As Long, n1 As Integer, i As Integer Do n = InputBox(" n = ", y) Loop Until n > 0 n1 = n If n = 2 Then MsgBox "numerele prime sunt : 2" Else sir = "2," i = 3 While i 0 For i = 1 To n a.v(i) = i Next For i = 2 To Int(Sqr(n)) If a.v(i) 0 Then j = 2 * i While j 0 i = 2 n1 = n l = 0 sir = "" Do fm = 0 While n Mod i = 0 fm = fm + 1 l = 1 n = Int(n / i) Wend If fm 0 Then sir = sir + Str$(i) + "^" + Str$(fm) + "*" End If i = i + 1 Loop Until n = 1 If l = 0 Then sir = Str$(n) + "^1" End If MsgBox Str$(n1) + "=" + sirEnd Sub66. Scrierea unui numr ca suma a dou cuburiSub buton7_Click() Dim n As Integer, a As vector, sir As String, n1 As Integer Do n = InputBox(" n = ", y) Loop Until n > 0 n1 = n For n = 1 To n1 Max = Int(n / 2) nr = 0 For i = 1 To Max For j = i To Max If i * i * i + j * j * j = n Then If nr = 0 Then i1 = i j1 = j Else i2 = i j2 = j End If nr = nr + 1 End If Next Next If nr > 1 Then MsgBox Str$(n) + "=" + Str$(i1) + "^" + Str$(j1) + "+" + Str$(i2) + "^" + Str$(j2) End If NextEnd Sub67. CMMDC a dou numere utiliznd recursivitateaSub buton8_Click() Dim a As Integer, b As Integer, c As Integer Do a = InputBox("a = ", y) b = InputBox("b = ", y) a1 = a b1 = b Loop Until a > 0 And b > 0 And a > b c = euclid(a, b) If c = 1 Then MsgBox " nr. sunt prime intre ele (" + Str$(a1) + "," + Str$(b1) + ")" Else MsgBox "Cmmdc (" + Str$(a1) + "," + Str$(b1) + ")=" + Str$(euclid(a, b)) End IfEnd Sub68. Funcia euclidFunction euclid(a As Integer, b As Integer) As Integer Dim r As Integer Do r = a Mod b MsgBox r a = b b = r Loop Until Not (r = 0 And r = 1) If r = 1 Then euclid = 1 Else euclid = a End IfEnd Function69. CMMDC a dou numere utiliznd scderi repetatePrivate Sub Buton9_Click() Dim a As Integer, b As Integer, c As Integer Do a = InputBox("a = ", y) b = InputBox("b = ", y) a1 = a b1 = b Loop Until a > 0 And b > 0 And a > b c = euclid1(a, b) If c = 1 Then MsgBox " nr. sunt prime intre ele (" + Str$(a1) + "," + Str$(b1) + ")" Else MsgBox "Cmmdc (" + Str$(a1) + "," + Str$(b1) + ")=" + Str$(euclid1(a, b)) End IfEnd Sub70. Funcia Euclid utiliznd scderi repetateFunction euclid1(a As Integer, b As Integer) As Integer If a > b Then euclid1 = euclid1(a - b, b) Else If a < b Then euclid1 = euclid1(a, b - a) Else euclid1 = a End If End IfEnd Function71. Funcia Euclid utiliznd scderi repetateFunction euclid2(a As Integer, b As Integer) As Integer If b = 0 Then euclid2 = a Else euclid2 = euclid2(b, a Mod b) End IfEnd Function72. x ^ y utiliznd un numr minim de nmuliriSub Button15_Click() Dim x As Integer, y As Integer, z As Integer, t As String, bb As vector Dim xx As Integer Do x = InputBox("a=", ib_title) y = InputBox("b=", ib_title) Loop Until (x > 0) And (y > 0) And (x >= y) baza1 x, y, bb, xx t = "" MsgBox "n = " + Str$(xx) For z = xx To 1 Step -1 t = t + Str$(bb.v(z)) Next MsgBox tEnd Sub73. Verific dac un numr natural este palindrome sau nuSub Button16_Click() Dim n As Long, m As Long Do n = InputBox("n=", ib_title) Loop Until (n > 0) m = n If palindrom(n) = True Then MsgBox "n=" + Str$(m) + " este plaindrom" Else MsgBox "n=" + Str$(m) + " nu este plaindrom" End IfEnd Sub74. Baza la exponent Sub Button17_Click() Dim x As Double, y As Byte, z As Double, t As Byte Do x = InputBox("baza=", ib_title) y = InputBox("exponent=", ib_title) Loop Until (x > 0) And (y > 0) z = putere(x, y, t) MsgBox Str$(z) + " " + Str$(t - 1)End Sub75. QuicksortSub Button18_Click() Dim n As Integer, a As vector cit_n "n = ", n cit_date "a", n, a 'MsgBox "Sirul a este" tipar "Sirul a este", n, a divimp 1, n, a 'MsgBox "Sirul a sortat este" tipar "Sirul a sortat este", n, aEnd Sub76. Minimul dintr-un ir de numere utiliznd divide et imperaSub Button19_Click() Dim n As Integer, a As vector cit_n "n=", n cit_date "a", n, a 'MsgBox "Sirul a este" tipar "sirul dat este ", n, a MsgBox "minimul in Sirul a este" + Str$(minim(1, n))End Sub77. Turnurile din HanoiSub Button20_Click() Dim n As Integer, a As sir, b As sir, c As sir d = "" a.s = "A" b.s = "B" c.s = "C" n = InputBox("n=", ib_title) hanoi n, a, b, c MsgBox dEnd Sub78. Subrutina Hanoi Sub hanoi(n As Integer, a As sir, b As sir, c As sir) If n = 1 Then d = d + "(" + a.s + "->" + b.s + ")," Else hanoi n - 1, a, c, b d = d + "(" + a.s + "->" + b.s + ")," hanoi n - 1, c, b, a End IfEnd Sub79. Subrutina back pentru permutriSub back_perm() Dim k As Integer k = 1 init k, st While k > 0 Do succesor am_suc, st, k If am_suc = True Then valid1 ev, st, k End If Loop Until (Not am_suc) Or (am_suc And ev) If am_suc Then If solutie(k) Then tipar_r Else k = k + 1 init k, st End If Else k = k - 1 End If WendEnd Sub80. Calculul sumei 1-1,1-1-1,.,1-1-1-1-1-1-1.-1Private Sub Buttton3_Click() Dim n As Integer, ss As String cit_n "n = ", n ss = "" i = 0 j = 1 While (i < n) ss = ss + " 1" i = i + 1 k = 1 While k