01.10.2013
4.00 / 1 oy

Fibonacci Dizisi Algoritması ve Programlanması

Problem: Fibonecci dizisinin ilk 100 sayısını hesaplayarak ekrana yazan algoritmayı yapın.

Nasıl Çözeriz? Fibonecci dizisinin nasıl hesaplandığını bilmeyenleriniz olabilir. Açıklayalım: Fibonacci dizisinin ilk iki sayısı sabittir: 1 ve l'dir. Daha sonraki her sayı kendisinden önce gelen iki sayının toplamıdır. Dizi şöyle devam eder:

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610....

Önceki bölümlerde, sorulan çözerken kağıt üzerinde matematiksel bir ilişki bulursak çözümümüz kolay olur demiştik. Burada matematiksel bir ilişki vardır. Bu ilişkiyi kullanarak soruyu çözebiliriz.

Diziyi inceleyelim: Dizinin herhangi bir sayısı -buna C sayısı diyelim-kendinden önce gelen iki sayının toplamına eşittir. C sayısından bir önce gelen sayı B, iki önce gelen sayı da A olsun. O halde A+B=C diyebiliriz.

Bir sonraki sayıya geçildiğinde A sayısı işlem dışı kalır, B sayısı C'den sonra hesaplanacak sayı için A sayısı pozisyonuna geçer, C sayısı da B sayısı pozisyonuna geçer. B ve C sayılan toplanarak D sayısı bulunur: B+C=D. Dizide D'den sonra gelen E sayısı hesaplanırken ise B sayısı işlem dışı kalacaktır. C ve D sayılan toplanarak E sayısı bulunacaktır.

Dizinin herhangi bir yerinde işlem akışı şöyledir:

A + B = C

B + C = D

C + D = E

D + E = F

Dikkatinizi çeken bir şey var mı? Yukandan aşağıya işlemleri sırayla yazdığımız zaman sayılar arasında düzenli bir diziliş var. 1. sütun A, B, C, ikinci sütun B, C, D, üçüncü sütun C, D, E diye gidiyor. İşlemleri devam ettir-sek bu sıra da devam edecek gibi görünüyor.

Dizinin her elemanı için X+Y-Z (Ya da A+B-C) gibi bir formülünün geçerli olduğunu görüyoruz. Bu formülü oluşturan değerleri değişken olarak düşünürsek bu değişkenlerin dizinin ilerlemesiyle aldıklan değerlerin değiştiğini de gözlemleyebiliriz. Her değişken dizinin üretilen sayıiimıaaijtı değerlerini sırayla alıyor.

2 + 3 = 5

3 + 5 = 8

5 + 8 = 13

Bu değişimin nasıl gerçekleştiğini de aşağıdaki şema açıklıyor. Sayılar sırayla birinci değişkene (X), sonra ikinci değişkene (Y) sonra da üçüncü değişkene (Z) geçiyor ve sonra işlemden çıkıyor. Değişkenlere baktığımızda Z'nin üretildikten sonra Y'ye, Y içindeki sayıların X'e aktarıldığını görüyoruz. X içine yeni sayı gelince eski sayı siliniyor.

Eğer yazacağımız programda bu değişkenler arasında bir aktarma yapacaksak bu aktarma biraz önce anlattığımız sıranın tersi şeklinde olmalıdır çünkü örneğin, Y içindeki sayıyı X'e almadan Z sayısını Y'e yazarsak Y içindeki sayıyı silmiş oluruz.

Aktarma sırası yukandaki şekilde olmalıdır. X içindeki değere artık ihtiyacımız olmadığı için X rahatlıkla silinebilir. Y, X'e aktarılır (1. işlem). Y aktarıldığına göre Y de silinebilir. Z içindeki değer Y'ye aktarılır (2. işlem). Z değeri de aktarıldığına göre Z değişkeni yeni hesaplanan değeri alabilir (3. işlem).

Bu işlemi bir sayaç ile tekrarlanabilir hale getirdiğimizde soruyu da çözmüş oluruz.

Burada ilk 100 Fibonecci sayısını ekrana yazan algoritmanın akış şeması var.

Çözümü inceleyelim: Hemen dikkatimizi çeken bir durum var. X ve Y değerlerine başlangıçta 1 değerinin atanması. Biliyoruz ki Fibonecci dizisinin ilk iki değeri 1 'dir. Dizi 3. elemandan sonra hesaplanmaya başlar. Biz de bunun için X+Y=Z formülüne uygun olarak X ve Y değerlerini başlangıç için 1 yaptık. Ekrana Fibonacci dizisini yazdırmak gerektiği için 1. ve 2. elemanı hemen yazdırdık. Diğer elemanlar hesaplandıkça yazdırılacaklar.

Gelelim sayacın döndüğü işlemlere. İlk olarak Z=X+Y satırını görüyoruz. Burada dizinin yeni sayısı hesaplanıyor. Sayaç 1 artırılıyor, yeni hesaplanan sayı ekrana yazdırılıyor ve daha sonra değişken değerlerinin birbirlerine aktarılıyor. Biraz önce anlattığımız

X=Y

Y=Z

Z=X+Y

İşlem sırasının son satırı olan Z=X+Y hesaplama işlemi burada ilk olarak gerçekleştiği için bazı arkadaşlanmız bir hata olduğunu düşünebilirler. Değişkenlerin aktırma sırasına sadık kaldık. Çünkü sayaç döndüğü zaman bu sıra gerçekleşecektir. İlk başlangıçta dizinin ilk iki sayısı olan 1 + 1'i toplamamız gerektiği için işlem satın üstte kaldı. Aşağıda değişkenler aktarıldıktan hemen sorra sayaç dönüyor ve aynı işlem sırası yakalanıyor. Hemen yeni sayı hesaplanıyor, yazdırılıyor ve diğer işlemlere geçiliyor.

Sayacın niçin 98'e tadar kontrol edildiğini arük biliyoruz: Başlangıçta dizinin ilk 2 sayısı yazılmıştı zaten. Bu çözüm ekrana toplam olarak 100 Fibonacci sayısı yazacaktır.

Fibonacci Dizisi Algoritması ve Programlanması
Bu makalenin telif hakkı ve tüm sorumlulukları yazara ait olup, şikayetler için lütfen bizimle iletişime geçiniz.
URL:
Etiketler:

Bu makale 34722 kez okundu

01.10.2013 tarihinde yazıldı
Reitix

Yorumlar

  • utku33
    10.12.2019

    doğrudur, ilave olarak üçüncü bir değişken kullanılarak her sayının birbirine oranı da hesaplanabilir ve bu hesaplanan oranın da 0.618 ve 1.618 altın oranı olduğu giderek yakınsayarak gözlemlenebilir. ancak bu değerleri sadece çıktı almak değil bir değişken içinde tüm fibonacci (ya da ilk x fibonacci sayısı) sayıları saklanmak istenirse bir vektör kullanılmalıdır

  • RainingCodes
    10.12.2019

    sadece 2 değişken ile bir for döngüsü içerisinde a=1 ve b=1 olarak başlayan değerler a=a+b ve b=a+b olarak güncellenerek ve her güncellemeden sonra ekrana yazdırılarak fibonacci sayılarını ekrana yazdıran bir program hazırlanabilir. burada dikkat edilecek nokta ise a ve b sayılarının veri tipinin ne olduğudur çünkü tüm programlama dillerinde int ya da double gibi veri tiplerinin bir değer saklama limiti vardır ve bu limit aşıldığında eksi sayılar gibi anlamsız sayılar görülebilir

  • artha
    27.10.2019

    sayıların birbirlerine bölümünün bir noktadan sonra hep aynı sayıyı vermesi değil ama bu sayının doğadaki ve insan psikolojisindeki bir çok davranış ile aynı sayı olması bence halen gizemini koruyan bir konu.. doğanın yasaları var da farkında olmadan bununla mücadele ediyorsak bunu fark ettiğimizde kendimize çok güleceğiz

  • ruhan
    03.03.2019

    farklı bir oranın varlığı çok da önemli değil çünkü doğadaki altın oranın da bu değerler ile elde edilmesi aslında konuyu asıl gizemli kılan unsur, farklı bir başlangıç noktası ile yakınsayan farklı bir oran sadece bir oran olur ama altın olamamış olur

  • ersan070
    18.11.2018

    acaba farklı bir algoritmaya sahip bir dizi olsa da belirli bir yerden sonra farklı bir orana yakınsayamaz mıydı? mesela bu oran da altın orandan farklı olsa ve bunu doğanın farklı yerlerinde tespit etsem buna altından daha kıymetli bir madenin oranı desem olmaz mı?

  • WebManiac
    27.09.2018

    bir çok bilimkurgu filmine ilham kaynağı olmuş olan fibonacci sayıları ve arkadaşların da bahsettiği oranları önce bir anlamanız ve işin gizem boyutunu kadanızda tam olarak oturtmanız bence çok önemli, böylece işi kodlamaya geçince de aslında neleri programlayabiliyor olduğunuzu daha iyi özümseyebilirsiniz

  • hakanbeys12
    19.06.2018

    dizinin tüm elemanlarını saklamak isterseniz birden çok değer saklayabilen bir vektör ya da collection değişken tanımlamanız ve her iterasyondan sonra güncel değeri bu değişkene yazdırmalısınız

  • kuzu
    14.04.2018

    her rakamı birbirine oranladığınızda altın orana biraz daha yakınlaştığını farkedeceksiniz, sonunda da hem evrende hem de kalabalıkların psikolojik davranışlarında sıklıkla karşılaşılan 0.618 ve 1.618 rakamları ile karşılaşacaksınız

  • kirklar39
    17.11.2014

    1 1 2 3 5 8 13 21... dizinin her eklenecek yeni terimi fibonacci dizisinde en son iki terim neyse onların toplamı olur.örneğin bir sonraki terim 13+21=34 olacaktır

  • ercan cskn
    15.10.2014

    tavşanların üremesinin incelenmesiyle bulunmuştu sanırım Fibonacci dizisi

  • erdem
    20.10.2013

    Çok keyifli konular bunlar, somut konularla programlama öğrenmek daha da kolaylaşıyor, teşekkür ederim

  • dost
    19.10.2013

    Hayatın algoritma ile betimlenmesi gibi, sims gibi :)

  • Gurcan80
    11.10.2013

    Sayın karagöz, aynı uygulamayı bir döngü ile uzatarak oranın 1.618'e yakınsadığını gözlemleyebilirsiniz

  • karagöz
    06.10.2013

    Teşekkürler.. Altın orana ilişkin de makaleler arıyorum, bilginiz var mı?

  • fatih arslan
    02.10.2013

    Sade bir çözüm, güzel bir anlatım. Teşekkür ederim

Bu yazıya siz de yorum yapabilirsiniz

İnternet sitemizdeki deneyiminizi iyileştirmek için çerezler kullanıyoruz. Bu siteye giriş yaparak çerez kullanımını kabul etmiş sayılıyorsunuz. Daha fazla bilgi.