Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  


AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


Reprezentarea algoritmilor cu ajutorul limbajului algoritmic

c

+ Font mai mare | - Font mai mic





DOCUMENTE SIMILARE

Trimite pe Messenger
If-Else
Tipuri de date predefinite
Crearea obiectelor Delphi in timpul executiei
Bucle incuibate
Functii pentru gestiunea textelor
STRUCTURI DE DATE
Operatori logici pe biti
Modularizarea programelor
Cautare in tabele
Functii de prelucrare a sirurilor de caractere

TERMENI importanti pentru acest document

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 v1, …, vn;

unde v1, , vn 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 v1, …, vn;

unde v1,…,vn 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

p1 : s1

pn : sn

ENDCASE;

unde s1, … , sn sunt secvente de instructiuni, iar p1, … , pn sunt predicate satisfacand conditiile: p1 pn = 1, pi pj = 0, i j.

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

CASE OF

p1 : s1

pn : sn

ELSE s0   

ENDCASE;

Instructiunea alternativa are forma:

IF p

THEN

s1

[ELSE

s2]

ENDIF;

unde p este un predicat iar s1, s2 sunt secvente de instructiuni. Aceasta instructiune codifica structura alternativa pentru n = 2. Daca s2 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 := ex1, ex2 [, ex3]

s

ENDFOR;

unde s este o secventa de instructiuni, v este o variabila numerica, iar ex1, ex2, ex3 sunt expresii aritmetice. ex1 reprezinta expresia de initializare, ex2 conditia de continuare, iar ex3 pasul iteratiei. Fie vexi valoarea expresiei exi; vex3 trebuie sa fie diferit de 0; daca vex3 = 1, atunci ex3 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 [(pa1, , pan)];

unde id este identificatorul care da numele subprogramului, iar pa1, , pan 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 := P1 /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 := B2 – 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 – D1/2) / (2*A);

X2 := (–B + D1/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, AI,J, 1 ≤ I ≤ M, 1 ≤ J ≤ N;

FOR I := 1, I ≤ M

BEGIN

L := 0;

FOR J := 1 TO N DO

IF AI,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, AI ,1 ≤ I ≤ N;

I := 1;

WHILE I ≤ N DO

IF AI = 0 THEN

FOR J := I TO N–1 DO

AJ := AJ+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, AI ,1 ≤ I ≤ N;

REPEAT

ORDONAT := TRUE;

FOR I := 1 TO N DO

IF AI > AI + 1 THEN

AUX := AI;

AI := AI+1;

AI + 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, AI, 1 ≤ I ≤ N;

REPEAT

S:=0;

FOR I:=1 TO N-1 DO

BEGIN

IF AI>AI+1

THEN BEGIN

X:=AI; AI:=AI+1;

AI+1:=X; S:=S+1;

END;

(13) END;

(14) UNTIL S=0;

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

(16)END.

Propozitia 2.1

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

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(n2).

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, AI ,1 ≤ I ≤ N;

FOR I:=1 TO N-1 DO

BEGIN

M:=AI; K:=I;

FOR J:=1 TO N-1 DO

BEGIN

IF M>AJ+1

THEN BEGIN

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

END;

END;

AK:=AI; AI:=M;

END;

WRITE AI, 1 ≤ I ≤ N;

(17)END.

Propozitia 2.2

Algoritmul de sortare prin selectie are complexitatea O(n2).

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(n2).

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, AI, 1 ≤ I ≤ N;

FOR I:=2 TO N DO

BEGIN

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

WHILE X<AJ AND J>0 DO

BEGIN

AJ+1:=AJ; J:=J-1;

END;

AJ+1:=X;

END;

WRITE AI, 1 ≤ I ≤ N;

(14)END.

Propozitia 2.3

Algoritmul de sortare prin insertie are complexitatea O(n2).

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(n2).

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, AI, 1 ≤ I ≤ N;

FOR I:=1 TO N DO

KI:=0;

FOR I:=2 TO N DO

FOR J:=1 TO I-1 DO

IF AJ<AI

THEN KI:=KI+1

ELSE KJ:=KJ+1

(11) FOR I:=1 TO N DO

(12) BK(I)+1:=AI;

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

(14)END.

Propozitia 2.4

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

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(n2).

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, AI, 1 ≤ I ≤ M, BJ, 1 ≤ J ≤ N;

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

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

BEGIN

K:=K+1;

IF AI<BJ

THEN BEGIN CK:=AI; I:=I+1; END

ELSE BEGIN CK:=BJ; J:=J+1; END;

END;

IF I≤M

THEN FOR L:=1 TO M DO

BEGIN K:=K+1; CK:=AL; END

ELSE FOR L:=J TO N DO

BEGIN K:=K+1; CK:=BL; END;

WRITE CK, 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);






Politica de confidentialitate



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 703
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2021 . All rights reserved

Distribuie URL

Adauga cod HTML in site