Opis programu
- Program ilustruje działanie algorytmu wyszukiwania elementu w zbiorze uporządkowanym metodą przez połowienie.
- Algorytm opisany w podręczniku w punkcie 4 na stronie 69.
- Wersja "PODRĘCZNIKOWA" opisana w podręczniku na stronach 103-104.
Kod programu:
#include <iostream>
using namespace std;
const int N = 10; //ilość liczb
int liczby[N]; //tablica dla liczb
// funkcja wprowadzająca do programu liczby do posortowania
void wprowadzDane()
{
int i;
cout << "\n Wyszukiwanie elementu w zbiorze uporzadkowanym";
cout << "\nwersja podrecznikowa, str 101-102\n";
cout << "\nIlosc liczb: " << N << "\n";
// pętla wprowadzająca liczby do posortowania
for (i = 0; i < N; i++)
{
cout << "podaj liczbe nr " << i << " (musi byc >= od liczby podanej poprzednio ): ";
cin >> liczby[i];
}
}
//funkcja wyszukująca pozycję szukanej wartosci w tablicy liczby
int znajdzDana(int wartosc)
{
int poczatek, koniec, srodek;
poczatek = 0;
koniec = N;
do
{
srodek = (poczatek + koniec) / 2;
if (liczby[srodek] == wartosc)
return srodek;
else
{
if (wartosc < liczby[srodek]) koniec = srodek - 1;
else poczatek = srodek + 1;
}
} while (poczatek <= koniec);
return -1;
}
//program główny
int main() {
int wartosc, pozycja;
wprowadzDane();
cout << "\n Podaj liczbe do wyszukania:"; cin >> wartosc;
pozycja = znajdzDana(wartosc);
if (pozycja >= 0) cout << "\nZnaleziono wartosc " << wartosc << " na pozycji nr " << pozycja;
else cout << "\nNie znaleziono wartosci " << wartosc;
return 0;
}
Użycie kodu:
- Powyższy kod można wykorzystać w środowiski Dev C++. Wystarczy utworzyć nowy projekt i wkleić ten kod zamiast istniejącego.
- Można też użyć kodu na jednej ze stron WWW z kompilatorami on-line, na przykład na stronie: www.cpp.sh