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.