Algoritmi - defitie si proprietati, tipuri - Pseudocod

Algoritmi - defitie si proprietati, tipuri

Definitie: Algoritmul este un set finit de pasi executabili, descrisi fara echivoc, care solutioneaza o clasa de probleme. Putem spune despre el ca este format dintr-o multime de instructiuni elementare, exprimate intr-un limbaj bine definit, interpretabile in mod unic si care, pornind de la o stare initiala, data, sunt executate intr-o ordine stabilita, permitand rezolvarea unei probleme in numar finit de pasi. Proprietatile sale sunt de fapt cerintele pe care trebuie sa le indeplineasca un algoritm si anume:

finitudinea (orice algoritm trebuie sa se termine dupa un numar finit de pasi sau in timp finit)

corectitudinea (fiecare pas al sau trebuie sa contina o operatie bine definita si posibila)

generalitatea orice algoritm trebuie sa rezolve toate problemele dintr-o clasa de probleme; sa poata fi aplicat pe mai multe seturi de date initiale aferente aceluiasi tip de problema)

unicitatea raspunsurilor (repetarea algoritmului in aceleasi conditii initiale trebuie sa conduca la aceeasi solutie)

claritatea algoritmul trebuie descris clar, fara ambiguitati; privita ca neambiguitate cere ca pasul urmator pasului curent trebuie sa fie unic definit)

optimalitatea (data de eficienta utilizarii resurselor temporale si de hard ; se refera la timpul de executie (in care sunt folosite resursele calculatorului: memorie, procesor) si la spatiul de memorie utilizat. Un algoritm este cu atat mai eficient cu cat spatiul de memorie utilizat este mai mic si numarul de operatii mai putine)

completitudinea - presupune tratarea cazurilor speciale (a exceptiilor) unei probleme

realism - realizabilitatea (orice algoritm trebuie sa poata fi codificat intr-un limbaj de programare ; fiecare pas al sau trebuie sa fie efectuabil)

Nerespectarea acestor caracteristici generale conduce la obtinerea de algoritmi neperformanti, posibil infiniti sau nerealizabili.

Obs1. Nu orice problema admite un algoritm de rezolvare.

2. Pseudocod

Notiuni fundamentale de algoritmi structurati folosind un pseudocod - sintaxa

Alocare de memorie pentru tipuri de variabile si constante

a)      Constante <numeconstanta>=valoare ex: pi=3.141

b)     Variabile <numevariabila> tip ex: a,b intreg ; c real

c)    Vectori (<numevector>(<numeindice>), plaja de valori) ex: (v(i),i=l,n)

d)     Matrici

(<numematrice>(<numeindice 1 ,numeindice2>,plaja valori indice2 ), plaja valori indice 1)

ex: ((a(ij)j=l,n),i=l,m)

e)    Liste de parametri (<numepar 1 >, <numepar2>,.. .,<numepark>) ex: (a,b,'Vasile',d)

f)     Comentariu /<text>   ex: /acesta este un comentariu

g)    Atribuirea <numevariabila>=rezultatul unei actiuni (expresii) ex: a=l; a=b+c

h)    Procedura de citire citeste(<lista de parametri>)

ex: citeste(a) citeste(b,c,d)

i)      Procedura de scriere scrie(<lista parametri>)

ex: scrie(a) ; scrie(b+c,d) ; scrie('Ion are ',p,'mere')

3. Structuri de control fundamentale:

Structura decizionala

daca conditie

atunci

secventa 1 de instructiuni

altfel

secventa2 de instructiuni

sfarsit daca

Actiunea acestei instructiuni este urmatoarea: se testeaza conditia care, daca este indeplinita impune executarea instructiunilor din secvental si apoi se preda controlul primei instructiuni dupa sfarsit daca, iar in cazul in care conditia nu este indeplinita se executa instructiunile din secventa2 si apoi se trece dupa sfarsit daca.

Structura decizionala poate avea si forma particulara in care doar o ramura a sa impune o actiune. In acest caz convenim ca ramura activa sa fie ramura atunci.

Forma instructiunii este:

daca conditie

atunci

secventa de instructiuni

sfarsit daca

Exemple: a = 0; b = 10 a = 4; b = -16

Sa se rezolve o ecuatie de tip ax+b=0 pentru a si b introduse de la tastatura.

Start

citeste(a,b)

daca a # 0 If a # 0

atunci Then

c=-b/a c=-b/a

scrie 'Solutia ecuatiei este ',c)  Print 'Solutia ecuatiei este ',c)

altfel Else

scrie ecuatia aleasa nu are solutie') Print ecuatia aleasa nu are solutie')

sfarsit daca End If

Stop

Putem sa scriem acest algoritm si sub forma

Start

citeste(a,b)

daca a=0  If a = 0

atunci Then

scrie ( ecuatia aleasa nu are solutie') Print ecuatia aleasa nu are solutie')

altfel Else

c= - b/a c=-b/a

scrie Solutia ecuatiei este ',c) Print Solutia ecuatiei este ',c)

sfarsit daca End If

Stop

Dar, cel mai des, coeficientul lui x introdus este diferit de zero si e preferabil ca ramura atunci sa contina actiunea cu cea mai mare probabilitate de a se executa, adica prima varianta este cea indicata.

Dandu-se trei numere sa se determine cel mai mic. a= 6; b = 2; c = 9

Start

citeste(a,b,c)

mini=a

daca b<mini If b < mini

atunci Then

mini=b mini = b

sfarsit daca End If

daca c<mini If c < mini

atunci Then

mini=c mini = c

sfarsit daca End If

scrie('cel mai mic numar introdus este ',mini) Print ('cel mai mic numar introdus este ',mini)

Stop

Structuri repetitive

Structura repetitiva cu test initial

cat timp conditie

secventa de instructiuni

sfarsit cat timp

Actiunea acestei instructiuni este urmatoarea. Se testeaza conditia. Daca este indeplinita se executa secventa de instructiuni si testeaza iar conditia. Daca conditia nu estre indeplinita se trece controlul primei instructiuni dupa sfarsit cat timp Sa observam ca aceasta instructiune poate sa nu se execute niciodata (daca conditia nu este indeplinita in faza initiala). Exista cerinta ca secventa de instructiuni sa contina o instructiune care sa aiba actiune asupra variabilei testata in conditie.

Exemple:

1. Algoritmul lui Euclid pentru determinarea celui mai mare divizor comun a doua numere intregi. (2500 de ani de perfectionare au transformat algoritmul prezentat ca o curiozitate in cel care urmeaza) a=28; b=16 a=27; b=90

Start

a,b intregi

citeste (a,b)

daca a>b If a > b

atunci Then

m=a m = a

n=b n = b

altfel Else

m=b m = b

n=a n = a

sfarsit daca End If

cat timp n# Do While n # 0

r = rest(m/n) r = rest (m / n)

m = n m = n

n = r n = r

sfarsit cat timp Exit Do

scrie 'CMMDC al numerelor ',a,' si ',b,' este ',m) Print ( 'CMMDC al numerelor ',a,' si ',b,' este ',m)

Stop Loop

Structura repetitiva cu test final

repeta

secventa de instructiuni

pana cand conditie

Actiunea acestei instructiuni este urmatoarea. Se executa secventa de instructiuni, se testeaza conditia. Daca conditia nu este indeplinita se repeta executia secventei de instructiuni si se testeaza iarasi conditia, iar daca conditia este indeplinita se preda controlul instructiunii de dupa pana cand.

Spre deosebire de secventa de instructiuni de sub cat timp secventa de sub repeta se executa cel putin o data indiferent de indeplinirea conditiei. Spre exemplificare vom da tot algoritmul de calcul al celui mai mare divizor comun.

Start

a,b intregi

citeste (a,b)

daca a>b  If a > b

atunci Then

m=a m = a

n=b n = b

altfel Else

m=b m = b

n=a n = a

sfarsit daca End If

repeta Do

r=rest(m/n) r = rest (m / n)

m=n m= n

n=r n = r

pana cand Loop Until

r = 0 r = 0

scrie (CMMDC al nr. ',a,' si ' ,b,' este ',m) Print (CMMDC al nr. ',a,' si ' ,b,' este ',m)

Stop

Observati diferenta dintre cele doua structuri repetitive, in prima, conditia este pusa la inceput si daca este indeplinita se executa secventa de instructiuni. In cea de a doua se executa secventa, se testeaza conditia si daca nu este indeplinita se repeta secventa. De asemenea, trebuie pusa in evidenta, in ambele cicluri, instructiunea care altereaza valoarea variabilei testata in conditie.

Stuctura repetitiva cu numar determinat de pasi

pentru <numeindex>, valoare initiala, valoare finala, [pas]

secventa de instructiuni

sfarsit pentru

Calculul produsului scalar a doi vectori U si V de dimensiune data n.

Start

citeste(n)

citeste((u(i),i,1,n),(v(i),i,l,n))

ps=0

pentru i,l,n

ps=ps+u(i)*v(i)

sfarsit pentru

scrie(ps)

Stop

2. Ordonarea crescatoare a unui sir

Start

citeste(n)

citeste((u(i),i,1,n))

pentru i,l,n-l

pentru j,2,n

daca u(j)>u(i)

atunci A=u(i)

u(i)=u(j)

u(j)=A

sfarsit daca

sfarsit pentru

Stop

Infatisarea lui Visual Basic

Toolbar-ul [1] care contine comenzile obisnuite ale unui mediu de programare: open (deschide un fisier); save (salveaza un fisier); new (un nou fisier), etc.

Toolbox-ul [2] care contine uneltele necesare pentru realizarea programelor. Sa nu uitam ca folosim un mediu de programare bazat pe obiecte. (Object Oriented Programming). De aici se adaoga Butonul de comanda -care declanseaza sau termina un proces

Project [3] listeaza formele, modulele de cod si fisierele control care constituie proiectul curent

Properties [4], care permite setarea proprietatilor pentru forma sau controlul selectat.

Atributele care definesc d.p.d.v. fizic forma sunt :

- 1: Name - numele de identificare a formei; implicit este:Form1; dupa atribuire devine cuvant rezervat; apelarea formei sau a unui atribut al acesteia se face cu referire la aceasta denumire; se sugereaza utilizatorilor denumiri sugestive (pt. apelarea, referirea la forma)
- 2: Proprietatile obiectului: Caption - contine textul afisat in bara de titlu a formei; este total independenta de valoarea proprirtatii Name; implicit, li se atribuie aceeasi valoare.
- 3: Valorile proprietatilor obiectului: Enable - valoarea True permite accesul la obiectele de pe forma si la actiunile specific formei, in timpul executiei
- 4: O mica descriere a proprietatilor obiectului: Windowstate - dimensiunea ferestrei in care este prezenta forma: normal, minimized si maximized ;

- 5: Left, Top,Width, Height - pozitia initiala a ferestrei

Principalele proprietati ale Butonului de comanda sunt :

- 1: Name - identificatorul butonului; implicit este:Command[n]; este independent de eticheta care apare pe buton; folosirea unui nume utilizator este indicata cu aceleasi restrictii ca si la forme; numele folosit devine cuvant rezervat si este folosit la referirea la atributele, metodele sau actiunile obiectului.
- 2: Caption - valoarea acestei proprietati este eticheta care apare pe buton (max 255 caractere)

- 3: Default - daca aceasta proprietate are valoare True, actiunea butonului de comanda se declanseaza la clic cu mouse-ul sau la tasta Enter ; implicit valoarea e False

- 4: Enable - permite activarea sau dezactivarea controlului; implicit, valoarea True (buton activ)

- 5: Visible - face controlul vizibil cu valoarea True, sau invizibil cu valoarea False ;

- 6: Left, Top,Width, Height - pozitia initiala a butonului si dimensiunile lui.

Structurile de control ale limbajului Visual Basic:

a)      Atribuirea

b)     Structuri decizionale: If si Select

Structura : If

If conditie Then If a>b Then

Secventa1  Print a

[Else  Else

Secventa2] Print b

End If End If

Obs : Ramura lui Else este optionala:

If conditie Then If a>0 Then

Secventa c=b/a

End If End If

Print c

If imbricate

If conditie principala Then If raspuns = "da" Then

Secventa principala Call complteazatest

ElseIf conditie1 Then  ElseIf amanare="da" Then

Secventa1 Call maitarziu

.. Else

[ElseIf conditie n Then Call renunt

Secventa n] End If

[Else

Secventa F]

End If

Sub schimbculfond (cul)

Structura Select Cul = Lcase (culoare)

Select Case <expresie de testat> Select Case cul

Case <lista de expresii1> Case "rosu

Secventa instructiuni1  text1.backcolor=VbRead

[Case <lista de expresii1> Case "verde"

Secventa instructiuni2  text1.backcolor=VbGreen

.

[Case Else Case Else

Secventa instructiuniF  MsgBox "alta culoare"

End Select End Select

End Sub

Atentie ! Diferenta dintre If cu ramuri multiple, care testeaza mai multe conditii, si Select Case care evalueaza o singura expresie si decide in raport cu valorile ei.

c)      Structuri repetitive : While, Do si For

While < conditie>

Secventa instructiuni (nu se executa niciodata, daca nu e indeplinita conditia)

Wend

Test initial direct (aceeasi functie cu instructiunea While)

Do While < conditie>

Secventa instructiuni

..

[Exit Do]

Secventa instructiuni

..

Loop

Test initial inversat

Do Until < conditie> Until - momentul initial al testarii

Secventa instructiuni (nu se executa niciodata, daca nu e indeplinita conditia)

..

[Exit Do] Exit Do - iesire fortata

Secventa instructiuni

..

Loop

Test final inversat

Do

Secventa instructiuni ( se executa macar o data, secventa de instructiuni)

Loop While < conditie> (se trece la instr. dupa Loop pt. cond. neindeplinita)

Test final direct

Do

Secventa instructiuni ( se executa o data, secventa de instructiuni si inca o data)

Loop Until < conditie> (apoi se trece la instr. dupa Loop pt. cond. neindeplinita)

For < contor>= <valoare initiala> To <valoare finala>

[Steep <valoare>]

Secventa instructiuni

Next

Operatori utilizati in VB:

Operatori aritmetici

Operatori de concatenare

Operatori de comparatie

Operatori logici