Τι Είναι ο Fibonacci Search;

Φαντάσου ότι έχεις μια σειρά από πολύχρωμα μπάλες που είναι τακτοποιημένες σε μια σειρά. Θέλεις να βρεις μια συγκεκριμένη μπάλα, αλλά δεν ξέρεις που βρίσκεται. Η σειρά των μπάλων είναι οργανωμένη, πράγμα που σημαίνει ότι είναι ταξινομημένη από την πιο μικρή μέχρι την πιο μεγάλη.

Ο Fibonacci Search είναι σαν ένα παιχνίδι που σε βοηθάει να βρεις τη μπάλα που ψάχνεις, αλλά χρησιμοποιεί έναν ειδικό τρόπο βασισμένο σε αριθμούς της Fibonacci. Αυτή η σειρά αριθμών είναι: 0, 1, 1, 2, 3, 5, 8, 13, 21, και ούτω καθεξής.

Πώς Λειτουργεί;

Ακολουθεί έναν έξυπνο τρόπο για να βρει τη μπάλα, χωρίς να κοιτάξει μία-μία όλες τις μπάλες:

  1. Βρίσκουμε Αριθμούς της Fibonacci: Δημιουργούμε μια σειρά αριθμών Fibonacci μέχρι να βρούμε τον μεγαλύτερο αριθμό που είναι μικρότερος ή ίσος με το μήκος της σειράς μπάλων.
  2. Χρησιμοποιούμε τους Αριθμούς για Αναζήτηση: Χρησιμοποιούμε αυτούς τους αριθμούς για να “πηδήξουμε” σε συγκεκριμένες θέσεις στη σειρά των μπάλων, αντί να κοιτάξουμε όλες τις θέσεις.
  3. Επαναλαμβάνουμε: Αν δεν βρούμε τη μπάλα στην αρχική μας πηγή, μειώνουμε τον αριθμό των “πηδημάτων” μας με βάση τους αριθμούς της Fibonacci και συνεχίζουμε μέχρι να βρούμε τη μπάλα ή να καταλάβουμε ότι δεν υπάρχει στη σειρά.

Παράδειγμα με Κώδικα

Ας δούμε πώς μπορούμε να το κάνουμε στην C#:

using System;

class FibonacciSearchExample
{
    static void Main()
    {
        int[] array = { 10, 22, 35, 40, 45, 50, 60, 70, 80, 82, 85, 90, 100 };
        int target = 85;

        int result = FibonacciSearch(array, target);
        if (result != -1)
        {
            Console.WriteLine($"Η μπάλα με τιμή {target} βρέθηκε στη θέση {result}.");
        }
        else
        {
            Console.WriteLine($"Η μπάλα με τιμή {target} δεν βρέθηκε.");
        }
    }

    static int FibonacciSearch(int[] array, int target)
    {
        int n = array.Length;
        int fibM_minus_2 = 0; // (m-2)th Fibonacci Number
        int fibM_minus_1 = 1; // (m-1)th Fibonacci Number
        int fibM = fibM_minus_1 + fibM_minus_2; // mth Fibonacci Number

        // Find the smallest Fibonacci number greater than or equal to the length of the array
        while (fibM < n)
        {
            fibM_minus_2 = fibM_minus_1;
            fibM_minus_1 = fibM;
            fibM = fibM_minus_1 + fibM_minus_2;
        }

        int offset = -1;

        // While there are elements to compare
        while (fibM > 1)
        {
            // Check if fibM_minus_2 is a valid index
            int i = Math.Min(offset + fibM_minus_2, n - 1);

            // If target is greater than the value at index i, move the search range
            if (array[i] < target)
            {
                fibM = fibM_minus_1;
                fibM_minus_1 = fibM_minus_2;
                fibM_minus_2 = fibM - fibM_minus_1;
                offset = i;
            }
            // If target is smaller than the value at index i, adjust the range
            else if (array[i] > target)
            {
                fibM = fibM_minus_2;
                fibM_minus_1 = fibM_minus_1 - fibM_minus_2;
                fibM_minus_2 = fibM - fibM_minus_1;
            }
            // Element found
            else
                return i;
        }

        // The last comparison
        if (fibM_minus_1 == 1 && array[offset + 1] == target)
            return offset + 1;

        return -1;
    }
}

Σημαντικά Σημεία

  1. Αριθμοί της Fibonacci: Χρησιμοποιούμε τη σειρά των αριθμών Fibonacci για να αποφασίσουμε σε ποιες θέσεις να κοιτάξουμε.
  2. Πηδήματα: Αντί να κοιτάμε όλες τις θέσεις, πηδάμε σε συγκεκριμένες θέσεις με βάση τους αριθμούς της Fibonacci.
  3. Ανατροφοδότηση: Αν δεν βρούμε αυτό που ψάχνουμε, προσαρμόζουμε τους αριθμούς Fibonacci και συνεχίζουμε την αναζήτηση.

Ελπίζω αυτό να σου δίνει μια καλή ιδέα για το πώς λειτουργεί ο Fibonacci Search! Αν έχεις άλλες ερωτήσεις, μη διστάσεις να ρωτήσεις.

Fibonacci SearchDownload