Programarea şi utilizarea calculatoarelor...Exemple de probleme Sa se scrire o functie pentru...

Programarea calculatoarelor

Universitatea “Constatin Brâncuşi” din Târgu-Jiu Facultatea de Inginerie

Departamentul de Automatică, Energie şi Mediu

Lect.dr. Adrian Runceanu

Curs 18 Algoritmi de căutare

04.01.2013 Programarea calculatoarelor 2

Algoritmi de căutare

1. Căutare secvențială 2. Căutare binară 3. Căutare prin interpolare 4. Probleme rezolvate


1. Căutare secvențială Să presupunem că dorim să determinăm dacă un element aparţine sau nu unui vector de elemente. Dacă nu ştim nimic despre elementele vectorului avem soluţia căutării secvenţiale, până găsim elementul căutat sau până testăm toate elementele. Algoritm descris în pseudocod găsit ←0 pentru i← 0,n-1 execută dacă x=v[i] atunci găsit ←1 sfârşit dacă sfârşit pentru


1. Căutare secvențială

Implementare C++:

int Caută_Secvential(int x, int v[], int n)

{

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

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

return 0;

}


1. Căutare secvențială Implementare C++:

int Caută_Secvential_Rapid(int x,int v[],int n)

{

int i=0;

while ( ( v[i]!=x ) && ( i<n ) )

i++;

if(i<n) return 1;

else return 0;

} 04.01.2013 Programarea calculatoarelor 6

2. Căutare binară

Dacă elementele vectorului sunt ordonate crescător, putem să ne dăm seama dacă elementul nu există în vector fără a fi nevoie să parcurgem toate elementele vectorului. Unul dintre algoritmii folosiţi în acest caz este algoritmul de căutare binară. Acest algoritm are la bază principiul înjumătăţirii repetate a domeniului în care se caută elementul, prin împărţirea vectorului în doi subvectori.


2. Căutare binară

• Notăm cu st primul indice al vectorului şi cu dr ultimul indice al vectorului, iar m este indicele elementului din mijloc al vectorului m=(st+dr)/2.

• Se compară valoarea căutată cu valoarea elementului din mijloc.

• Dacă cele două valori sunt egale înseamnă că s-a găsit elementul.

• Dacă nu sunt egale vectorul v-a fi împărţit în doi subvectori.


2. Căutare binară

Operaţia de căutare constă în identificarea subvectorului în care se poate găsi elementul, prin compararea valorii căutate cu cea din mijloc, după care se divizează acest subvector în doi subvectori ş.a.m.d. până când se găseşte elementul, sau până când nu se mai poate face împarţirea în subvectori, ceea ce înseamnă că nu s-a găsit elementul.


2. Căutare binară

5 8 11 15 17 19 20 23 26

1 2 3 4 5 6 7 8 9


Exemplu: Dorim să căutăm elementul x=19 într-un vector cu 9 elemente:

st=1 dr=9 m=5

se caută în subvectorul din dreapta st=m+1=6 19 20 23 26

6 7 8 9

19<20 se caută în subvectorul din stânga dr=m-1=6 st=m=5

17 19

5 6

19>17 se caută în subvectorul din dreapta st=m+1=6

19

6 Elementul a fost găsit

2. Căutare binară Algoritm descris în pseudocod

Funcţia CautareBinara(n, A, x) st←1 dr←n cât timp st≤dr execută m ← [(st+dr)/2] dacă x=A[m] atunci CautareBinara ← m st ← dr+1 altfel dacă st<A[m] atunci dr ← m-1 altfel st ← m+1 sfârşitdacă sfârşitdacă sfârşitcât timp sfârşitCautareBinara


2. Căutare binară Implementare C++:

int CautareBinara(int n, int a[], int x) { int st, dr, m; st = 0; dr = n - 1; while(st <= dr) { m = (st + dr) / 2; if (x == a[m]) { return m; st = dr + 1; }


else

if (x < a[m]) dr = m - 1;

else st = m + 1;

}

return -1;

}

3. Căutare prin interpolare

Este similară cu căutarea binară, dar foloseşte o altă formulă pentru calculul lui m şi anume: • m=st+(x-v[st])*(dr-st)/(v[dr]-v[st]) ceea ce

conduce la o delimitare mai rapidă a zonei din tablou în care s-ar putea găsi x.

• Ca principiu, metoda este inspirată după procedeul căutarii într-o carte de telefon.

• Aplicarea căutării prin interpolare necesită ca elementul de căutat, x, să se afle în interiorul intervalului v[1],...,v[n], astfel apare riscul ca valoarea calculată a lui m sa depaşească n.


3. Căutare prin interpolare Algoritm descris în pseudocod

Functia CăutareInterpolare(V,n,x) st ← 0 dr ← n-1 gasit ← fals dacă ((x<=v[dr]) şi (x>=v[st])) execută repetă m ← st +(x-v[st])*[(dr-st)/(v[dr]-v[st])] dacă x ≥ v[m] atunci st ← m+ 1 altfel dr ← m-1 sfârşit dacă până când ( (v[m]≠x) şi (st<dr)şi (v[st]=v[dr]) şi (x≥v[st]) şi (x≤v[dr]) ) sfârşit dacă dacă v[m]=x atunci gasit ← adevarat sfârşit dacă sfârşit functie


3. Căutare prin interpolare Implementare în C++

int CăutareInterpolare(int v[], int n, int x) { int st,dr,m; st=0; dr=n-1; if ((x<=v[dr]) && (x>=v[st])) do { m=st+(x-v[st])*(dr-st)/(v[dr]-v[st]); if(x>v[m]) st=m+1; else dr=m-1; } while((v[m]!=x) && (st<dr) && (v[st]==v[dr]) && (x>=v[st]) && (x<=v[dr]));


3. Căutare prin interpolare

if(v[m]==x) return 1; else return 0; } Această metodă este eficientă în cazul în care n este foarte mare şi valorile elementelor tabloului au o distribuţie uniformă în intervalul v[1],...,v[n].


Exemple de probleme

Sa se construiasca o functie care verifica

daca un numar dat este prim sau nu.

Sa se scrie un program pentru afisarea

descompunerilor numerelor pare mai mici ca un

intreg dat in sume de doua numere prime.

Se va folosi Ipoteza lui Goldbach = orice

numar par se poate scrie ca suma a doua

numere prime.


Exemple de probleme Exemplu:


Date de intrare: n = 12

Date de iesire: 4=2+2 6=3+3 8=3+5 10=3+7 10=5+5 12=5+7

#include<iostream.h> int prim (int n) { int d; if(n>1) { for (d=2; d<=n/2 ; d++) if (n%d==0) return 0; // nu este prim return 1; // este prim } else return 0; // nu este prim }


int main () { int n,i,j; cout<<"dati n = "; cin>>n; for (i=2; i<=n; i=i+2) { cout<<"Numarul "<<i<<" poate fi descompus in suma de cate doua numere prime:\n"; // se verifica daca numerele j si i-j sunt prime

for (j=1; j<=i/2; j++) if (prim(j) && prim (i-j)) cout<<j<<"+"<<i-j<<endl; } }


Exemple de probleme

Rezultatul unei execuții a programului:


Exemple de probleme

Sa se scrie o functie care sa determine pozitia valorii maxime intr-un vector. Sa se scrie un program pentru ordonarea unui vector de numere prin determinarea repetata a valorii maxime dintr-un vector si schimbarea cu ultimul element din vector.




Date de intrare: n=5 5,4,3,2,1

Date de iesire: 1 2 3 4 5

Exemple de probleme

#include<iostream.h> int imax (float x[], int n) { int i, im=0; // im = indice maxim

for (i=1;i<n;i++) if (x[i] > x[im]) // x[im] este un maxim partial

im=i; return im; }


Exemple de probleme // ordonare vector

void sort (float x[], int n) { int im; float aux; while ( n>1 ) { im=imax(x,n); // schimba x[im] cu x[n-1]

aux=x[im]; x[im]=x[n-1]; x[n-1]=aux; n--; // scade dimensiune vector

} }


Exemple de probleme int main () { float t[100]; int i, n; cout<<"Dati n = "; cin>>n; for(i=0; i<n; i++) { cout<<"t["<<i<<"]="; cin>>t[i]; }


sort (t,n);

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

cout<<t[i]<<" ";

}

Exemple de probleme



Exemple de probleme

Sa se scrie o functie pentru calculul valorii unui polinom cu coeficienti intregi. P(x)= a[0]*xn +a[1]*xn-1 + ... +a[n-1]*x1 + a[n]*x0 Exemplu: x3 + 3*x2 + 2*x + 6 are ca radacina pe x=-3




Date de intrare: Numar coeficienti: 4 1 3 2 6 x=-3

Date de iesire: P(-3)=0 (valoarea -3 este radacina a polinomului)

Exemple de probleme

#include<iostream.h>

// calcul valoare polinom ptr un x dat

long valoare_polinom(int c[], int n, int x)

{

int i, s=0;

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

s = s * x + c[i];

return s;

}


Exemple de probleme

int main () { int x, a[100],i=0, n; cout<<"Numar coeficienti = "; cin>>n; cout<<"Dati coeficientii polinomului, in ordinea descrescatoare a puterilor lui x:\n"; for (i=0; i<=n-1 ;i++) cin>>a[i]; cout<<"Dati valoarea lui x = "; cin>>x; cout<<valoare_polinom(a,n,x); }


Exemple de probleme



Exemple de probleme

Sa se scrire o functie pentru inmultirea a doua matrice patratice cu acelasi numar de linii si coloane. Sa se scrie o functie pentru ridicarea unei matrice patratice la o putere intreaga, prin inmultiri repetate (folosind prima functie). Sa se scrie un program pentru verificare pe o matrice unitate.




Date de intrare: n=3 1 2 3 4 5 6 7 8 9

Date de iesire: 40 36 42 66 81 96 102 126 150

Exemple de probleme

#include<iostream.h> typedef float num; typedef num mat[20][20]; // definire tip "mat"

// generare matrice unitate

void matrice_unitate(mat u, int n) { int i,j; for (i=0;i<n;i++) for (j=0;j<n;j++) if (i==j) u[i][j]=1; else u[i][j]=0; }


Exemple de probleme

// produs matrice patratice

void produs_matrici(mat a, mat b, mat c, int n) { int i,j,k; mat t; // matrice de lucru (pentru produs): t=a*b for (i=0;i<n;i++) for (j=0;j<n;j++) { t[i][j]=0; for (k=0;k<n;k++) t[i][j] += a[i][k]*b[k][j]; }


Exemple de probleme

// copiaza din t in c

for (i=0;i<n;i++) for (j=0;j<n;j++) c[i][j]=t[i][j]; }


Exemple de probleme

// afisare matrice

void scrie_matrice(mat a, int n) { int i,j; for (i=0;i<n;i++) { for (j=0;j<n;j++) cout<<a[i][j]<<" "; cout<<"\n"; } }


Exemple de probleme

// ridicare la putere matrice

void exp_matrice(mat a, int n, int k, mat p)

{

int i,j;

matrice_unitate(p,n); // initializare p cu matrice unitate

// inmultiri repetate

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

produs_matrici(p,a,p,n);

}


Exemple de probleme int main () { int n=3; // dimensiuni pentru teste mat a={{1,2,3},{4,5,6},{7,8,9}}; mat b,c ; matrice_unitate(b,n); produs_matrici(a,b,a,n); cout<<"Matricea initiala\n"; scrie_matrice(a,n); // ridicare la putere matrice exp_matrice(a,n,2,c); cout<<"Matricea A la puterea 2\n"; scrie_matrice(c,n); }


Exemple de probleme



Structura biletelor de examen




Subiect I - Grile cu alegere multiplă. Identificați litera care corespunde răspunsului corect. Subiect II - Algoritm în pseudocod Specializarea INGINERIE ENERGETICA: Subiect III – Enunțul unei probleme având un exemplu specificat. Specializarea INGINERIA SISTEMELOR: Subiect III – Enunțul unei probleme cu vectori sau matrici, având un exemplu specificat. Subiect IV – Enunțul unei probleme cu funcții, având un exemplu specificat.



Subiect II - Algoritm în pseudocod

Algoritm 1


Se consideră următorul algoritm pseudocod:

citeste n (numar natural cu cel mult 9 cifre) cat timp n>=10 executa | s=0 | cat timp n≠0 executa | | s=s+n%10 | | n=[n/10] | |sfarsit cat timp | n=s |sfarsit cat timp scrie n

Algoritm 1 (continuare)


1. Ce se va afişa dacă valoarea citită pentru n este 989736?

2. Scrieţi programul C++ corespunzător algoritmului

dat. 3. Scrieţi un algoritm echivalent cu algoritmul dat,

dar care să utilizeze un alt tip de structură repetitivă.

Algoritm 1 - solutie


1. 9+8+9+7+3+6=42 4+2 = 6 Rezultat final 6



2. Programul C++ corespunzător

algoritmului dat este:


long int n, s;

int main()

{

cout<<"Dati n= ";

cin>>n;

while(n>=10)

{

s=0;

while(n!=0)

{

s=s+n%10;

n=n/10;

}

n=s;

}

cout<<n;

}



3. Algoritmul echivalent cu algoritmul dat, dar care să utilizeze un alt

tip de structură repetitivă este:

citeste n (numar natural cu cel mult 9 cifre)

repeta

| s=0

| repeta

| | s=s+n%10

| | n=[n/10]

| |pana cand n=0

| n=s

|pana cand n<10

scrie n

Algoritm 2


Se consideră următorul algoritm pseudocod: citeste a,b (numere naturale) c=a%10 pentru i=1,b-1 executa | c=c*a | c=c%10 |sfarsit pentru scrie c

Algoritm 2 (continuare)


1. Ce valoare afişează algoritmul pentru a=28 şi b=10?

2. Scrieţi programul C++ corespunzător

algoritmului dat. 3. Scrieţi algoritmul pseudocod care să fie

echivalent cu cel dat şi care să conţină un alt tip de structură repetitivă.



1. i=1 => c=8*28=224; c=4; i=2 => c=4*28=112; c=2; i=3 => c=2*28=56; c=6; i=4 => c=6*28=168; c=8; i=5 => c=8*28=224; c=4; i=6 => c=4*28=112; c=2; i=7 => c=2*28=56; c=6; i=8 => c=6*28=168; c=8; i=9 => c=8*28=224; c=4; Rezultat: 4



2. Programul C++ corespunzător

algoritmului dat este:


int a,b,c,i;

int main()

{

cout<<"a= "; cin>>a;

cout<<"b= "; cin>>b;

c=a%10;

for(i=1;i<=b-1;i++)

{

c=c*a;

c=c%10;

}

cout<<"\nc = "<<c;

}



3. Algoritmul echivalent cu algoritmul dat, dar care să utilizeze un alt tip de structură repetitivă este:

citește a,b (numere naturale) c=a%10 i=1 cât timp i<=b-1 execută | c=c*a | c=c%10 | i=i+1 |sfârșit cât timp scrie c



Subiectul III – Enunțul unei probleme cu vectori sau matrici, având un exemplu specificat.

Întrebări?


Programarea şi utilizarea calculatoarelor...Exemple de probleme Sa se scrire o functie pentru...

Documents

Transcript of Programarea şi utilizarea calculatoarelor...Exemple de probleme Sa se scrire o functie pentru...