|

Algoritmi de Căutare – Căutarea Secvențială 18


1. Obiectivele lecției:

  • Să înțeleagă principiul căutării secvențiale.
  • Să implementeze algoritmul de căutare secvențială în limbajul C++.
  • Să analizeze eficiența algoritmului (complexitatea în timp).
  • Să aplice metoda pentru rezolvarea unor probleme practice.

2. Conținutul lecției:

Ce este căutarea secvențială?

  • Definiție: Căutarea secvențială este o metodă simplă de căutare, în care se verifică fiecare element al unui vector în ordine, până când se găsește elementul căutat sau se ajunge la finalul vectorului.
  • Aplicație: Este utilizată atunci când datele nu sunt sortate sau când se lucrează cu seturi de date mici.

Cum funcționează?

  1. Se compară elementul căutat cu fiecare element din vector, pornind de la început.
  2. Dacă se găsește o potrivire, se returnează poziția elementului.
  3. Dacă nu se găsește elementul până la finalul vectorului, se indică faptul că nu există.

Pseudocod:

Intrare: vector, dimensiune, valoare_cautata

Pentru i de la 0 la dimensiune – 1:

    Dacă vector[i] == valoare_cautata:

        Returnează i

Returnează -1 (valoarea nu a fost găsită)


3. Cod în C++:


Exemplu de bază:

#include <iostream>

using namespace std;

int cautareSecventiala(int arr[], int n, int valoare_cautata) {

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

        if (arr[i] == valoare_cautata) {

            return i; // Returnează poziția unde a fost găsită valoarea

        }

    }

    return -1; // Valoarea nu a fost găsită

}

int main() {

    int arr[] = {4, 2, 7, 1, 9, 3};

    int n = sizeof(arr) / sizeof(arr[0]);

    int valoare_cautata;

    cout << „Introdu valoarea cautata: „;

    cin >> valoare_cautata;

    int rezultat = cautareSecventiala(arr, n, valoare_cautata);

    if (rezultat != -1) {

        cout << „Valoarea ” << valoare_cautata << ” a fost gasita la pozitia ” << rezultat << „.” << endl;

    } else {

        cout << „Valoarea ” << valoare_cautata << ” nu a fost gasita in vector.” << endl;

    }

    return 0;

}


Exemplu cu toate aparițiile unei valori:

#include <iostream>

using namespace std;

void cautareSecventialaToate(int arr[], int n, int valoare_cautata, int pozitii[], int& nr_pozitii) {

    nr_pozitii = 0; // Inițializăm numărul de poziții găsite la 0

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

        if (arr[i] == valoare_cautata) {

            pozitii[nr_pozitii] = i; // Stocăm poziția găsită

            nr_pozitii++;           // Incrementăm numărul de poziții găsite

        }

    }

}

int main() {

    int arr[] = {4, 2, 7, 2, 9, 3, 2};

    int n = sizeof(arr) / sizeof(arr[0]);

    int valoare_cautata;

    cout << „Introdu valoarea cautata: „;

    cin >> valoare_cautata;

    int pozitii[n]; // Tablou static pentru stocarea pozițiilor

    int nr_pozitii; // Variabilă pentru numărul de poziții găsite

    cautareSecventialaToate(arr, n, valoare_cautata, pozitii, nr_pozitii);

    if (nr_pozitii > 0) {

        cout << „Valoarea ” << valoare_cautata << ” a fost gasita la pozitiile: „;

        for (int i = 0; i < nr_pozitii; i++) {

            cout << pozitii[i] << ” „;

        }

        cout << endl;

    } else {

        cout << „Valoarea ” << valoare_cautata << ” nu a fost gasita in vector.” << endl;

    }

    return 0;

}


4. Complexitatea algoritmului:

  1. Cazul cel mai favorabil: O(1)
    • Elementul căutat se află la prima poziție.
  2. Cazul cel mai defavorabil: O(n)
    • Elementul căutat se află la ultima poziție sau nu există în vector.
  3. Cazul mediu: O(n)
    • Elementul căutat este distribuit aleatoriu.

Avantaje:

  • Simplu de implementat.
  • Nu necesită vector sortat.

Dezavantaje:

  • Ineficient pentru vectori mari.
  • Timp de execuție proporțional cu dimensiunea vectorului.

5. Activități practice pentru elevi:

  1. Realizați un program care determină dacă o valoare introdusă de utilizator există într-un vector de numere reale.
  2. Modificați algoritmul pentru a afișa numărul total de apariții ale unei valori în vector.
  3. Implementați un program care verifică dacă un șir de caractere există într-un vector de șiruri.

6. Scheme logice:

  1. Căutare secvențială:
    • Start -> Inițializează index i=0 -> Compară arr[i] cu valoare_cautata -> (DA: Returnează i) / (NU: i++) -> Dacă i≥n: Returnează -1 -> Stop.

7. Concluzie:

  • Căutarea secvențială este un algoritm de bază, ușor de implementat, dar cu o eficiență scăzută pentru vectori mari.
  • Este utilă atunci când datele nu sunt sortate sau pentru probleme simple.

Prin implementarea acestui algoritm, elevii vor învăța concepte fundamentale de iterare și comparare.

Similar Posts

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *