Yazan : Şadi Evren ŞEKER

Bu arama algoritması, özyineli (recursive) bir seri olan fibonacci sayılarını kullanarak sıralı bir dizi üzerinde arama yapmaktadır.

Çalışma mantığı arama yapılacak olan sıralı diziyi fibonacci sayılarını kullanarak parçalara bölmektir. Örneğin arama yapılacak olan alanın en fazla 2147483647 değerine sahip olabildiği integer alan olsun. Bu durumda bu sayıya ulaşana kadar olan fibonacci sayılarına ihtiyaç duyulacaktır:

{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, INT_MAX};

Bu sayılar arama alanını parçalara bölmektedir. Öncelikle aranan sayının, en büyük fibonacci sayısından büyük mü küçük mü olduğu kontrol edilir. Buna göre ilk kontrolde 1836311903 sayısından küçük ise bu sefer 1134903170 sayısından küçük olup olmadığı kontrol edilir.

Şayet aranan sayı büyük ise bu sefer serinin 2 önceki sayısı mevcut sayıya eklenir. Örneğin sayımızı bulmak için 196418 sayısından büyük olup olmadığını kontrol ederken sayının büyük olduğu görüldü bu durumda aradığımız sayının 196418 indeksinden sağda olduğunu biliyoruz. Ancak bir önceki sayı olan 317811’den de küçük olduğu biliniyor bu durumda 196418 + 75025 = 271443 sayısından büyük olup olmadığı kontrol edilir ve bu işlem böylece gider.

Yani özetle fibonacci sayılarının arasındaki aralık serideki her sayıda artmaktadır. Fibonacci araması ise bu işi terse çevirerek en büyük aralıktan en küçüğe doğru aralığı daraltarak arama işlemi yapar. En sonunda aralık 1’e inince sayı bulunur (ya da sayı seride yer almıyorsa bulunmadığı anlaşılır).
Bu arama algoritması bir parçala fethet (divide and conquere) yaklaşımıdır. Benzer bir arama yöntemi olan ikili arama (binary search) ile aynı algoritma karmaşıklığına sahiptir O(log n) ancak yapılan matematiksel çalışmalarda fibonacci aramasının daha hızlı olduğu gösterilmiştir.

Yorumlar

  1. fatih

    #include
    #include
    int main(){
    int n;
    printf("Lutfen Bir Sayi Giriniz:");
    scanf("%d",&n);
    int a=1;
    int b=1;
    for(int i=1;i<=n;i++){ printf("%d ",a); int c=a+b; a=b; b=c; } getch(); } hocam bu fibonacci kodunda,mesela 100 yazdıgım zaman bi yerden sonra sonuc - ye donuyo.bunun sebebi nedir ?

  2. Şadi Evren ŞEKER Article Author

    Kullandığınız derleyici Dev-CPP içerisinde gelen MinGW ise, yani DEV-CPP kullanıyorsanız, bir tam sayı değişkeni içerisine (integer) koyabileceğiniz azami değer 2147483647'dir. Sizin kodunuzda 100 değeri için sonuç hesaplarken bu değer aşılıyor olduğu için, bu değerin aşıldığı yerden sonra sonuçlar eksi değerlere döner. Daha detalı bilgi için tam sayı veri tipi (integer variable type) başlıklı yazıyı okuyabilirsiniz.

    başarılar

  3. Şadi Evren ŞEKER Article Author

    fibonacci sıralaması ile neyi kastediyorsunuz? şayet bir diziyi yada veri kaynağını sıralamak istiyorsanız, fibonacci sıralaması gibi bir yöntem yoktur. (veya varsa da ben bilmiyorum, bu konuda kaynak verirseniz inceler ve öğrenerek burada paylaşmaya çalışırım)
    Şayet bahsettiğiniz klasik fibonacci sayıları ise, aşağıdaki bağlantıda bulunan yazıya bakabilirsiniz. İhtiyacınızı çözmezse lütfen yazın eksik olan ve ihtiyacınız olan bilgiyi eklemeye çalışırız.

    http://www.bilgisayarkavramlari.com/2008/08/05/fibonacci-sayilari-fibonacci-numbers/

    Başarılar

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir


6 − iki =