Algoritmi de Cautare

Tema -Tehnici de cautare

Cautarea este una dintre cele mai des intalnite subprobleme in programare. Ea constituie o parte esentiala din numeroasele procese de prelucrare a datelor.

Cautarea este mult simplificata daca datele in care efectuam aceasta operatie sunt sortate (ordonate, aranjate) intr-o anumita ordine (cuvintele in ordine alfabetica, numerele in ordine

crescatoare sau descrescatoare).

Aceatsta este de doua tipuri :

1) Cautare secventiala :

a) intr-un sir oarecareb) intr-un sir ordonat

2) Cautare binara intr-un sir ordonat

1) Cautarea secventiala este unul dintre cei mai simplii algoritmi

studiati. El urmareste sa verifice apartenenta unui element la un sir de

elemente de aceeasi natura sau a unui numar la un sir de numere.

a) Cautarea secventiala se poate face intr-un vector (sir) cu elementele neordonate. Astfel complexitatea algoritmului este liniara :

Ex:

#include <iostream.h>

int main()

{

int n,v[100],i,gasit=0,x;

cout<<”Dati n : “;cin>>n;

cout<<”Dati nr pe care trebuie sa-l cautam: “;cin>>x;

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

{

cout<<”v["<<i+1<<"]=”;cin>>v[i];

}

i=1;

while ( (i<=n) && (!gasit) )

{

if (v[i]==x) gasit=1;

i++;

}

if (gasit) cout<<x<<” se afla in vector”;

else cout<<x<<” nu se afla in vector”;

return 0;

}

b) Cautarea secventiala intr-un tablou (sir) ordonat se face aproximativ la fel ca la un tablou neordonat, diferenta constand in faptul ca in tabloul ordonat cautarea se opreste atunci cand este intalnit un element cu o cheie mai mare.

Parcurgem sirul de la un capat la celalalt si se compara numarul de

cautat cu fiecare numar din sir. In cazul in care s-a gasit corespondenta(egalitate), un indicator flag este pozitionat. La sfarsitul parcurgerii sirului, indicatorul ne va arata daca numarul cautat apartine sau nu sirului.

Ex:

#include<iostream.h>

using namespace std;

int main()

{

int n,x,i,gasit,a[50];

cout<<”Dati numarul de elemente ale sirului : “; cin>>n;

cout<<”Dati numarul de cautat : “; cin>>x;

cout<<”Dati elementele sirului”<<endl;

gasit=0;

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

{

cout<<”a["<<i<<"]= “; cin>>a[i];

if (a[i]==x) gasit=1;

}

if (gasit==0)

cout<<”Numarul nu apartine sirului !”<<endl;

else cout<<”Numarul apartine sirului !”<<endl;

return 0;

}

2) Cautarea binara este un algoritm de cautare folosit pentru a gasi un element intr-un sir ordonat (tablou unidimensional/vector). Algoritmul functioneaza pe baza tehnicii divide et impera. Elementul cautat este “verificat” cu mijlocul vectorului. Daca elementul este egal cu mijlocul,cautarea se termina. Insa daca nu sunt egale, se compara valoarea mijlocului cu cea a elementului de cautat. Daca elementul este mai mare se continua cautarea de la mijlocul listei pana la sfarsit, iar daca este mai mic se continua cautarea de la inceput pana la mijloc.

Ex:

#include <iostream.h>

int main()

{

int mij,n=7,i,x=10,v[7]={4,5,8,10,20,45,76},st,dr,g=0;

st=0;

dr=n-1;

mij=(st+dr)/2;

while ( (st<dr) && (!g) )

{

if (v[mij]==x) {g=1;break;}

else if (v[mij]<x) st=mij+1;

else if (v[mij]>x) dr=mij-1;

}

if (g) cout<<x<<” se afla in vector pe pozitia “<<mij;

else cout<<x<<” nu se afla in vector”;

return 0;

}

Operatiile de cautare sunt executate frecvent de catre oameni in viata de zi cu zi, ca de exemplu cautarea unui cuvant in dictionar sau cautarea unui numar in cartea de telefon. Deschidem cartea la intamplare,dorim sa cautam numele “Popa Andrei “. Verificam daca numele se afla in prima partea a cartii sau in a doua parte. Continuam cautarea in portiunea respectiva, actiunea se repeta pana la gasirea numelui.

Exercitii

1) Se citesc de la tastatura “n” numere intregi compuse din cel mult 9 cifre.

Determinati si afisati minimul si maximul dintre numerele citite.

Explicatia exercitiului:

Pasul 1: Se citeste primul numar al secventei;

Pasul 2: Se atribuie minimului (maximului) valoarea de la pasul 1;

Pasul 3: Se citeste urmatorul numar al sceventei

Pasul 4: Se compara minimul (maximul) cu valoarea citita la pasul 3;

Pasul 5: Daca valoarea de la pasul 3 este mai mica decat minimul (mai mare decat maximul) atunci minimului (maximului) i se atribuie valoarea citita la pasul 3

Pasul 6: Daca mai sunt valori de comparat in secventa se reia pasul 3, iar daca nu mai sunt valori, minimul (maximul) este disponibil pentru afisare sau prelucrare.


int main()

{long i,n,nr,min,max;

cout<<”Numere citite=”;cin>>n;

cout<<”Numarul=”;cin>>nr;

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

{cout<<”Numarul=”;cin>>nr;

if(nr>max)

max=nr;

if(nr<min)

min=nr;

}

cout<<”\nMaximul citit=”<<max;

cout<<”\nMinimul citit=”<<min;

return 0;

}

n = numarul de numere ce se citesc de la tastatura;

nr = numarul ce se citeste in mod repetat;

min,max = minimul si maximul ce se determina.

2) Se citesc de la tastatura: numarul natural “n” (0<n<50) si apoi “n” numere naturale cu maxim 4 cifre fiecare. Afisati acestea pe o singura linie de ecran, separate prin spatiu, dar in ordinea inverse a

introducerii lor de la tastatura.


Pasul 1: Se citeste “n”, apoi se citesc cele “n” numere si se memoreaza intr-un vector ca valori ale elementelor x[1], x[2], …, x[n];

Pasul 2: Se parcurge vectorul secvential, pe indici descrescatori, afisandu-se pe ecran valorile elementelor x[n], x[n-1],…, x[i] separate prin spatiu.


int main()

{

int n,x[51],i;

cout<<”cate numere se dau?”;cin>>n;

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

cout<<”x["<<i<<"]=”;cin>>x[i]; }

for(i=n;i>=1;i–)

cout<<x[i]<<” “;

return 0;

}

3) Consideram un tablou unidimensional “v” de n elemente deja sortat, si trei variabile: “i”, “s” si “m”. Verificati daca mijlocul vectorului/tabloului unidimensional este egal cu elementul cautat.


Acest algoritm se incadreaza in clasa algorimilor elaborate conform tehnicii de programare Divide et Impera. Metoda verifica de mai multe ori daca mijlocul tabloului unidimensional este egal cu

elementul cautat:

1: In cazul in care este egala, variabila m reprezinta pozitia elementului in vector;

2: Daca nu se indeplineste conditia de egalitate se trece la verificarea pozitiei elementului cautat in vector.

3: Daca elementul cautat este mai mic decat elementul din mijlocul vectorului, variabila “s” ia valoarea lui “m” iar daca nu variabila i ia valoarea lui m.

Totul se repeta cat timp i este mai mic decat s.

#include<iostream>


int n,x,v[10],m;

int caut (int s, int d)

{

if(s>d)

return -1;

else

{

m =(s+d)/2;

if (x==v[m])

return m;

if (x<v[m])

return caut(s,m-1);

else

return caut(m+1,d);

}

}

int main()

{

cout<<”n,x “;

cin>>n>>x;

cout<<”dati “<<n<<” elemente (in ordine crescatoare).\n”;

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

cin>>v[i];

cout<<”elementul “<<x<<” a fost gasit pe pozitia: “<<caut (1,n);

return 0;

}

i = inceput;

m = mijloc;

s = sfarait ;

4) Se citeste de la tastatura numarul natural “n” (0<n<50) si apoi “n” numere naturale cu maxim 9 cifre fiecare. Afisati toate cifrele impare existente in toate cele n numere date. Cifrele vor fi luate in considerare exact in ordinea de la intrare. Daca toate numerele sunt alcatuite doar cu cifre pare afisati mesajul NU EXISTA.


Pasul 1: Se citeste n, apoi se citesc cele n numere si se memoreaza intr-un vector ca valori ale elementelor x[1], x[2],…,x[n];

Pasul 2: Se initializeaza lungimea vectorului auxiliar cu 0;

Pasul 3: Se parcurge vectorul x secvential, pe ranguri descrescatoare,cu scopul de a accesa cifrele fiecarui numar. Orice cifra impara intalnita se va adauga la vectorul y ca si noua componenta.

Pasul 4: Daca lungimea vectorului y a ramas 0se scrie mesajul NU EXISTA, iar in caz contrar se executa pasul 5;

Pasul 5: Se parcurg elementele lui y pe ranguri descrescatoare si se afiseaza acestea fara separator.


int main()

{

int n, y[51],i,c;

long x[51];

cout<<”cate numere se dau?”;cin>>n;

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

cout<<”x["<<i<<"]=”;cin>>x[i]; }

int L=0;

for(i=n;i>=1;i–)

while(x[i]) {

c=x[i]%10;

if(c%2) {

L++;

y[L]=c; }

x[i]/=10;

}

if(!L)

cout<<”NU EXISTA”;

else

for(i=L;i>=1;i–)

cout<<y[i];

return 0;

}

Y = vectorul auxiliar;

L = lungimea vectorului auxiliar.

5) Consideram un vector “a”, cu “n” elemente deja sortate. Verificati daca mijlocul vectorului este egal cu elementul cautat si afisati cum ca elementul cautat apartine sirului.


Algoritmul compar numarul de cautat cu elementul aflat la mijlocul sirului (element care se mai numeste si pivot):

1: In cazul in care cele doua elemente coincid cautarea s-a incheiat

cu succes;

2 Daca numarul de cautat este mai mare decat pivotul, se continua

cautarea in aceeasi maniera in subsirul delimitat de pivot si capatul sirului initial;

3: Daca numarul de cautat este mai mic decat pivotul se continua

cautarea in aceeasi maniera in subsirul delimitat de pivot si inceputul

sirului initial.



int main()

{

int i, n, x, st, dr, mijl, gasit, a[50];

cout<<”Introduceti numarul elementelor vectorului : “;cin>>n;

cout<<”Introduceti elementul de cautat : “;cin>>x;

for(i=0;i<n;i++) {

cout<<”a["<<i<<"]= “;cin>>a[i]; }

st=0; dr=n-1; gasit=0;

while (st<=dr && gasit!=1) {

mijl=(st+dr)/2;

if (a[mijl]==x)

gasit=1;

else

if (x<a[mijl])

dr=mijl-1;

else

st=mijl+1;

}

if (st>dr)

cout<<”Nu s-a gasit elementul cautat !”<<endl;

else

cout<<”Elementul cautat apartine sirului !”<<endl;

return 0;

}

Tema -Metode de sortare

A. Notiuni teoretice

1.Cosideratii generale

Ce dificila ar fi consultarea unui dictionar ,daca nu ar avea cuvintele aranjate in ordine alfabetica.Analog,ordinea articolelor din memoria calculatorului are implicatii majore asupra vitezei si simplitatii algoritmilor care le prelucreaza.

Nu vom insista asupra enormelor aplicatii ale sortarii dar mentionam ca frabricantii de calculatoare estimeaza ca peste 25% din timpul de rulare al calculatoarelor este ocupat de sortare in conditiile in care toate solicitarile sunt luate in considerare.

2.Terminologie

Chiar daca dictionarele definesc sortarea ca pe un proces de separare si aranjare al lucrarilor dupa clase si fel, uzual programatorii folosesc cuvantul sortare in sens de aranjare a lucrurilor intr-o ordine ascendenta sau descendenta.

Se poate utiliza si termenul de ordonare.

3.Definitie

Problema sortarii consta in rearanjarea unei colectii aflate in memoria interna astfel incat cheile articolelor sa fie ordonate crescator ( eventual descrescator).

4.Clasificarea algoritmilor(strategii generale)

A. Algoritmi de sortare prin comparatii

1. Sortare prin interschimbare 2. Sortare prin insertie

Sortarea prin insertie directa si sortare prin insertie binara Sortare prin metoda Shell

3.Sortare prin selectie

Selectie naiva Selectie sistematica

B. Algoritmi de sortare prin distribuire

1. Sortarea cuvintelor

2. Distribuire prin segmentare

C.Algoritmi de sortare prin numarare

D.Sortare topologica

E.Algoritmi de sortare utilizand metoda “Divide et impera”

1. Sortarea prin interclasare 2. Sortarea rapida

A. Algoritmi de sortare prin comparatii

Au la baza determinarii permutarii, comparatii la fiecare moment intre doua elemente a[i] si a[j] din tabloul ce se sorteaza.Dupa scopul compararii avem algoritmi definiti astfel:

Prin rearanjarea valorilor a[i] si a[j] in ordine(interschimbare)

sortarea prin metoda bulelor(BubbleSort)

Prin inserarea uneia din valori intr-o subsecventa deja ordonata(insertie).

insertie directa sortarea SHELL ( pentru vectori de mari dimensiuni)

Prin selectia unei valori ce se repartizeaza pe pozitia finala a ei (selectie)

selectia naiva mai rapida decat a bulelor,dar mai putin eficienta comparativ cu: selectia sistematica ce presupune parcurgerea a doua etape:

- constructia proprietatii Heap(a) pentru o secventa data

-selectarea elementului maximal in mod repetat din secventa curenta ( refacand apoi Heap pentru secventa ramasa)

Ansamblul (Heap) reprezinta o modalitate frecventa de organizare a datelor utilizata foarte mult de calculul paralel.

B.Algoritmi de sortare prin distribuire

Algoritmii de sortare prin distribuire presupunand ca se cunosc informatii privind distributia acestor elemente (informatii suplimentare despre elementele). Utilizam aceste informatii pentru a distribui elementele secventei de sortat in “pachete” ce se vor sorta in acelasi mod prin alta metoda, iar apoi le combinam obtinand lista finala sortata.

Algoritmi de sortare a cuvintelor (RadixSort)

Sa presupunem ca avem n fise, iar fiecare contine un nume ce identifica in mod unic fisa.Sa sortam manual fisele.Le impartim in pachete,fiecare pachet cuprizand toate fisele ce incep cu aceeasi litera.Apoi sortam fiecare pachet dupa a doua litera.. s.a.m.d. Dupa sortarea pachetelor le recombinam obtinand o lista liniara sortata. Aceasta metoda poate fi formalizata intr-un algoritm de sortare a sirurilor de cuvinte (caractere). Presupunem ca elementele secventei de sortat reprezinta sirul de lungime fixata m ce se definesc peste un alfabet de k litere. Putem presupune ca elementele de sortat reprezinta nmere scrise in baza k. De aceea sortarea cuvintelor este numita in limba engleza “radix sort”(radix=baze).

C.Algoritmul de sortare prin numarare

Consta in a numara pentru fiecare element a(i) cate elemenete ,strict mai mici decat el, exista. Numerele obtinute sunt memorate intr-un vector k.Pe baza lui vom rearanja elementele lui a intr-un alt vector b.

D. Sortarea topologica

Consideram ca relatia de ordine este partiala. De ex a2<a1 ,a2<a3<a4. Problema consta in crearea unei liste liniare compatibila cu relatia de ordine: daca Ai<Aj atunci Ai precede pe Aj in lista finala.In exemplul anterior lista finala poate fi (a2,a1,a3,a4) sau (a2,a3,a1,a4) sau (a2,a3,a4,a1).

E.Sortare untilizand metoda “Divide et impera”

1.Sortarea rapida (Quick Sort) reprezentata in 1962. Pentru rezolvare este necesara o procedura care traseaza o portiune de vector cuprinsa intre indicii dati de p si q. Rolul acestei proceduri este de a pozitiona prima componenta a[p] pe o pozitie k suprinsa intre p si q astfel incat toate componentele vectorului curinse intre p si k-1 sa fie mai mici sau egale decat a[k] si toate componentele vectorului cuprinse intre k+1 si q sa fie mai mari sau egale decat a[k].

2.Mergesor. Un alt algoritmcare se bazeaza pe metoda “Divide et Impera” este algoritmul de interclasare a doi vectori sortati.El produce ca rezultat tot un vector sortat, care contine elementele celor doi vectori care se interclaseaza.DEci pentru a sorta elementele vectorului a , il vom partitiona in doua vom sorta sirurile a[1]…a[m],a[m+1]…a[n] apoi vom interclasa subsirurile sortate.

Reprezentarea algoritmilor de sortare in pseudocod

1.Sortarea prin metoda bulelor (Bubble Sort)

Se parcurge vectorul (operand interschimbarii de elemente ,,vecine”)atat timp cat mai exista o pareche ( a[i],a[a+i] ) cu a[i]>a[a+i].

repeta modificat=fals pentru i=1,N-1 executa daca a[i]>a[i+1] atunci schimba a[i],a[i+1] modificat adevarat sf daca sf pentru pana cand modificat=fals

Acest algoritm se mai numeste si “sortarea prin selectie si interschimbare” , “sortarea prin propagare” sau “metoda lenta de sortare” datorita numarului mare de operatii care trebuie effectuate.Succesul algoritmului este asigurat de trecerea succesiva prin tablou,pana cand acesta este sortat,cu specificatia ca , la fiecare trecere , elementele successive I si i+1 pentru care a[i]>a[i+1], vor fi interschimbate.

Metoda poate fi imbunatatita daca ,dupa fiecare trecere , se va retine ultima pozitie din tablou in care a avut loc o interschimbare, iar trecerea urmatoare se va efectua doar pana la acea pozitie. In cazul in care la o trecere nu a avut oc nicio interschimbare algoritmul se va incheia.

Pentru o si mai buna optimizare se poate inlocui trecerea prin tablou intr-un sens cu trecerea in dublu sens .In acest caz , daca la doua treceri successive, intre doua elemente I si i+1 nu a avut loc o interschimbare atunci la trecerile urmatoare nu se vor inregistra interschimbari.

Cu toate optimizarile aduse acestei sortari, ea se dovedeste a fi cu mult mai lenta decat sortarea prin insertie,fiind insa preferata de unii datorita simplitatii, ce nu ridica problem de implementare. Pentru valori suficient de mari ale dimensiunii vectorului ce urmeaza a fi sortat se recomanda utilizarea unor algoritmi ce au o complexitate mai redusa si, prin urmare, ofera un timp de calcul mai mic.

#include<iostrem.h>

void main ( )

{

int n,i,aux,terminat,a[50];

cout<<”Introduceti dimensiunea vectorului : “;cin>>n;

for(i=0;i<=n-1;i++) {

cout<<”a["<<i<<"]=”;

cin>>a[i];

}

terminat=0;

while(!terminat) {

terminat=1;

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

if(a[i]>a[i+1]) {

aux-a[i];

a[i]=a[i+1];

a[i+1]=aux;

terminat=0;

}

}

cout<<”Vectorul ordonat este este : “;

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

cout<<a[i]<<” “;

cout endl;

}

2.Metoda prin selectie directa

O versiune a metodei de baza SelectSort este urmatoarea:

pentru i=1,N-1 executa pentru j=i+1 , N executa daca a[i]>a[j] atunci schimba a[i],a[j] sf daca sf pentrusf pentru

Si aceasta metoda realizeaza in final acelasi lucru,insa pe pescurs se modifica si pozitia altor elemente care nu satisfaac conditia de ordine.Daca in algoritmul initial avem ‘schimba’ doar de n ori, in acest algoritm ‘schimba’ poate apare de mai multe ori.Complexitatea acestuia este n x n ( n la patrat).

Consideram un vector de elemente compatibile intre ele si dorim sa le ordonam crescator. Pentru aceasta comparam primul element cu toate elementele cu toate elementele care urmeaza dupa

el.Daca gasim un element mai mic decat primul atunci le interschimbampe cele doua.Apo continuam cu al doilea element al sirului, pe care,de asemenea il comparam cu toate elementele care urmeaza dupa el si in caz de inversiune interschimbam cele doua elemente.Apo procedam la fel cu al treilea element al sirului iar procesul continua astfel pana la penultimul element al sirului care va fi comparat cu ultimul element din sir.


void main ( )

{

int i,j,n,aux,a[50] ;

cout<<”Introduceti numarul de elemente din sir : “;cin>>n;

cout<<”Introduceti numerele”<<endl;

for(i=0;i<n;i++) {

cout<<”a["<<i<<"]=”;cin>>a[i];

}

//urmeaza algoritmul de sortare

for(i=0;i<n-i;i++)

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

if (a[j]<a[i] ) {

aux-a[j];

a[i]=a[j];

a[j]-aux;

}

//urmeaza afisarea sirului sortat

cout<<”Sirul sortat este:”<<endl;

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

cout<<a[i]<<” “;

cout<<endl;

}

3.Sortarea prin insertie

Sortarea prin insertie se bazeaza pe aceleasi principii ca si cele aplicate de majoritatea jucatorilor de carti,adica dupa ridicarea uncei carti de pe masa,aceasta se aseaza in pachetul din mana la locul potrivit.Cu alte cuvinte,consideram ca avem vectorul sortat a, iar la ivirea unui nou element care se va adauga vectorului,el va fi pus pe locul potrivit printr-o insertie in interiorul vectorului.

Insertie directa.Este cea mai simpla implementare a algoritmului si se face in felul urmator: Se considera ca primele i elemente al vectorului sunt deja sortate.Pentru elementul al (i+1)-lea,din tabloul initial,se va gasi pozitia in care trebuie inserat printre primele i elemente.Toate elementele tabloului de la acasta pozitie si pana la i vor fi deplasate cu o pozitie mai la dreapta iar pozitia eliberata va fi ocupata de elemntul i+1.

pentru j=1 ,N-1 executa x=a[j]; i=j-1;

cat timp ((i>=0) && (x<a[i])) a[i+1]=a[i] i=i-1; sf cat timp a[i+1]=xsf pentru

Inserare rapida.Deoarece vectorul destinatie este un vector ordonat crescator, cautarea pozitiei in care va fi inserat a[i] se poate face nu secvential ( ca in cazul inserarii directe) ci prin algoritmul de cautare binara.Subvectorul destinatiei este impartit in doi subvectori,se examineaza relatia de ordine dintre elementul de la mijlocul subvectorului si elementul a[j] si se stabileste daca elemntul a[i] va fi inserat in prima jumatate sau in a doua jumatate.Operatia de divizare a subvectorului continua pana se gaseste pozitia in care urmeaza sa fie inserat a[i].

#include<iostream.h>void main ( ){ int i,j,n,aux,a[50]; cout<<" introduceti dimensiunea sirului: "<<endl;cin>>n; cout<<"Dati elementele sirului:"<<endl; for(i=0;i<n;i++) { cout<<"a["<<i<<"]=";cin>>a[i]; } for(j=1;j<n;j++) { aux=a[j]; i=j-1; while (aux<a[i] && i>=0) { a[i+1]=a[i]; i=i-1; } a[i+1]=aux; } cout <<"Sirul ordonat este:"; for(i=0;i<n;i++) cout<<a[i]<<" "; cout<<andl;}

PROBLEME

1. Subprogramul ordonare primeste prin parametrul x un tablou unidimensional cu cel mult 100 de elemente ,numere reale, iar prin parametrul n un numar intreg ce reprezinta numarul efectiv de elemente ale tabloului x. Subprogramul ordoneaza crescator elementele tabloului si furnizeaza tabloul ordonat prin tot parametru x. Scrieti un program C/C++ care citeste de la tastatura doua numere naturale n si m (1<=n<=100 si m<=n) , si apoi un sir de n numere reale distincte. Folosind apeluri utile ale subprogramului ordonare,programul afiseaza pe prima linie a ecranului cele mai mari m elemente din sirul citit (in ordinea crescatoare a valorilor lor), iar pe a doua linie a ecranului, cele mai mici m elemente din sir ( in ordinea descrescatoare valorii lor). Numerele afisate pe aceeasi linie vor fi separate prin cate un spatiu. daca n=9 m=3

sirul este (14.2,60,-7.5,-22,33.8,80,4,10,3)atunci se va afisa pe ecran: 33.8 60 80 3 -7.5 -22#include<iostream.h>#include<iomanip.h>float a[100],m,n;void ordonare (float x[100],int n){int i,j,final=0,aux; while (final==0) { {final=1; for (i=1;i<=n-1;i++) if(x[i]>x[i+1]) (final=0;aux=x[i];x[i]=x[i+1];x[i+1]=aux;} } }}void citire ( ){ do { cin>>n>>m;} while ((n<1) | | (n>100) | | (m<1) | | (m>n)); for(int i=1; i<=n;i++) cin>>a[i]; }

void main ( ) { citire ( ) ; ordonare (a,n) ;for (int i=n-m+1 ; i<=n; i++)cout<<setw(6)<<setprecision(2)<<a[i]; cout<<endl;for(i=m;i>=1;i--) cout<<a[i]<<" ";}

2. Scrieti programul C/C++ care citeste de la tastatura un numar natural n (1<=n<=99),impar, si construiesete in memorie un tablou unidimensional A=(A1,A2,...,An) cu elementele multimii {1,2,...,[(n+1)/2], iar elementele de pe pozitii pare sirului descrescator n,n-1,...,[(n+1)/2]+1. pentru n=11 se va construi tabloul A: 1 11 2 10 3 9 4 8 5 7 6 Elementele tabloului se afiseaza pe ecran,separate prin cate un spatiu.#include<iostream.h>ofstream f("sir.txt");int a[10000],n;void main( ){int i; while (n<0 | | n2==0);a[1]=1;for (i=2;i<n;i=1+2) { a[i+2]=i/2+1; a[i]=n+1-i/2; }for(i=1;i<=n;i++)cout<<a[i]<<" ";}

3) Fisierul matrice.txt contine pe primul rand doua valori naturale m si n reprezentand numarul de linii si respectiv coloane ale unei matrice a,iar pe urmatoarele m linii cate n valori intregi cu maxim 4 cifra fiecare, separate prin cate un spatiu,reprezentand elementele matricei a. Se cere sa se afiseze pe ecran un sir de 2*(n+m)-4 numere ordonate crescator ,sir format din elementele alfate pe chenarul exterior al matricei a. Chenarul exterios este format din prima linie,ultima linie,prima coloana si ultima coloana. Alegeti un algoritm de rezolvare eficient din punct de vedere al gestionarii memoriei.daca fisierul matrice.xt contine: 3 4 6 7 1 9 3 0 2 8 5 4 8 5 se va afisa: 1 3 4 5 5 6 7 8 8 9 Scrieti programul C/C++ corespunzator.#include<iostream.h>#include<fstream.h>ifstream f("matrice.txt");void main( ){ int s=0,n,m,i,j,t,a[100],x; f>>m; f>>n; t=0; for(i=1;i<=n;i++) {t++;f>>a[t];} for(j=2;j<=m-1;j++) for(i=1;i<=n;i++) {f>>x; if(i==1 | | i==n) {t++;a[t]=x} } for(i=1;i<=n;i++) (t++;f>>a[t]) for(i=1;i<t;i++) for(j=j+1; j<=t;j++) if (a[i]>a[j]) {int aux-a[i]; a[i=a[j]; a[j]=aux; } for (i=1;i<=t;i++) cout<<a[i]<<" "; f.close( )}4) Scrieti un program C/C++ care citeste de la tastatura un numar natural nenul n (n<=1000 ) si apoi n numere naturale, de maximum 4 cifre fiecare,reprezentand elementele unui tablou unidimensional. Programul afiseaza mesajul 'DA' in cazul in care elementele tabloului pot fi rearanjate astfel incat sa formeze o progresie aritmetrica, iar in caz contrar afiseaza mesajul 'NU' .daca n=6 si tabloul unidimensional are valorile 5 10 30 15 25 20 --> at se va afisa 'DA' .

#include<iostream.h>#include<conio.h>int n,a[100];

void main( ) { do {printf("%d n=");//cout<<"n="; scandf("d",& n);cin>>n; while(n<=0 | | n>100 ) for(int i=1;i<=n;i++) {printf("a[%d]= ",i)//cin>>a[i]; int t.man; do {t=0; for(int i=1;i<n;i++) if (a[i]>a[i+1] ) {man=a[i];a[i]=a[i+1]; a[i+1] =man; t=1; } while(t) ; int k; k=a[2]-a[1]; t=1; for(i=2;i<n&&t;i++) if(a[i+1]-a[i] !=k) if(t) printf(\n DA");//cout<<"DA"elseprintf("\n NU")//cout<<"NU";getch();}5) Fisierul text NUMERE.IN contine , pe mai multe linii,cel mult 30000 de numere naturare nenule mai mici sau egale decat 500,despartite prin cate un spatiu.Scrieti programul C/C++ care afiseaza pe ecran, in ordine descrescatoare, despartite prin cate un spatiu, toate numerele care au aparut exact o singura data in fisierul NUMERE.IN . Daca fisierul NUMERE.IN contine numerele: 2 23 34 3 8 9 9 23 6 8 9 2 4 5 23 9Se vor afisa urmatoarele: 34 6 5 4 3#include<iostream.h>void main ( ){ int v[500],n,i,x; for(i=1;i<=500;i++) v[i]=0; do{ fin>>x; v[x]=v[x]+1; } while(!fin.eof( ) ); i=500; while(i>=1) { if(v[i]==1)cout<<i<<" ";i-- }

fin.close( );}6) Se dă un tablou a cu n elemente întregi. Să se realizeze sortarea crescătoare a elementelor tabloului.a – tabloul unidimensional;n – lungimea tabloului;aux – pentru interschimbul elementelor (de acelaşi tip cu elementele tabloului);i – contor (utilizat pentru parcurgerea tabloului);f – variabilă logică (se utilizează pentru a şti dacă s-a făcut cel puţin o operaţie de interschimbare la parcurgerea tabloului).Se iniţializează variabila f cu 1 (adică se presupune că şirul este sortat);Se începe parcurgerea tabloului plecând de la i=0 (primul element al tabloului);Se compară elementul a[i] cu elementul următor a[i+1]:Dacă a[i] > a[i+1] atunci se realizează interschimbul celor două elemente şi variabila f primeşte valoarea 0;Se trece la următoarea poziţie în tablou prin incrementarea lui i;Se continua parcurgerea tabloului făcând comparaţiile necesare până când i ajunge la valoarea n-2;Se reia algoritmul începând cu pasul 1 cât timp f=0,Când f rămâne 1 atunci înseamnă că tabloul este sortat crescător (la ultima parcurgere nu s-a realizat nici un interchimb de elemente).#include<iostream.h>int a[20],aux,f;unsigned int n,i;void main (void) { cout<<"n="; cin>>n; for (i=0;i<n;i++) { cout<<"a["<<i+1<<"]="; cin>>a[i]; }do { f=1; for(i=0;i<n-1;i++) if (a[i]>a[i+1]) { aux=a[i]; a[i]=a[i+1]; a[i+1]=aux; f=0; } } while(!f); cout<<"sirul sortat este"<<endl; for (i=0;i<n;i++) cout<<a[i]<<" "; }

Algoritmi de Cautare

Documents

Transcript of Algoritmi de Cautare