Reprezentarea algoritmilor cu ajutorul limbajului algoritmic

Reprezentarea algoritmilor cu ajutorul limbajului algoritmic

Limbajul algoritmic numit si pseudocod constituie un mijloc de reprezentare naturala a algoritmilor.

Datele cu care se lucreaza sunt de tipurile: intreg, real, logic, sir de caractere. Asupra datelor se fac operatiile cunoscute (adunarea, scaderea, inmultirea, impartirea, exponentierea, comparatii), iar natura rezultatului este in functie de tipul datelor cu care se opereaza. De asemenea, datele pot fi organizate in tablouri, stive, cozi sau ansamble. Tablourile pot fi unidimensionale (vectori), bidimensionale (matrice, masiv) sau n-dimensionale.

Operatiile cu stive, cozi, ansamble sunt: extragerea unui element x (x L), introducerea unui element x (x L) si verificarea daca stiva, coada sau ansamblul este vid (L = ).

Prin program in limbaj algoritmic se intelege o succesiune de instructiuni ale limbajului.

Instructiunile limbajului algoritmic pot fi scrise liber in sensul ca o instructiune se poate scrie pe mai multe randuri, iar un rand poate contine mai multe instructiuni. Instructiunile se separa intre ele prin caracterul punct si virgula. Aceste instructiuni, cu exceptia celei de atribuire, sunt identificate prin anumite cuvinte, numite cuvinte cheie. Pentru a marca cuvintele cheie le vom scrie cu litere mari de tipar. Deosebim instructiuni declarative si efective.

O instructiune declarativa este formata dintr-un cuvant cheie, urmat de un sir de variabile separate prin caracterul virgula. Cuvintele cheie sunt:

INTEGER pentru date de tip intreg;

REAL    pentru date de tip real;

BOOLEAN pentru date de tip logic;

CHAR    pentru date de tip caracter;

ARRAY    pentru structura de tablou;

STACK    pentru structura de stiva;

QUEUE    pentru structura de coada;

HEAP    pentru structura de ansamblu.

Instructiunile efective corespund structurilor fundamentale din programarea structurata.

Instructiunea de pornire are forma :

PROGRAM id;

unde id este un identificator (sir de caractere) care da numele programului. Aceasta instructiune corespunde instructiunii START de la scheme logice.

Instructiunea de citire are forma:

READ v₁, ., v_n;

unde v₁, , v_n sunt variabile.

Instructiunea de atribuire are forma:

v := ex;

unde v este o variabila, iar ex este o expresie. Din aceasta categorie fac parte si operatiile de scoatere sau introducere a unui element din sau in stiva, coada sau ansamblu.

Instructiunea de scriere are forma:

WRITE v₁, ., v_n;

unde v₁,.,v_n sunt variabile.

Instructiunile de citire, atribuire, scriere au aceeasi semnificatie cu cea a instructiunilor de citire, atribuire, scriere prezentate la descrierea schemelor logice.

Instructiunea alternativa generalizata are forma:

CASE OF

p₁ : s₁

p_n : s_n

ENDCASE;

unde s₁, . , s_n sunt secvente de instructiuni, iar p₁, . , p_n sunt predicate satisfacand conditiile: p₁ p_n = 1, p_i p_j = 0, i j.

Instructiunea alternativa generalizata codifica structura alternativa generalizata. Aceasta instructiune poate avea si forma :

CASE OF

p₁ : s₁

p_n : s_n

ELSE s₀   

ENDCASE;

Instructiunea alternativa are forma:

IF p

THEN

s₁

[ELSE

s₂]

ENDIF;

unde p este un predicat iar s₁, s₂ sunt secvente de instructiuni. Aceasta instructiune codifica structura alternativa pentru n = 2. Daca s₂ este secventa vida atunci ramura ELSE lipseste.

Instructiunea repetitiva conditionata anterior are una din formele:

WHILE p DO UNTIL p DO

s    s

ENDWHILE;    ENDUNTIL;

unde p este un predicat, iar s este o secventa de instructiuni. Aceste instructiuni codifica structurile repetitive conditionate anterior.

Instructiunea repetitiva conditionata posterior are una din formele:

REPEAT    DO

s s

UNTIL p;    ENDDO;

unde p este un predicat, iar s este o secventa de instructiuni. Sa observam ca a doua forma nu reprezinta neaparat un ciclu infinit deoarece secventa de instructiuni s poate contine o instructiune de oprire sau o instructiune de iesire din ciclu. Instructiunea REPEAT UNTIL codifica structura repetitiva conditionata posterior.

Instructiunea repetitiva cu numarul de repetari cunoscut, are forma:

FOR v := ex₁, ex₂ [, ex₃]

s

ENDFOR;

unde s este o secventa de instructiuni, v este o variabila numerica, iar ex₁, ex₂, ex₃ sunt expresii aritmetice. ex₁ reprezinta expresia de initializare, ex₂ conditia de continuare, iar ex₃ pasul iteratiei. Fie vex_i valoarea expresiei ex_i; vex₃ trebuie sa fie diferit de 0; daca vex₃ = 1, atunci ex₃ poate fi omisa. Instructiunea FOR codifica structura repetitiva care descrie cicluri cu un numar cunoscut de repetari.

Instructiunea de iesire din ciclu are forma :

EXIT;

Efectul instructiunii consta in trecerea la executia primei instructiuni care urmeaza celui mai interior ciclu care o contine.

Instructiunea de repetare a ciclului are forma:

CYCLE;

Efectul instructiunii consta in reluarea parcurgerii celui mai interior ciclu care o contine.

Instructiunea de oprire este de forma:

STOP.

si corespunde instructiunii STOP de la scheme logice.

Instructiunea de apel de subprogram are forma:

CALL id [(pa₁, , pa_n)];

unde id este identificatorul care da numele subprogramului, iar pa₁, , pa_n sunt parametrii actuali. Lista parametrilor este optionala.

Exemplul 2.5

Sa se calculeze mediile aritmetica, geometrica si armonica a trei numere reale pozitive.

PROGRAM CALCUL;

BEGIN

READ X, Y, Z;

S := X + Y + Z;

P := X * Y * Z;

S1 := 1 / X + 1 / Y + 1 / Z;

MA := S / 3;

MG := P^{1 /3};

MR := 3 / S1;

WRITE MA, MG, MR;

END.

Codul sursa al programului C corespunzator este prezentat in continuare:

#include<stdio.h>

#include<math.h>

void main()

Exemplul 2.6

Se dau trei numere A, B si C reprezentand coeficientii unei ecuatii de gradul 2. Sa se rezolve ecuatia si sa se afiseze rezultatele obtinute.

PROGRAM ECUATIE_GRAD_2;

BEGIN

READ A, B, C;

IF A = 0 THEN

IF B = 0 THEN

IF C = 0 THEN

WRITE "Ecuatia are o infinitate de solutii"

ELSE

WRITE "Ecuatia nu are nici o solutie"

ENDIF;

ELSE

BEGIN

X := -C / B;

WRITE X;

END;

ENDIF;

ELSE

BEGIN

D := B² - 4 * A * C

IF D < 0 THEN

WRITE "Ecuatia nu are solutii reale"

ELSE

IF D = 0 THEN

BEGIN

X := -B / (2 * A)

WRITE X;

END;

ELSE

BEGIN

X1 := (-B - D^1/2) / (2*A);

X2 := (-B + D^1/2) / (2*A);

WRITE X1, X2;

END;

ENDIF;

ENDIF;

END;

ENDIF

END.

Codul sursa in limbajul C pentru acest program este urmatorul:

#include<stdio.h>

#include<math.h>

void main()

}

Exemplul 2.7

Se da o matrice A cu m linii si n coloane. Sa se afiseze cate elemente nule are fiecare linie a matricei.

PROGRAM NUMARA;

BEGIN

READ M, N, A_I,J, 1 ≤ I ≤ M, 1 ≤ J ≤ N;

FOR I := 1, I ≤ M

BEGIN

L := 0;

FOR J := 1 TO N DO

IF A_I,J = 0 THEN

L := L + 1

ENDIF;

ENDFOR;

WRITE L;

END;

ENDFOR;

END.

Programul corespunzator este:

#include<stdio.h>

void main()

for(i=1;i<=m;i++)

Exemplul 2.8

Se da un sir A cu n elemente. Sa se elimine elementele nule din sir.

PROGRAM ELIMINARE;

BEGIN

READ N, A_I ,1 ≤ I ≤ N;

I := 1;

WHILE I ≤ N DO

IF A_I = 0 THEN

FOR J := I TO N-1 DO

A_J := A_J+1;

ENDFOR;

N := N - 1;

I := I - 1;

ENDIF

I := I + 1;

ENDWHILE;

WRITE A

END.

Programul care elimina numerele nule dintr-un sir arata astfel:

#include<stdio.h>

void main()

i=1;

while (i<=n)

i++;

}

printf('Elementele noului sir: ');

for(i=1;i<=n;i++)

printf('%d ',a[i]);

Exemplul 2.9

Se da un sir A cu n elemente. Sa se ordoneze sirul A folosind metoda bulelor.

PROGRAM ORDONARE;

BEGIN

READ N, A_I ,1 ≤ I ≤ N;

REPEAT

ORDONAT := TRUE;

FOR I := 1 TO N DO

IF A_I > A_{I + 1} THEN

AUX := A_I;

A_I := A_I+1;

A_{I + 1} := AUX;

ORDONAT := FALSE;

ENDIF

ENDFOR;

UNTIL ORDONAT = TRUE;

END.

Problema sortarii

Problema sortarii consta in a ordona crescator elementele vectorului a=(a(1), , a(n)).

Algoritmi de sortare:

I. Algoritmi clasici

Sortarea prin metoda bulelor (BubbleSort)

Sortarea prin selectie (SelectSort)

Sortarea prin insertie (InsertSort)

Sortarea clasica prin numarare (ClassicCountSort)

II. Algoritmi imbunatatiti

Sortarea prin interclasare (MergeSort)

Sortarea rapida (QuickSort)

Sortarea imbunatatita prin numarare (ImproveCountSort)

Sortare prin ansamble (HeapSort)

I Algoritmi clasici

1. Sortarea prin metoda bulelor

Algoritmul de sortare prin metoda bulelor numit si algoritmul de sortare prin interschimbare consta in interschimbarea lui a(i) cu a(i+1) daca a(i)>a(i+1); sortarea se termina cand pornind cu perechea (a(1), a(2)) si terminand cu perechea (a(n-1), a(n)) nu s-a efectuat nici o schimbare.

PROGRAM SMB;

BEGIN

READ N, A_I, 1 ≤ I ≤ N;

REPEAT

S:=0;

FOR I:=1 TO N-1 DO

BEGIN

IF A_I>A_I+1

THEN BEGIN

X:=A_I; A_I:=A_I+1;

A_I+1:=X; S:=S+1;

END;

(13) END;

(14) UNTIL S=0;

(15) WRITE A_I, 1 ≤ I ≤ N;

(16)END.

Propozitia 2.1

Algoritmul de sortare prin metoda bulelor are complexitatea O(n²).

Demonstratie

Instructiunea REPEAT se executa de cel mult n ori. Instructiunea FOR, inclusa in instructiunea REPEAT, se executa la fiecare executie a instructiunii REPEAT de n-1 ori. Deci algoritmul are complexitatea O(n²).

Programul corespunzator in C este urmatorul:

#include<stdio.h>

void main()

do

while(!ordonat);

printf('Sirul ordonat este: ');

for(i=1;i<=n;i++)

printf('%d ',a[i]);

2. Sortarea prin selectie

Algoritmul de sortare prin selectie consta in a determina a(j)= min si se efectueaza interschimbarea a(i) a(j), pentru i=1, , n-1.

PROGRAM SS;

BEGIN

READ N, A_I ,1 ≤ I ≤ N;

FOR I:=1 TO N-1 DO

BEGIN

M:=A_I; K:=I;

FOR J:=1 TO N-1 DO

BEGIN

IF M>A_J+1

THEN BEGIN

M:=A_J+1; K:=J+1;

END;

END;

A_K:=A_I; A_I:=M;

END;

WRITE A_I, 1 ≤ I ≤ N;

(17)END.

Propozitia 2.2

Algoritmul de sortare prin selectie are complexitatea O(n²).

Demonstratie

Prima instructiune FOR se executa de n-1 ori. A doua instructiune FOR, inclusa in prima instructiune FOR, se executa de cel mult n-1 ori. Deci algoritmul are complexitatea O(n²).

Programul corespunzator in C este urmatorul:

#include<stdio.h>

void afisare(int a[20], int n)

void selectie(int a[20], int n)

a[k]=a[i];

a[i]=m;

void main()

selectie(a,n);

afisare(a,n);

3. Sortarea prin insertie

Algoritmul de sortare prin insertie consta in a considera pe rand fiecare element a(i) al sirului si se insereaza in subsirul ordonat a(1), , a(i-1) creat din primele i-1 elemente.

PROGRAM SI;

BEGIN

READ N, A_I, 1 ≤ I ≤ N;

FOR I:=2 TO N DO

BEGIN

X:=A_I; J:=I-1;

WHILE X<A_J AND J>0 DO

BEGIN

A_J+1:=A_J; J:=J-1;

END;

A_J+1:=X;

END;

WRITE A_I, 1 ≤ I ≤ N;

(14)END.

Propozitia 2.3

Algoritmul de sortare prin insertie are complexitatea O(n²).

Demonstratie

Instructiunea FOR se executa de n-1 ori.La fiecare iteratie a acestei instructiuni, instructiunea WHILE se executa de cel mult n-1 ori. Deci algoritmul are complexitatea O(n²).

Programul corespunzator in C este urmatorul:

#include<stdio.h>

void afisare(int a[20], int n)

void insertie(int a[20], int n)

a[j+1]=x;

void main()

insertie(a,n);

afisare(a,n);

4. Sortarea clasica prin numarare

Presupunem ca elementele vectorului a=(a(1), , a(n)) sunt distincte. Algoritmul de sortare clasica prin numarare consta in a determina numarul k(i) al elementelor mai mici decat a(i), i=1, , n si a crea un vector sortat b cu ajutorul numerelor k(i), i=1, , n.

PROGRAM SCN;

BEGIN

READ N, A_I, 1 ≤ I ≤ N;

FOR I:=1 TO N DO

K_I:=0;

FOR I:=2 TO N DO

FOR J:=1 TO I-1 DO

IF A_J<A_I

THEN K_I:=K_I+1

ELSE K_J:=K_J+1

(11) FOR I:=1 TO N DO

(12) B_K(I)+1:=A_I;

(13) WRITE B_I, 1 ≤ I ≤ N;

(14)END.

Propozitia 2.4

Algoritmul de sortare clasica prin numarare are complexitatea O(n²).

Demonstratie

Prima instructiune FOR se executa de n-1 ori. La fiecare iteratie a acestei instructiuni a doua instructiune FOR se executa de cel mult n-1 ori. Deci algoritmul are complexitatea O(n²).

Programul corespunzator in C este urmatorul:

#include<stdio.h>

void afisare(int a[20], int n)

void numarare(int a[20], int n)

void main()

numarare(a,n);

afisare(a,n);

5. Problema interclasarii

Problema interclasarii consta in a obtine vectorul sortat crescator c=(c(1), , c(m+n)) din vectorii sortati crescator a=(a(1), , a(m)) si b=(b(1), , b(n)).

PROGRAM INT;

BEGIN

READ M,N, A_I, 1 ≤ I ≤ M, B_J, 1 ≤ J ≤ N;

I:=1; J:=1; K:=0;

WHILE (I≤M) AND (J≤N) DO

BEGIN

K:=K+1;

IF A_I<B_J

THEN BEGIN C_K:=A_I; I:=I+1; END

ELSE BEGIN C_K:=B_J; J:=J+1; END;

END;

IF I≤M

THEN FOR L:=1 TO M DO

BEGIN K:=K+1; C_K:=A_L; END

ELSE FOR L:=J TO N DO

BEGIN K:=K+1; C_K:=B_L; END;

WRITE C_K, 1 ≤ I ≤ M+N;

END.

Propozitia 2.5

Algoritmul de interclasare are complexitatea O(m+n).

Demonstratie

Instructiunea WHILE se executa de cel mult m+n-1 ori si instructiunea FOR se executa de cel mult m sau n ori. Deci algoritmul are complexitatea O(m+n).

Programul corespunzator in C este urmatorul:

#include<stdio.h>

void afisare(int a[20], int n)

void main()

printf('n=');

scanf('%d',&n);

for(i=1;i<=n;i++)

i=1;

j=1;

k=0;

while (i<=m && j<=n)

if(a[i]<=b[j])

c[++k]=a[i++];

else

c[++k]=b[j++];

if(i<=m)

for(l=i;l<=m;l++)

c[++k]=a[l];

else

for(l=j;l<=n;l++)

c[++k]=b[l];

afisare(c, k);