Exemplificări de implementare a algoritmilor

Exemplificări de modalități de implementare a algoritmilor studiați

1. Implementarea unui algoritm de sortare

Sortarea este o operațiune fundamentală în informatică, utilizată pentru organizarea datelor într-o ordine specifică (crescătoare sau descrescătoare). Un exemplu simplu de algoritm de sortare este sortarea prin selecție, care selectează în mod repetat cel mai mic element și îl plasează în poziția corectă.

Exemplu: Implementarea sortării prin selecție.
Start Citește n Citește vectorul v[1..n] Pentru i = 1 până la n-1 Execută min ← i Pentru j = i+1 până la n Execută Dacă v[j] < v[min] Atunci min ← j Interschimbă v[i] și v[min] Afișează vectorul sortat Stop

Sortarea prin selecție are o complexitate de O(n²), ceea ce o face ineficientă pentru volume mari de date. Alternative mai rapide sunt QuickSort și MergeSort.

2. Implementarea unui algoritm de căutare

Căutarea unui element într-un vector este un proces esențial în programare. Căutarea liniară verifică fiecare element până găsește valoarea dorită, având o complexitate O(n). O metodă mai eficientă este căutarea binară, care necesită ca vectorul să fie sortat și are o complexitate de O(log n).

Exemplu: Implementarea căutării binare.
Start Citește n, vectorul v[1..n], x st ← 1, dr ← n, găsit ← Fals Cât timp st ≤ dr și găsit = Fals Execută mij ← (st + dr) / 2 Dacă v[mij] = x Atunci găsit ← Adevărat Altfel Dacă v[mij] < x Atunci st ← mij + 1 Altfel dr ← mij - 1 Dacă găsit Atunci Afișează "Element găsit" Altfel Afișează "Element inexistent" Stop

Căutarea binară este semnificativ mai rapidă decât căutarea liniară, fiind utilizată în baze de date și structuri eficiente precum arborii de căutare binară.

3. Implementarea unui algoritm recursiv

Recursivitatea este o tehnică puternică folosită pentru rezolvarea problemelor care pot fi împărțite în subprobleme similare. Un exemplu clasic este șirul Fibonacci, unde fiecare termen este suma celor doi termeni anteriori.

Exemplu: Calculul termenului n din șirul Fibonacci folosind recursivitate.
Funcție Fibonacci(n) Dacă n ≤ 1 Atunci returnează n Altfel returnează Fibonacci(n-1) + Fibonacci(n-2)

Deși elegant, acest algoritm are o complexitate exponențială O(2ⁿ). O abordare mai eficientă este utilizarea programării dinamice pentru a evita recalculările inutile.