ALGORITMI DE INSERARE SI DE

STERGERE IN VECTORI

CE ESTE UN ALGORITM?

Un algoritm înseamna în matematica si informatica o metoda sau o procedura de calcul, alcatuita din pasii elementari necesari pentru rezolvarea unei probleme sau categorii de probleme. De obicei algoritmii se implementeaza în mod concret prin programarea adecvata a unui calculator, sau a mai multora. Din diverse motive exista si algoritmi înca neimplementati, teoretici.

Algoritmul este notiunea fundamentala a informaticii. Totul este construit în jurul algoritmilor.

INPORTANTA OPTIMIZARII Ideal este ca, pentru o problema data, sa gasim

mai multi algoritmi,iar apoi sa-l alegem dintre acestia pe cel optim. Care este insa criteriul de comparatie? Eficienta unui algoritm poate fi exprimata in mai multe moduri.Putem analiza a posteriori comportarea algoritmilor dupa implementare ,prin rularea pe calculator a unor cazuri diferite sau,putem analiza a priori algoritmul,inaintea programarii lui ,prim determinarea cantitativa a resurselor necesare.

ALGORITM PENTRU STERGEREA UNUI ELEMENT DINTR-UN VECTOR

Algoritmul pentru stergerea dintr-un vector

a elementului K inseamna deplasarea elementelor vectorului, incepand cu indicele K+1 , cu o pozitie spre stanga .

Lungime logica a vectorului se va micsora cu un element si va fi n-1.

STERGEREA MULTIPLA

!!! sa se stearga elementul de pe locul k al unui vector cu n numere intregi.

OBS!!!Stergerea se face prin deplasare tuturor elementelor aflate pe poziti de la k+1 la n, cu un loc catre stanga si micsorarea lungimi efective a vectorului

for(i=k+1;i<=n;i++) v[i-1]=v[i]; n--; } else i++;

int i,n,k,a[10]; cout<<"n="; cin>>n; cout<<"k="; cin>>k; ...........// se creeaza vectorul for(i=k;i<n-1;i++) a[i]=a[i+1]; // se sterge elementul //se afiseaza vectorul dupa stregerea elementului for(i=0;i<n-1;i++) cout<<a[i]<<“ “;

ex2)sa se stearga toate numerele prime.

ALGORIT PENTRU INSERAREA UNUI ELEMENT INTR-UN VECTOR

Algoritmul pentru inserarea intr-un vector a unui element in pozitia indicelui k inseamna deplasarea elementelor vectorului,incepand cu indicele k+1, cu o pozitie spre dreapta si atribuirea noii valori elementului cu indicele k. Lungimea logica a vectorului se va mari cu un element si va fi n+1 , cu conditia ca n+1 sa fie mai mic sau efal cu lungimea fizica a vectorului ,altfel ultimul element al vectorului se pierde

const int DIM=10 int i,n,k,x,a[DIM]; cout<<"n=" ; cin>>n; cout<<"k="; cin>>k' cout"x="; cin>>x; //x contine valoarea care se insereaza .......//se creeaza vectorul if(n+1<=DIM) for(i=n;i>k;i--) a[i]=a[i-1]; a[k]=x; for(i=0;i<n+1;i++) cout<<a[i]<<" "; else {for (i=n-1;i>k;i--) a[i]=a[i-1]; a[k]=x; for(i=0;i<n;i++) cout<<a[i]<<" ";

De retinut!

Mutarea catre dreapta a elementelor pentru a face loc celui care se insereaza trebuie sa inceapa de la sfarsit catre locul inserarii.

for(i=n;i>=k;i--) v[i+1]=v[i]; n++; v[k]=x;

INSERAREA MULTIPLA Folosind structura repetitiva WHILE ptr a putea diferentia cazul cand inseram

de cazul cand nu se face inserarea.

ex1) Sa se insereze intre oricare 2 nr. cu acelasi paritate media lor aritmetica.

... i=1; while(i<n) if(v[i]%2==v[i+1]%2) {for(j=n;j>=i+1;j--) v[j+1]=v[j]; n++; v[i+1]=(v[i]+v[i+2])/2; i=i+2; } else i++;

ex2)Inserati in fata fiecarui numar negativ modulu sau.

#include<iostream.h> void main() {int v[100][100]n,i cin>>n; for(i=1;i<=n;i++) cin>>v[i]; i=1; while(i<=n) if(v[i]<0) {x=abs(v[i]); for(j=n;j>=i;j++) v[j+1]=v[j]; n++; v[i]=x; i=i+2; } else i++; for(i=1;i<=n;i++) cout<<v[i]<<" "; cout<<endl;}

Sortarea prin inserare Sortarea prin inserare consta în urmatoarele:

Fie secventa a0 < a1 < a2 ... < aj-1.

Inserarea elementului aj în aceasta secventa consta în compararea lui aj cu aj-1, aj-2 ... pâna când se ajunge la ai < aj; se insereaza aj dupa ai, cu mentiunea ca în prealabil elementele aj-1, aj-2, ..., ai+1 au fost deplasate spre dreapta cu o pozitie. Metoda care procedeaza întocmai se numeste inserare directa.

Metoda inserarii binare consta în cautarea binara a locului unde trebuie inserat elementul aj, având în vedere ca secventa a0, a1, ..., aj-1 este ordonata crescator.

Tot din categoria inserarii face parte si metoda shell. Pentru a explica metoda se introduce notiunea de h-sortare. Numim h-sortare, sortarea prin inserare directa a urmatoarelor secvente:

a0, ah, a2h, ....

a1, a1+h, a1+2h, ....

......

ah, a2h, a3h, ....

h este numit increment.

Metoda shell consta în alegerea unui numar de k incrementi

h1 > h2 > h3 > ... > hk = 1

si de a face o h1 - sortare, urmata de o h2 - sortare s. a. m. d., în final o 1 - sortare.

Performatele metodei sunt strâns legate de alegerea incrementilor.

În exemplul din paragraful 2.6., functia sort_inserare_directa reda algoritmul de inserare directa, iar functia shell_sort reda algoritmul metodei shell.

STUDIU DE CAZ

Scop: explicarea modului in care se aplica algoritmii pentru cautarea unui element intr-un vector , pentru stergerea unui element si pentru inserarea unui element intr-un vector .

Enuntul P1) Se citesc intr-un vector ,de la tastatura ,cel mult 50 de numere intregi .Sa se sterga primul element care are valoarea x (x se citeste de la tastatura ).

OBS!: Se va folosi algoritmul de cautare secventiala pentru a gasi pozitia primului element cu valoarea x , si apoi algoritmul de stergere din acea pozitie.

Enuntul problumei 2): Se citesc intr-un vector de la tastatura ,cel mult 50 de numere intregi. Sa se insereze elementul cu valoare y inainte de primul element carea are valuarea x(x si y se citesc de la tastatura).

OBS!: Se va folosi algoritmul de cautare secventiala pentru a gasi pozitia primului element cu valaorea x, si apoi algoritmul de inserare a valorii y in aceea pozitie.

BIBLIOGRAFIE

-cartea Informatica de Mariana Milosescu -cartea Informatica de Dana Lica -wikipedia -www.math.uaic.ro informaticasite.ro

PROIECT INTOCMIT DE:ILIE DENISA

CLS IX I1PROFESOR

INDRUMATORCONSTANTIN ADRIANA