File

Report


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.



















!!! 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]<<“ “;

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]<<" ";





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;














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 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.



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.





-cartea Informatica de Mariana Milosescu
-cartea Informatica de Dana Lica
-wikipedia
-www.math.uaic.ro
informaticasite.ro

similar documents