Wyszukiwanie Fibonacciego

Cel

Wyszukiwanie Fibonacciego pozwala na wyszukanie elementu na posortowanej liście. Podobnie jak w przypadku Wyszukiwania Binarnego wykorzystywana jest metoda "Dziel i Zwyciężaj" polegająca na zawężaniu przedziału w którym może znajdować się szukana wartość. Miejsce podziału listy na dwie części określają liczby Fibonacciego. Zaletą takiego rozwiązania jest fakt, że wystarczą operacje dodawania i odejmowania, a nie potrzeba mnożyć, ani dzielić. Niemniej wykonywane jest kilka operacji porównania więcej.

Algorytm

Oznaczmy k-tą liczbę Fibonacciego poprzez F_k. Ciąg liczb Fibonacciego definiujemy jako: F_{k + 2} = F_{k + 1} + F_k, gdzie dwa pierwsze wyraz to F₁ = 1 oraz F₀ = 0.

Początkowo szukamy takiego wyrazu F_m, aby F_m > n, gdzie n jest długością listy, która będzie przeszukiwana. Wyrazy na liście indeksujemy od 1. Następnie dopóki m nie wyniesie 0 wykonujemy:

1. Porównaj szukany element z elementem na pozycji F_{m - 1}, jeśli wartości są równe to zwróć F_{m - 1}
2. Jeśli jednak szukana wartość jest mniejsza to odrzuć elementy na pozycjach F_{m - 1} + 1 do n, ustaw m = m - 1 i wróć do punktu 1
3. Jeśli jednak szukana wartość jest większa to odrzuć elementy na pozycjach 1 do F_{m - 1}. Pozostałe element ponumeruj, ustaw m = m - 2 i wróć do punktu 1

Jeśli po zakończeniu pętli na wskazanej pozycji nie ma szukanego elementu to oznacza, że nie istnieje.

Przykład

Weźmy posortowaną listę L = {1, 5, 8, 13, 15, 16, 20, 26, 30, 34}. Na początek ustalamy, że F₇ > n = 10.

Spróbujmy wyszukać teraz wartość 13.

Bardzo podobnie wygląda przeszukiwanie listy, gdy element nie istnieje. Przykładowo wyszukajmy nieistniejący element 2.

Implementacja

Liczby Fibonacciego

Liczby Fibonacciego bardzo łatwo się wyprowadza z zależności rekurencyjnej. Nie jest to jednak efektywna metoda i zdecydowanie lepiej jest wyprowadzić w sposób iteracyjny. Zauważmy, że w tym przypadku zawsze chcemy dowiedzieć się jaka jest następna, albo poprzednia liczba Fibonacciego. Istnieje możliwosć, aby zawsze przechowywać dwie kolejne liczby Fibonacciego. Dzięki temu zawsze będzie można wyliczyć poprzedni, albo następny wyraz bez wyliczania do od początku.

W celu uproszczenia zapisu kodu utworzona została klasa Fibonacci, która pozwala na pobranie aktualnego wyrazu, albo przesunąć wyraz o 1 do przodu lub do tyłu. Poniżej znajduje się jej pełny kod:

1. class Fibonacci {
2. private:
3.   int a, b;
5. public:
6.   Fibonacci() {
7.     a = 0;
8.     b = 0;
9.   }
11.   void Nastepna() {
12.     if (b == 0) b = 1;
13.     int c = a + b;
14.     a = b; b = c;
15.   }
17.   void Poprzednia() {
18.     if (b == 0) return;
19.     int c = b - a;
20.     b = a; a = c;
21.   }
23.   int Aktualna() {
24.     return b;
25.   }
26. };

W klasie zadeklarowane są (3.) dwie zmienne a i b, które oznaczają kolejne dwa wyrazy liczb Fibonacciego. Na podstawie nich będą wyliczany poprzedni lub następny. W celu wyliczenia następnego wyrazu należy wywołać funkcję Nastepna(), jeśli poprzednią to Poprzednia(), a jesli chcemy odczytać aktualną wartość to należy wywołać Aktualna().

Wyszukiwanie

Przejdźmy teraz do algorytmu wyszukiwania. Funkcja będzie przyjmować tablicę danych, więc usuwanie danych jest mało wygodne. Podczas obcinania danych z końca wystarczy zmienić długość tablicy, ale z początku nie można tak łatwo. Z tego powodu (3.) deklarowana jest zmienna pozp, która jest numerem indeksu pierwszego elementu w tablicy. Przykładowo jeśli będzie mieć wartość 2 to element o indeksach 0 i 1 są pomijane przez algorytm.

1. int wyszukajFibonacci(int* tab, int n, int x) {
2.   Fibonacci f;
3.   int pozp = 0;
4.   while (f.Aktualna() < n)
5.     f.Nastepna();
6.   f.Poprzednia();
7.   while (f.Aktualna() != 0) {
8.     while (pozp + f.Aktualna() >= n)
9.       f.Poprzednia();
10.     if (tab[pozp + f.Aktualna() - 1] == x) {
11.       return pozp + f.Aktualna() - 1;
12.     } else if (tab[pozp + f.Aktualna() - 1] > x) {
13.       f.Poprzednia();
14.     } else {
15.       pozp += f.Aktualna();
16.       f.Poprzednia();
17.       f.Poprzednia();
18.     }
19.   }
20.   return (tab[pozp] == x) ? pozp : -1;
21. }

(2.) Zadeklaruj generator liczb Fibonacciego oraz (3.) ustal indeks początkowy na 0. Następnie (4. - 5.) znajdź najmniejszą liczbę Fibonacciego większą lub równą n. (6.) Zmniejsz indeks liczby Fibonacciego o 1. (7.) W pętli (8. - 9.) upewnij się, że aktualnie sprawdzana pozycja nie wykracza poza tablicę. Następnie (10.) sprawdź czy został znaleziony element. Jeśli tak to (11.) zwróć aktualną pozycję. W przypadku, gdy jednak (12.) szukana wartość jest mniejsza niż aktualna pozycja to (13.) tylko cofnij liczbę Fibonacciego. Usuwanie danych z końca nie ma większego znaczenia. Jednak dla przeciwnego przypadku: (15.) istnieje potrzeba zmiany indeksu początkowego i (16. - 17.) wyliczenia wyrazu Fibonacciego o dwa indeksy mniejszego.

Testowanie funkcji

W celu przetestowania działania kodu. Poniższa funkcja główna wczyta dane od użytkownika i wypisze wynik na ekran.

1. int main() {
2.   int n, x;
3.   cout << "Z ilu elementow sklada sie lista:\nn = ";
4.   cin >> n;
5.   cout << "Podaj " << n << " liczb";
6.   int* tab = new int[n];
7.   for (int i = 0; i < n; i++)
8.     cin >> tab[i];
9.   cout << "Podaj jaki element wyszukac\nx = ";
10.   cin >> x;
11.   int poz = wyszukajFibonacci(tab, n, x);
12.   if (poz > -1) cout << "Znaleziono na pozycji " << poz;
13.   else cout << "Element nie wystepuje w tablicy";
14.   system("pause");
15.   return 0;
16. }

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Napisz funkcję Wyszukiwania Fibonacciego, która pozwoli wyszukać element x w liście posortowanej malejąco. Program na wczytać dane od użytkownika, a następnie wypisać na ekran pozycję elementu na liście, albo komunikat, że element w tablicy nie występuje.

• Kod źródłowy Zadanie 1